第六章 樹和二叉樹

1、第第6 6章章 樹和二叉樹樹和二叉樹樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)關(guān)系定義的層次結(jié)構(gòu)6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語一、樹的定義一、樹的定義 樹是有樹是有 n (n 0) 個(gè)結(jié)點(diǎn)的有限集合。如果個(gè)結(jié)點(diǎn)的有限集合。如果 n=0，稱，稱為為空樹空樹；如果；如果 n 0，則：，則：有且僅有一個(gè)特定的稱之為有且僅有一個(gè)特定的稱之為根根(Root)的結(jié)點(diǎn)，它的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；只有直接后繼，但沒有直接前驅(qū)；當(dāng)當(dāng)n 1，除根以外的其它結(jié)點(diǎn)劃分為，除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個(gè)互不相交的有限集個(gè)互不

2、相交的有限集 T1, T2 , Tm，其中每個(gè)集合，其中每個(gè)集合本身又是一棵樹，并且稱為根的本身又是一棵樹，并且稱為根的子樹子樹(SubTree)。例如例如:A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹其中：其中：A是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的的子樹，且本身也是一棵樹子樹，且本身也是一棵樹有有13個(gè)結(jié)點(diǎn)的樹個(gè)結(jié)點(diǎn)的樹ACGBDEFKLHMIJ子樹樹結(jié)構(gòu)的四種表示方法：樹結(jié)構(gòu)的四種表示方法：2)括號(hào)表示法：括號(hào)表示法：(A(B(E(K,L),F),C(G),D(

3、H(M),I,J)FKLEBMHIJDGCA3)嵌套集合表示法嵌套集合表示法ABEKLFCGDHMIJ4)凹入表示法凹入表示法ACGBDEFKLHMIJ1)倒立樹表示法倒立樹表示法二、樹的基本術(shù)語二、樹的基本術(shù)語樹的結(jié)點(diǎn)樹的結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支孩子結(jié)點(diǎn)孩子結(jié)點(diǎn):結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子雙親結(jié)點(diǎn)雙親結(jié)點(diǎn):B結(jié)點(diǎn)是結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子結(jié)點(diǎn)的孩子,則則A結(jié)點(diǎn)是結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親結(jié)點(diǎn)的雙親兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn):同一雙親的孩子結(jié)點(diǎn)同一雙親的孩子結(jié)點(diǎn)堂兄結(jié)點(diǎn)堂兄結(jié)點(diǎn):同一層上，不同一雙親的結(jié)點(diǎn)同一層上，不同一雙親的

4、結(jié)點(diǎn)結(jié)點(diǎn)層結(jié)點(diǎn)層:根結(jié)點(diǎn)的層定義為根結(jié)點(diǎn)的層定義為1,根的孩子為第根的孩子為第2層結(jié)點(diǎn)層結(jié)點(diǎn)樹的高度（深度）樹的高度（深度）:樹中結(jié)點(diǎn)的最大層次數(shù)樹中結(jié)點(diǎn)的最大層次數(shù)結(jié)點(diǎn)的度結(jié)點(diǎn)的度:結(jié)點(diǎn)的子樹個(gè)數(shù)結(jié)點(diǎn)的子樹個(gè)數(shù)樹的度樹的度: 樹中各結(jié)點(diǎn)的度的最大值樹中各結(jié)點(diǎn)的度的最大值葉子結(jié)點(diǎn)葉子結(jié)點(diǎn):也叫終端結(jié)點(diǎn)，是度為也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)的結(jié)點(diǎn)分枝結(jié)點(diǎn)分枝結(jié)點(diǎn):度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；森林森林:互不相交的樹集合；互不相交的樹集合；有序樹有序樹:子樹從左到右有序子樹從左到右有序,(即左右子樹不能互換即左右子樹不能互換)無序樹無序樹:不考慮子樹的左右順序；不考慮子樹的左右順序；結(jié)點(diǎn)結(jié)點(diǎn)A的度：

