資源描述：
《第十章樹與有序樹.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第十章樹與有序樹10.1樹的基本概念10.2連通圖的生成樹和帶權(quán)連通圖的最小生成樹10.3有序樹10.4前綴碼和最優(yōu)二分樹家譜PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory一般假定在孩子是按年齡排序的,則這種樹是有序的。語法樹英語句子“Thebigelephantatethepeanut”可以圖解如下圖，稱之為這個英語句子的語法樹。有向樹定義1一個有向圖，若去掉邊的方向，所得無向圖是一棵樹，則稱這個有向圖為有向樹。(a)(b)例兩個有向
2、樹的例子。今后只討論(b)這樣的所謂的“根樹”——有一個根的樹。根樹設(shè)T=(V,E)是一棵有向樹，若僅有一個頂點的入度為0，其余的頂點的入度均為1，這樣一棵有向樹我們稱為根樹。入度為0的頂點稱為樹根，出度為0的頂點稱為樹葉，出度不為0的頂點稱為分枝點。例abcdeabcde父親、兒子、祖先、后代、兄弟設(shè)T=(V,E)是一棵根樹。如果e=(v,u)?E，稱v是u的父親，u是v的兒子。對v1,v2?V，若存在一條從v1到v2的通路，則稱v1是v2的祖先，v2是v1的后代。若(v0，v1)，(v0，v2)?E，說v
3、1與v2是兄弟。abedinm子樹設(shè)T=(V,E)是一棵根樹。v0?V，v0是中一個分支點,所謂以v0為根的子樹是指T的一個子圖T’，T’以v0和v0的全部的后代為頂點，以從v0出發(fā)的所有通路經(jīng)過的邊為邊。以v0的一個兒子為根的子樹稱為v0的子樹。abedinm例試回答問題哪個是樹根?哪些是樹葉?哪個是e的父親?哪些是e的祖先?哪些是e的兒子?哪些是e的后代?哪些是e的兄弟?哪些是e的子樹?acbedfhgilkjnm有序樹定義2一棵根樹，若每一個分枝點出發(fā)的邊，分別標(biāo)以整數(shù)1，2，?，k。則稱這樣的根樹為有
4、序樹。有序樹可以說是各子樹從左到右是有次序的樹句子主語謂語形容詞冠詞名詞Thebigelephantatethepeanut例例需要說明的是，一棵有序樹的每個分枝點出發(fā)的邊的標(biāo)號并不是要求是連續(xù)的。一個分枝點出發(fā)的邊，若被標(biāo)上i，則稱這條邊是這個分枝點的i子樹。如上圖，一個分枝點出發(fā)的兩條邊被分別標(biāo)上1，3，我們說這個分枝點沒有第2子樹。句子主語謂語形容詞冠詞名詞Theelephantatethepeanut13m－分樹、正則m－分樹如果一棵有序樹的每個分枝點最多有m個兒子，稱這棵有序樹為m－分樹。若一棵m－
5、分樹的每一個分枝點恰好有m個兒子，稱這樣的m－分樹為正則m－分樹。2－分樹:左子樹、右子樹對于2－分樹，它的每一個分枝點的第一個子樹和第二子樹又分別叫左子樹和右子樹。例單淘汰賽的正則2-分樹定理9一棵正則m－分樹的分枝點的個數(shù)為i，樹葉的個數(shù)為t，則有(m-1)i=t-1證明：總共有i個分枝點，每個分枝點有m個兒子，故總的兒子數(shù)目為mi。而所有的兒子包括全部頂點減去一個根，即為i+t-1，所以有：mi=i+t-1即為（m-1)i=t-1。例5用帶4個插座的接線板，連接19個燈到一個總插座上，問至少需要多少塊接
6、線板。解：任何一個連接方法都是一棵4－分樹，按定理9中公式，有(4-1)i≥19－1,所以i≥6樹形圖的高度、頂點的路長在一棵樹形圖中，一個頂點的路長規(guī)定為從樹根到這個頂點的通路的長。一棵樹形圖的高度即為該樹中最長路的長度。在一棵樹形圖中從樹根到每一個頂點有且僅有唯一的一條通路。高為h的正則m－分樹高為h的正則m－分樹，最多有mh片樹葉，而至少有m+(m-1)(h-1)片樹葉。例求證一棵正則2－分樹必有奇數(shù)個頂點。證明:假設(shè)一棵正則2－分樹有i個分枝點、t個樹葉。每個分枝點有2個兒子，故總的兒子數(shù)目為2i。而
7、所有的兒子包括全部頂點減去一個根，所以有：2i=i+t-1即為i=t-1。從而全部頂點數(shù)目為i+t=(t-1)+t=2t-1顯然,它是一個奇數(shù)，結(jié)論得證明。例數(shù)學(xué)表達式的二分樹(二叉樹)以二叉樹表示數(shù)學(xué)表達式的遞歸定義：若表達式=(第一表達式)(運算符)(第二表達式),則以左子樹表示第一表達式以右子樹表示第二表達式根結(jié)點的數(shù)據(jù)庫存放運算符+*/cdab(a*b)+(c/d)++d+cab((a+b)+c)+d第十章樹與有序樹10.1樹的基本概念10.2連通圖的生成樹和帶權(quán)連通圖的最小生成樹10.3有序樹10.
8、4前綴碼和最優(yōu)二分樹