5、的度：結(jié)點(diǎn)結(jié)點(diǎn)B的度：的度：結(jié)點(diǎn)結(jié)點(diǎn)M的度：的度：葉子：葉子：結(jié)點(diǎn)結(jié)點(diǎn)A的孩子：的孩子：結(jié)點(diǎn)結(jié)點(diǎn)B的孩子：的孩子：結(jié)點(diǎn)結(jié)點(diǎn)I的雙親：的雙親：結(jié)點(diǎn)結(jié)點(diǎn)L的雙親：的雙親：結(jié)點(diǎn)結(jié)點(diǎn)B，C，D為兄弟為兄弟結(jié)點(diǎn)結(jié)點(diǎn)K，L為兄弟為兄弟樹的度：樹的度：結(jié)點(diǎn)結(jié)點(diǎn)A的層次：的層次：結(jié)點(diǎn)結(jié)點(diǎn)M的層次：的層次：樹的深度：樹的深度：結(jié)點(diǎn)結(jié)點(diǎn)F，G為堂兄弟為堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)A是結(jié)點(diǎn)是結(jié)點(diǎn)F，G的祖先的祖先320B,C,DE,F314K，L，F(xiàn)，G，M，I，JDE4ACGBDEFKLHMIJ 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, de

6、finition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Parent(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( )

7、;三、樹的基本操作三、樹的基本操作62175 438910 11 12五種基本形態(tài)：五種基本形態(tài)：一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成的、互不相交的二叉樹組成LLRR6.2 二叉樹二叉樹一、定義一、定義每個(gè)結(jié)點(diǎn)至多有二棵子樹每個(gè)結(jié)點(diǎn)至多有二棵子樹( (即不存在度大于即不存在度大于2 2的結(jié)點(diǎn)的結(jié)點(diǎn)) )二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的子樹有左、右之分，且其次序不能任意顛倒特點(diǎn)特點(diǎn)：1、滿二叉樹、

8、滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k-1個(gè)結(jié)點(diǎn)的二叉樹個(gè)結(jié)點(diǎn)的二叉樹二、兩種特殊形態(tài)的二叉樹二、兩種特殊形態(tài)的二叉樹621754389 10 1113 14 1512滿二叉樹滿二叉樹2、完全二叉樹、完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為若設(shè)二叉樹的高度為h，則共有，則共有h層，除第層，除第 h 層外，層外，其它各層其它各層 (1 h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左層從右向左連續(xù)連續(xù)缺若干結(jié)點(diǎn)缺若干結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)都與深度為每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從的滿二叉樹

9、中編號(hào)從1到到n結(jié)結(jié)點(diǎn)一一對(duì)應(yīng)點(diǎn)一一對(duì)應(yīng)621754389 10 11 12完全二叉樹完全二叉樹215436 7216543非完全二叉樹非完全二叉樹性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。(i 1) 證明用歸納法證明用歸納法證明：證明：當(dāng)當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，時(shí)，只有根結(jié)點(diǎn)，2i-1=20=1假設(shè)對(duì)所有假設(shè)對(duì)所有j，ij 1，命題成立，即第，命題成立，即第j層上至多有層上至多有2j-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)由歸納假設(shè)第由歸納假設(shè)第i-1 層上至多有層上至多有 2i-2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2，故在第，故

10、在第i層上的最層上的最大結(jié)點(diǎn)數(shù)為第大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的層上的最大結(jié)點(diǎn)數(shù)的2倍，即倍，即2*2i-2= 2i-16.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)2 深度為深度為 k 的二叉樹至多有的二叉樹至多有 2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k 1)kii112 20 + 21 + + 2k-1 = 2k-1kii1(層上的最大結(jié)點(diǎn)數(shù)）第證明：證明：由性質(zhì)由性質(zhì)1可見，深度為可見，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)的二叉樹的最大結(jié)點(diǎn)數(shù)性質(zhì)性質(zhì)3 對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹T, 如果其葉子結(jié)點(diǎn)數(shù)為如果其葉子結(jié)點(diǎn)數(shù)為n0, 度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n2,則則n0n21.證明證

11、明:若度為若度為1的結(jié)點(diǎn)有的結(jié)點(diǎn)有 n1 個(gè)，個(gè)，結(jié)點(diǎn)個(gè)數(shù)為，結(jié)點(diǎn)個(gè)數(shù)為 n，則：則：n = n0 + n1 + n2 若總邊數(shù)為若總邊數(shù)為 e e，則根據(jù)二叉樹的定義有：，則根據(jù)二叉樹的定義有：e = 2n2 + n1 = n - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 證明：證明：設(shè)完全二叉樹的深度為設(shè)完全二叉樹的深度為 k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2和完全和完全二叉樹的定義有二叉樹的定義有2k-1 - 1 n 2k- 1或或 2k-1 n 2k取對(duì)數(shù)取對(duì)數(shù) k-1 log2n 1，則其雙親是結(jié)點(diǎn)，則其雙親是

12、結(jié)點(diǎn) i/2 2)如果如果2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；為葉子結(jié)點(diǎn)，無左孩子； 否則，其左孩子是結(jié)點(diǎn)否則，其左孩子是結(jié)點(diǎn)2i3)如果如果2i1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無右孩子；無右孩子； 否則，其右孩子是結(jié)點(diǎn)否則，其右孩子是結(jié)點(diǎn)2i162175438910 11 12練習(xí)：練習(xí)：1、設(shè)樹、設(shè)樹T的度為的度為4，其中度為，其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分的結(jié)點(diǎn)個(gè)數(shù)分別為別為4,2,1,1。T有多少個(gè)葉子葉子結(jié)點(diǎn)？有多少個(gè)葉子葉子結(jié)點(diǎn)？2、設(shè)一棵完全二叉樹有、設(shè)一棵完全二叉樹有1000個(gè)結(jié)點(diǎn)。問該完全二個(gè)結(jié)點(diǎn)。問該完全二叉樹有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為叉樹有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)

13、度為2的結(jié)點(diǎn)？的結(jié)點(diǎn)？有多少個(gè)度為有多少個(gè)度為1的結(jié)點(diǎn)？若完全二叉樹有的結(jié)點(diǎn)？若完全二叉樹有1001個(gè)結(jié)個(gè)結(jié)點(diǎn)，再回答上述問題，并說明理由。點(diǎn)，再回答上述問題，并說明理由。 1、解：各結(jié)點(diǎn)射出的分支總數(shù)為：、解：各結(jié)點(diǎn)射出的分支總數(shù)為： 4*1+2*2+1*3+4*1=15即樹中總結(jié)點(diǎn)為：即樹中總結(jié)點(diǎn)為：15+1=16由條件可知非葉子結(jié)點(diǎn)數(shù)為：由條件可知非葉子結(jié)點(diǎn)數(shù)為：4+2+1+1=8即葉子結(jié)點(diǎn)個(gè)數(shù)為：即葉子結(jié)點(diǎn)個(gè)數(shù)為：16-8=82、解：若完全二叉樹中結(jié)點(diǎn)總數(shù)為偶數(shù)，則：、解：若完全二叉樹中結(jié)點(diǎn)總數(shù)為偶數(shù)，則：n1=1,n0=n2+1;即此題中：即此題中：n0=500,n1=1,n2=49

14、9若完全二叉樹中結(jié)點(diǎn)總數(shù)為奇數(shù)，則：若完全二叉樹中結(jié)點(diǎn)總數(shù)為奇數(shù)，則： n1=0,n0=n2+1;即此題中：即此題中：n0=501,n1=0,n2=500完全二叉樹完全二叉樹 的順序表示的順序表示6.2.36.2.3 、二叉樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的存儲(chǔ)結(jié)構(gòu)12489 105673一、順序表示一、順序表示1 2 3 4 5 6 7 8 9 10第第i個(gè)結(jié)點(diǎn)的左右孩子一定個(gè)結(jié)點(diǎn)的左右孩子一定保存在第保存在第2i和和2i+1號(hào)單元里號(hào)單元里缺點(diǎn)缺點(diǎn):浪費(fèi)空間。最壞的情況下，深度為浪費(fèi)空間。最壞的情況下，深度為k且只有且只有k個(gè)個(gè)結(jié)點(diǎn)的單支樹，卻需要長度為結(jié)點(diǎn)的單支樹，卻需要長度為2k-1的一維數(shù)組的一

15、維數(shù)組9123654789 10一般二叉樹的順序表示一般二叉樹的順序表示1090000876504321二、鏈表表示二、鏈表表示含兩個(gè)指針域的結(jié)點(diǎn)結(jié)含兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)構(gòu)lChild data rChild含三個(gè)指針域的結(jié)點(diǎn)結(jié)含三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)構(gòu)lChild data parent rChild二叉鏈表二叉鏈表 data lChildrChild三叉鏈表三叉鏈表parent data lChildrChildlchild data rchild ABCDEFG AB C D E F Gtypedef struct BiTNode TElemType data; struct BiTNod

16、e *lchild , *rchild ; BiTNode , *BiTree ;1、二叉鏈表的存儲(chǔ)表示、二叉鏈表的存儲(chǔ)表示在在n個(gè)結(jié)點(diǎn)的二叉鏈表中有個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域個(gè)空鏈域lchild data parent rchild A B C D E F Gtypedef struct BiTNode TElemType data; struct BiTNode *lchild , *rchild, *parent ; BiTNode , *BiTree ;2、三叉鏈表的存儲(chǔ)表示、三叉鏈表的存儲(chǔ)表示ABCDEFG遍歷：遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且按某種搜索路徑訪問

17、二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次每個(gè)結(jié)點(diǎn)僅被訪問一次訪問：訪問：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如何二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如何訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次？訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次？6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)可以在遍歷基礎(chǔ)上實(shí)現(xiàn)對(duì)于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只

18、有一個(gè)直接后繼，遍歷對(duì)于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼，遍歷是很容易的事是很容易的事一、二叉樹的遍歷方法一、二叉樹的遍歷方法令令:L:遍歷左子樹遍歷左子樹 D:訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) R:遍歷右子樹遍歷右子樹有六種遍歷方法有六種遍歷方法: DLR，LDR，LRD,DRL，RDL，RLD先左后右先左后右,有三種遍歷方法：有三種遍歷方法： DLR、LDR、LRD ，分別稱為分別稱為先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷二叉樹的遍歷可以分解為二叉樹的遍歷可以分解為:訪問根，遍歷左子樹和遍訪問根，遍歷左子樹和遍歷右子樹歷右子樹 A A B B D D C C E E F F G

19、G1、先序遍歷（、先序遍歷（DLR）若二叉樹非空若二叉樹非空 (1)訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； (2)先序遍歷左子樹；先序遍歷左子樹； (3)先序遍歷右子樹；先序遍歷右子樹； 先序遍歷序列：先序遍歷序列：A B D E G C F例例:先序遍歷右圖所示的二叉樹先序遍歷右圖所示的二叉樹 （1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A （2）先序遍歷左子樹）先序遍歷左子樹 （3）先序遍歷右子樹）先序遍歷右子樹 A A B B D D C C E E F F G G2、中序遍歷（、中序遍歷（LDR）若二叉樹非空若二叉樹非空(1)中序遍歷左子樹中序遍歷左子樹(2)訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)(3)中序遍歷右子樹中序遍歷右子樹

20、中序遍歷序列：中序遍歷序列： D B G E A C F例例:中序遍歷右圖所示的二叉樹中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹）中序遍歷左子樹 （2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A （3）中序遍歷右子樹）中序遍歷右子樹 A A B B D D C C E E F F G G3、后序遍歷（、后序遍歷（LRD）若二叉樹非空若二叉樹非空(1)后序遍歷左子樹后序遍歷左子樹(2)后序遍歷右子樹后序遍歷右子樹(3)訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 后序遍歷序列：后序遍歷序列： D G E B F C A例：例：后序遍歷右圖所示的二叉樹后序遍歷右圖所示的二叉樹 （1）后序遍歷左子樹）后序遍歷左子樹 （2）后序遍歷右子樹

21、）后序遍歷右子樹 （3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A A A B B D D C C E E F F G G 先序遍歷序列：先序遍歷序列：例例:用二叉樹表示表達(dá)式用二叉樹表示表達(dá)式 a+b*(c-d)-e/f- + a * b c d / e f 前綴式前綴式(波蘭式波蘭式)中序遍歷序列：中序遍歷序列：a + b * c d e / f 中綴式中綴式后序遍歷序列：后序遍歷序列：a b c d - * + e f / - 后綴式后綴式(逆波蘭式逆波蘭式) 若二叉樹非空若二叉樹非空 （1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹）先序遍歷左子樹 （3）先序遍歷右子樹；）先序遍歷右子樹；二、遍歷

22、的遞歸算法二、遍歷的遞歸算法 上面介紹了三種遍歷方法，顯然可以用遞歸的方式實(shí)現(xiàn)上面介紹了三種遍歷方法，顯然可以用遞歸的方式實(shí)現(xiàn)三種遍歷方法，以先序?yàn)槔喝N遍歷方法，以先序?yàn)槔合刃虮闅v的定義：先序遍歷的定義：先序遍歷遞歸算法先序遍歷遞歸算法void PreOrderTraverse(BiTree T) if (T) printf(T-data)； PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); A A B B D D C C E E F F G G H H I I J J K K L L三、三、 遍歷的非遞歸算法遍歷的非遞歸算法

23、(以中序遍歷為例以中序遍歷為例)中序遍歷序列：中序遍歷序列： H D K I L B E J A F C G A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); t=T; while (t) Push(S,t); t=t-lchild; if (!StackEmpty(S) Pop(S,t); printf(t-data); t=t-rchild; while(t | !StackEmpty(S) A A B B D D C C E E F F G G H H I

24、 I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p);printf(p-data); p=p-rchild; A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p)&

25、amp;p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); printf(p-data); Push(S,p-rchild); A A B B D D C C E E F F G G H H I I J J K K L L四、二叉樹的建立四、二叉樹的建立基本思想：基本思想：輸入輸入在空子樹處添加在空子樹處添加*的二叉樹的的二叉樹的先序序列先序序列設(shè)每個(gè)元素是一個(gè)字符，按先序遍歷的順序，建立二叉設(shè)每個(gè)元素是一個(gè)字符，按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)，并完成相應(yīng)結(jié)點(diǎn)的鏈接。鏈表的所有結(jié)點(diǎn)，并完成相應(yīng)結(jié)點(diǎn)的鏈接。 D D A

26、A BB C C EE FFT T* * * * * * * *(在空子樹處添加在空子樹處添加*的二叉樹的的二叉樹的)先序序列：先序序列：A B D * F * * * C E * * * A A B B D D C C E E F F先序序列：先序序列：A B D F C E A A B B D D C C E E F FStatus CreateBiTree(BiTree &T) scanf (&ch); if (ch= = * ) T=NULL; else if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW)

27、; T-date = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; D D A A BB C C EE FFT T輸入：輸入：A B D * F * * * C E * * *五、利用中序、先序法或中序、后序法求二叉樹五、利用中序、先序法或中序、后序法求二叉樹1、利用中序、先序法求二叉樹、利用中序、先序法求二叉樹步驟步驟: (1)利用先序順序可知：第一個(gè)是根利用先序順序可知：第一個(gè)是根(2)利用中序順序，配合步驟利用中序順序，配合步驟(1)所找到的根作對(duì)所找到的根作對(duì)應(yīng)，可分成左右兩子樹應(yīng)，可分成左右兩子樹(3)再

28、分別按再分別按(1)(2)步驟處理左、右子樹，找到其步驟處理左、右子樹，找到其他的根和終端結(jié)點(diǎn)他的根和終端結(jié)點(diǎn)例例:中序序列中序序列: D C E F B H G A K J L I M 先序序列先序序列: A B C D E F G H I J K L M2、利用中序、后序法求二叉樹、利用中序、后序法求二叉樹步驟步驟: (1)利用后序順序可知：最后一個(gè)一定是根利用后序順序可知：最后一個(gè)一定是根(2)利用中序順序，配合步驟利用中序順序，配合步驟(1)所找到的根作對(duì)所找到的根作對(duì)應(yīng)，可分成左右兩子樹應(yīng)，可分成左右兩子樹(3)再分別按再分別按(1)(2)步驟來處理左、右子樹步驟來處理左、右子樹例例

29、:中序序列中序序列: D C E F B H G A K J L I M 后序序列后序序列: D F E C H G B K L J M I A練習(xí)：練習(xí)：1、已知中序序列、已知中序序列:DCEBAKJF 后序序列后序序列:DECBKJFA2、已知中序序列、已知中序序列:A-B*C+D/E*F 先序序列先序序列:/+-A*BCD*EF3、已知中序序列、已知中序序列:CBEDFAHJKIG 后序序列后序序列:CEFDBKJIHGAJ計(jì)算二叉樹的結(jié)點(diǎn)個(gè)數(shù)計(jì)算二叉樹的結(jié)點(diǎn)個(gè)數(shù)J求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)J求二叉樹的高度求二叉樹的高度J按層次遍歷二叉樹按層次遍歷二叉樹六、線索二叉

30、樹六、線索二叉樹 (Threaded Binary Tree)1 1、基本概念、基本概念前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中，兩個(gè)相鄰的結(jié)點(diǎn)互稱為序列中，兩個(gè)相鄰的結(jié)點(diǎn)互稱為前驅(qū)與后繼。前驅(qū)與后繼。線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針。線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針。線索二叉樹：加上線索的二叉鏈表表示的二叉樹。線索二叉樹：加上線索的二叉鏈表表示的二叉樹。即加上結(jié)點(diǎn)前趨、后繼信息的二叉樹。即加上結(jié)點(diǎn)前趨、后繼信息的二叉樹。線索化：對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索線索化：對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程。二叉樹的過程。有有n個(gè)結(jié)點(diǎn)的二

31、叉鏈表，有個(gè)結(jié)點(diǎn)的二叉鏈表，有n+1個(gè)空指針域，故可個(gè)空指針域，故可利用這些的空指針域存放結(jié)點(diǎn)的前趨和后繼指針，利用這些的空指針域存放結(jié)點(diǎn)的前趨和后繼指針，以這種結(jié)點(diǎn)構(gòu)成的二叉鏈表稱為以這種結(jié)點(diǎn)構(gòu)成的二叉鏈表稱為線索鏈表。線索鏈表。在線索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域在線索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域：Ltag=0, lchild指向其左孩子指向其左孩子1, lchild指向其前驅(qū)指向其前驅(qū)Rtag= 0, rchild指向其右孩子指向其右孩子1, rchild指向其后繼指向其后繼2、實(shí)現(xiàn)、實(shí)現(xiàn)結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)LtagRtag線索鏈表的類型說明線索鏈表的類型說明typedef enum link

32、 , thread PointerTag; typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; BiThrNode，*BiThrTreeABCDE A B D C ET先序序列：ABCDE0000111111LtagRtag1）先序線索二叉樹先序線索二叉樹 A B D C ET中序序列：BCAED0000111111ABCDE2）中）中序線索二叉樹序線索二叉樹 A B D C ET后序序列：CBEDA0000111111ABCDE3）后）后序線索二叉

33、樹序線索二叉樹1、雙親表示：、雙親表示：通過保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，通過保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系6.4 樹和森林樹和森林一、樹的存儲(chǔ)結(jié)構(gòu)一、樹的存儲(chǔ)結(jié)構(gòu)typedef struct PTNode TElemType data; int parent; PTNode;parentdata存儲(chǔ)實(shí)現(xiàn)時(shí)，以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在結(jié)存儲(chǔ)實(shí)現(xiàn)時(shí)，以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在結(jié)點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在鏈表中的位置。點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在鏈表中的位置。用雙親表示實(shí)現(xiàn)的樹定義用雙親表示實(shí)現(xiàn)的樹定義#define M

34、AX_TREE_SIZE 100typedef struct PTNode nodesMAX_TREE_SIZE; int r,n;/根位置，結(jié)點(diǎn)數(shù)根位置，結(jié)點(diǎn)數(shù)PTree; 如何找孩子結(jié)點(diǎn)如何找孩子結(jié)點(diǎn)?特點(diǎn)：特點(diǎn)：找結(jié)點(diǎn)的雙親容易，找結(jié)點(diǎn)的孩子難找結(jié)點(diǎn)的雙親容易，找結(jié)點(diǎn)的孩子難7 70 0T.nT.rABCDEFG3G1F1E0D0C0B-1Adata parent01234562、孩子表示法、孩子表示法通過保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置通過保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置,表示樹中結(jié)點(diǎn)之間表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系的結(jié)構(gòu)關(guān)系與雙親表示法相反與雙親表示法相反,孩子表示法適合實(shí)現(xiàn)涉及孩子的操作孩子

35、表示法適合實(shí)現(xiàn)涉及孩子的操作方法一方法一 ：多重鏈表（類似二叉鏈表）：多重鏈表（類似二叉鏈表）兩種方式：定長結(jié)點(diǎn)兩種方式：定長結(jié)點(diǎn) 不定長結(jié)點(diǎn)不定長結(jié)點(diǎn)1、定長結(jié)點(diǎn)定長結(jié)點(diǎn)等數(shù)量的鏈域等數(shù)量的鏈域 data child1child2child3childdABCDEFGABCDEFG 空鏈域空鏈域n(k-1)+1個(gè)個(gè) data degree child1child2childd2、不定長結(jié)點(diǎn)不定長結(jié)點(diǎn)IACBDHGFE方法二：孩子鏈表方法二：孩子鏈表對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn) 1 3 2 8 7 6 4 5 IHGFE DC B A 0 1

36、 2 3 4 5 6 7 8 9 90 0T.nT.r樹的孩子鏈表類型定義樹的孩子鏈表類型定義typedef struct CTNode int child; struct CTNode * next; * ChildPtr; typedef struct TElemType data; ChildPtr firstchild; CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r;CTree;0 1 2 3 4 5 6 7 8 9 90 0T.nodesT.nT.rIHGF E DC B A 1 3 2 8 7 6 4 5 特點(diǎn)：特

37、點(diǎn)：找結(jié)點(diǎn)的孩子容易，找結(jié)點(diǎn)的雙親難找結(jié)點(diǎn)的孩子容易，找結(jié)點(diǎn)的雙親難方法三：帶雙親的孩子鏈表方法三：帶雙親的孩子鏈表將雙親表示和孩子表示聯(lián)合起來。將雙親表示和孩子表示聯(lián)合起來。0 1 2 3 4 5 6 7 833211000-1 IHGF E DC B A 1 3 2 8 7 6 4 5 IACBDHGFE特點(diǎn)：特點(diǎn)：找結(jié)點(diǎn)的雙親和孩子都容易。找結(jié)點(diǎn)的雙親和孩子都容易。ABRECDFGHKP137圖圖6.14(b)方法四：孩子兄弟表示法方法四：孩子兄弟表示法用二叉鏈鏈表作為樹的存貯結(jié)構(gòu)用二叉鏈鏈表作為樹的存貯結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： datafirstchildnextsiblingtype

38、def struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;結(jié)構(gòu)定義：結(jié)構(gòu)定義：ABCDEFG空鏈域空鏈域n+1個(gè)個(gè)A BE F G D C 特點(diǎn)：特點(diǎn)：操作容易操作容易破壞了樹的層次破壞了樹的層次例如：例如：二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導(dǎo)出樹與二叉樹之間的轉(zhuǎn)換可導(dǎo)出樹與二叉樹之間的轉(zhuǎn)換樹樹根根結(jié)點(diǎn)結(jié)點(diǎn)X的第一個(gè)孩子的第一個(gè)孩子結(jié)點(diǎn)結(jié)點(diǎn)X緊鄰的右兄弟緊鄰的右兄弟二叉樹二叉樹 根根 結(jié)點(diǎn)結(jié)點(diǎn)X的左孩子的左孩子

39、 結(jié)點(diǎn)結(jié)點(diǎn)X的右孩子的右孩子二、樹與二叉樹的轉(zhuǎn)換二、樹與二叉樹的轉(zhuǎn)換I IA AC CD DH HG GF FE E樹樹B B二叉樹二叉樹F FI IA AB BH HG GE EC CD DA BE CG D H I F 樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換I IA AC CD DH HG GF FE E樹樹B B二叉樹二叉樹F FI IA AB BH HG GE EC CD D樹轉(zhuǎn)換成的二叉樹其右子樹一定為空樹轉(zhuǎn)換成的二叉樹其右子樹一定為空森林：樹的集合森林：樹的集合 將森林中樹的根看成兄弟，可用樹的孩子兄弟表示將森林中樹的根看成兄弟，可用樹的孩子兄弟表示法來存儲(chǔ)森林；用樹與二叉樹的轉(zhuǎn)換方法，

40、進(jìn)行森林與法來存儲(chǔ)森林；用樹與二叉樹的轉(zhuǎn)換方法，進(jìn)行森林與二叉樹轉(zhuǎn)換；可用樹的遍歷方法對(duì)森林進(jìn)行遍歷二叉樹轉(zhuǎn)換；可用樹的遍歷方法對(duì)森林進(jìn)行遍歷包含兩棵樹的森林包含兩棵樹的森林I IA AC CD DH HG GF FE EB B J J K K M M N N L L O O P PT1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林的二叉樹表示森林的二叉樹表示森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換ABCDEFGHIKJ樹根相連樹根相連三、樹的遍歷三、樹的遍歷先根次序遍歷先根次序遍歷后根次序遍歷后根次序遍歷對(duì)應(yīng)二叉樹先序遍歷對(duì)應(yīng)二叉樹先序遍歷 ABEFCGDHI樹的先根遍歷結(jié)果與

41、其對(duì)應(yīng)二叉樹樹的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的先序遍歷結(jié)果相同表示的先序遍歷結(jié)果相同1、樹的先根次序遍歷、樹的先根次序遍歷I IA AC CB BD DH HG GF FE E當(dāng)樹非空時(shí)當(dāng)樹非空時(shí) 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 依次先根遍歷根的各棵子樹依次先根遍歷根的各棵子樹樹先根遍歷樹先根遍歷 ABEFCGDHIF FI IA AB BD DH HG GC CE E二叉樹二叉樹2、樹的后根次序遍歷、樹的后根次序遍歷:對(duì)應(yīng)二叉樹中序遍歷對(duì)應(yīng)二叉樹中序遍歷 EFBGCHIDA樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同表示的中序遍歷結(jié)果相同當(dāng)樹非空時(shí)當(dāng)樹非空時(shí)依次

42、后根遍歷根的各棵子樹依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)I IA AC CB BD DH HG GF FE E樹后根遍歷樹后根遍歷 EFBGCHIDAF FI IA AB BD DH HG GC CE E二叉樹二叉樹四、森林的遍歷四、森林的遍歷先序遍歷先序遍歷中序遍歷中序遍歷對(duì)應(yīng)二叉樹先序遍歷對(duì)應(yīng)二叉樹先序遍歷 ABCDEFGHIKJ1、森林的先序遍歷、森林的先序遍歷當(dāng)森林非空時(shí)當(dāng)森林非空時(shí) 訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn) 先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林先序遍歷除第一棵樹外剩余的樹構(gòu)成的森林先序遍歷除第一棵樹外剩余的樹構(gòu)成的森

43、林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林先序遍歷森林先序遍歷 ABCDEFGHIKJ對(duì)應(yīng)二叉樹中序遍歷對(duì)應(yīng)二叉樹中序遍歷 BCEDAGFKIJH2、森林的中序遍歷、森林的中序遍歷當(dāng)森林非空時(shí)當(dāng)森林非空時(shí)中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn)中序遍歷除第一棵樹外剩余的樹構(gòu)成的森林中序遍歷除第一棵樹外剩余的樹構(gòu)成的森林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林中序遍歷森林中序遍歷BCEDAGFKIJH練習(xí)：練習(xí)：1、對(duì)以下兩棵二叉樹分別畫出它們的順序

44、存儲(chǔ)結(jié)構(gòu)、對(duì)以下兩棵二叉樹分別畫出它們的順序存儲(chǔ)結(jié)構(gòu)ABDEFCGIJKABDEFCIJABDEFCGH2、對(duì)右邊的樹，分別畫出、對(duì)右邊的樹，分別畫出孩子鏈表和孩子兄弟鏈表孩子鏈表和孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)3、分別畫出下列樹對(duì)應(yīng)的二叉樹、分別畫出下列樹對(duì)應(yīng)的二叉樹ABCABCABDEFCGHIJK4、將下列森林轉(zhuǎn)化為相應(yīng)的二叉樹、將下列森林轉(zhuǎn)化為相應(yīng)的二叉樹121415139101113245867ABD5、畫出下列二叉樹對(duì)應(yīng)的森林、畫出下列二叉樹對(duì)應(yīng)的森林ABDEFCGHIJKMJ路徑路徑:樹中一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支樹中一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支J路徑長度路徑長度(Path Leng

45、th):路徑上的分支數(shù)路徑上的分支數(shù)J樹的外部路徑長度樹的外部路徑長度:各葉結(jié)點(diǎn)各葉結(jié)點(diǎn)(外結(jié)點(diǎn)外結(jié)點(diǎn))到根結(jié)點(diǎn)的路到根結(jié)點(diǎn)的路 徑長度之和徑長度之和 (EPL)J樹的內(nèi)部路徑長度樹的內(nèi)部路徑長度:各非葉結(jié)點(diǎn)各非葉結(jié)點(diǎn)(內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn))到根結(jié)點(diǎn)的到根結(jié)點(diǎn)的 路徑長度之和路徑長度之和 (IPL)J樹的路徑長度樹的路徑長度:從根到每個(gè)葉子結(jié)點(diǎn)的路徑長度之和從根到每個(gè)葉子結(jié)點(diǎn)的路徑長度之和 PL = EPL + IPL6.5 哈夫曼樹哈夫曼樹及其應(yīng)用及其應(yīng)用一、最優(yōu)二叉樹一、最優(yōu)二叉樹(哈夫曼樹哈夫曼樹)12345678234567813*1+2*3 = 91*1+2*1+3*1+4*1 = 10EP

46、L =EPL =J樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度 (Weighted Path Length) 樹的各葉子結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長度樹的各葉子結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長度的乘積的和的乘積的和10niiilwWPLJ結(jié)點(diǎn)的權(quán)結(jié)點(diǎn)的權(quán):結(jié)點(diǎn)上被賦予的一定意義的實(shí)數(shù)結(jié)點(diǎn)上被賦予的一定意義的實(shí)數(shù)7*2+5*2+2*2+4*2=36帶權(quán)路徑長度帶權(quán)路徑長度達(dá)到最小達(dá)到最小abcd7524abcd4275abcd75244*1+2*2+7*3+5*3=447*1+5*2+2*3+4*3=35WPL=WPL=WPL=權(quán)值大的結(jié)點(diǎn)離根最近權(quán)值大的結(jié)點(diǎn)離根最近F : 7 5 2 4J哈夫曼樹哈夫曼樹(最優(yōu)二叉樹最優(yōu)二叉樹):帶權(quán)路徑長度帶權(quán)路徑長度WPL最小的二最小的二叉樹叉樹abcd7524二、哈夫曼樹的建立二、哈夫曼樹的建立1、編制一個(gè)將百分制轉(zhuǎn)換成五級(jí)分制的程序、編制一個(gè)將百分制轉(zhuǎn)換成五級(jí)分制的程序60?70?80?90?0.050.150.400.300.10NNNNYYYY80以上的數(shù)據(jù)需要以上的數(shù)據(jù)需要3次或次或3次以上比較才能