樹和二叉樹講義

1、第六章第六章 樹和二叉樹樹和二叉樹6.1 樹的概念及術(shù)語樹的概念及術(shù)語6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用樹是樹是n(n0)n(n0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。 在任意一棵非空樹中：在任意一棵非空樹中： (1) (1) 有且僅有一個(gè)特定的稱為根有且僅有一個(gè)特定的稱為根( (Root)Root)的結(jié)點(diǎn)；的結(jié)點(diǎn)； (2) (2) 當(dāng)當(dāng) n1n1時(shí)時(shí), , 其余結(jié)點(diǎn)可分為其余結(jié)點(diǎn)可分為m(m0)m(m0)個(gè)互不相個(gè)互不相交的有限集交的有限集T T1 1,T,T2 2, ,T,Tm m, , 其中

2、每一個(gè)集合本身又是一棵樹其中每一個(gè)集合本身又是一棵樹, , 并且稱為根的并且稱為根的子樹子樹( (SubTreeSubTree) )。樹的抽象數(shù)據(jù)類型定義如下：樹的抽象數(shù)據(jù)類型定義如下：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R: R: 若若D D為空集，則稱為空樹；為空集，則稱為空樹；6.1 6.1 樹的概念及術(shù)語樹的概念及術(shù)語樹的抽象數(shù)據(jù)類型定義如下：樹的抽象數(shù)據(jù)類型定義如下：ADT TreeADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D: DD: D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R: R: 若若D D為空集，則稱為空樹；為空集，則稱為空樹； 若若D D僅含一個(gè)數(shù)據(jù)

3、元素僅含一個(gè)數(shù)據(jù)元素, ,則則R R為空集為空集, ,否則否則R=H,HR=H,H是如下二是如下二元關(guān)系元關(guān)系: :(1) (1) 在在D D中存在中存在唯一的唯一的稱為根的數(shù)據(jù)元素稱為根的數(shù)據(jù)元素rootroot, ,它在關(guān)系它在關(guān)系H H下下無前驅(qū)無前驅(qū); ;(2) (2) 若若D-root,D-root,則存在則存在, ,則存在則存在D Drootroot的一個(gè)的一個(gè)劃分劃分D D1 1,D,D2 2, , ,D Dm m(m(m0),0),對(duì)任意對(duì)任意jk(1j,km)jk(1j,km)有有D Dj jDDk k=,=,且對(duì)任意的且對(duì)任意的i(1im),i(1im), 唯一存在數(shù)據(jù)元素

4、唯一存在數(shù)據(jù)元素X Xi iDDi i, ,有有 H;H;(3) (3) 對(duì)應(yīng)于對(duì)應(yīng)于D-rootD-root的劃分的劃分, ,H-H-,有唯一的一個(gè)劃分有唯一的一個(gè)劃分H H1 1,H,H2 2, ,H Hm m(m(m0),0),對(duì)任意對(duì)任意jk(1j,km)jk(1j,km)有有H Hj jHHk k=,=,且對(duì)任意且對(duì)任意i(1im), i(1im), H Hi i是是D Di i上的二元關(guān)系，上的二元關(guān)系， ( ( D Di i, H, Hi i)是一棵符合本定是一棵符合本定義的樹義的樹, ,稱為根稱為根rootroot的子樹。的子樹。例如例如A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹ACGBD

5、EFKLHMIJ有有13個(gè)結(jié)點(diǎn)的樹個(gè)結(jié)點(diǎn)的樹其中：其中：A A是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T T1 1=B,E,F,K,L=B,E,F,K,L； T T2 2=C,G=C,G； T T3 3=D,H,I,J,M,=D,H,I,J,M,T T1 1,T,T2 2,T,T3 3都是根都是根A A的子樹，且本身也是一棵樹。的子樹，且本身也是一棵樹。AJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)廣義表廣義表樹的其它表示方式樹的其它表示方式ACGBDEFKL

6、HMIJ 樹的結(jié)構(gòu)定義是一個(gè)遞歸的定義樹的結(jié)構(gòu)定義是一個(gè)遞歸的定義, ,即在即在樹的定義中又用到樹的概念樹的定義中又用到樹的概念, ,它道出它道出了樹的固有特性了樹的固有特性。 結(jié)結(jié) 論論樹的基本術(shù)語樹的基本術(shù)語1層2層4層3層height= 4ACGBDEFKLHMIJ 二叉樹二叉樹( (Binary Tree)Binary Tree)是一種樹型結(jié)構(gòu)是一種樹型結(jié)構(gòu), , 特點(diǎn)是每個(gè)特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹結(jié)點(diǎn)至多只有二棵子樹, ,并且二叉樹為有序樹。并且二叉樹為有序樹。 二叉樹的五種基本形態(tài)如下二叉樹的五種基本形態(tài)如下: :6.6.2 2 二叉樹二叉樹(a)(b)(c)(d)(e)6.

7、2.1 6.2.1 二叉樹的定義二叉樹的定義性質(zhì)性質(zhì)1 1 在二叉樹的第在二叉樹的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (i1)i1)。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2 2，故在第，故在第i i層上的層上的最最大結(jié)點(diǎn)數(shù)為第大結(jié)點(diǎn)數(shù)為第i-1i-1層上的最大結(jié)點(diǎn)數(shù)的層上的最大結(jié)點(diǎn)數(shù)的2 2倍，倍，即即2 2* *2 2i i2 2= = 2 2i-1i-1。歸納法證明：當(dāng)歸納法證明：當(dāng)i=1i=1時(shí)，只有根結(jié)點(diǎn)，時(shí)，只有根結(jié)點(diǎn)，2 2i-1i-1=2=20 0=1=1。假設(shè)對(duì)所有假設(shè)對(duì)所有j j，ijij 1 1，命題成立，即第命題成立，即第

8、j j層上至多有層上至多有2 2j-1j-1 個(gè)個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)。由歸納假設(shè)第由歸納假設(shè)第i-1i-1層上至多有層上至多有2 2i i2 2個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)2 2 深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (k1)k1)。證明：由性質(zhì)證明：由性質(zhì)1 1可見，深度為可見，深度為k k的二叉樹的最大結(jié)點(diǎn)數(shù)為的二叉樹的最大結(jié)點(diǎn)數(shù)為 kii11220 + 21 + + 2k-1 = 2k - -1kii1(層上的最大結(jié)點(diǎn)數(shù)）第性質(zhì)性質(zhì)3 3 對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹T,T,如果其終端結(jié)點(diǎn)數(shù)為如果其終端結(jié)點(diǎn)

9、數(shù)為n n0 0, ,度度為為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n2 2, , 則則n n0 0= = n n2 2+1+1。 推出推出 n n2 2 = = n n0 0 - 1 - 1 證明：若度為證明：若度為1 1的結(jié)點(diǎn)有的結(jié)點(diǎn)有 n n1 1 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n n，分，分支總數(shù)為支總數(shù)為 B B，則根據(jù)二叉樹的定義，則根據(jù)二叉樹的定義， n = nn = n0 0 + n + n1 1 + n + n2 2 B = 2n B = 2n2 2 + n + n1 1 = n - 1= n - 1因此，有因此，有 2 2n n2 2 + n + n1 1 = n= n0 0

10、+ n + n1 1 + n + n2 2 - 1 - 1 或或 n n0 0 = = n n2 2 + 1 + 1 1 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹621754389 10 1113 14 1512滿二叉樹滿二叉樹1. 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹621754389 1

11、0 1113 14 1512滿二叉樹滿二叉樹若設(shè)二叉樹的高度為若設(shè)二叉樹的高度為h h，則共有則共有h h層。除第層。除第 h h 層外，其它層外，其它各層各層 (1 (1 h-1 h-1) ) 的結(jié)點(diǎn)數(shù)都達(dá)到最大值，的結(jié)點(diǎn)數(shù)都達(dá)到最大值，第第 h h 層從右層從右向左連續(xù)缺若干結(jié)點(diǎn)向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。，這就是完全二叉樹。6217543891011122. 完全二叉樹完全二叉樹 (Complete Binary Tree)62175438910 111.1.深度為深度為h h的完全二叉樹其結(jié)點(diǎn)個(gè)數(shù)的取值范圍的完全二叉樹其結(jié)點(diǎn)個(gè)數(shù)的取值范圍2h-1h-1 2h h-12.2.完

12、全二叉樹中葉結(jié)點(diǎn)只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)完全二叉樹中葉結(jié)點(diǎn)只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)第二層。第二層。3.3.且當(dāng)完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，有且僅有一個(gè)且當(dāng)完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，有且僅有一個(gè)單分支結(jié)點(diǎn)，為奇數(shù)時(shí)無單分支結(jié)點(diǎn)。單分支結(jié)點(diǎn)，為奇數(shù)時(shí)無單分支結(jié)點(diǎn)。有關(guān)完全二叉樹的重要結(jié)論有關(guān)完全二叉樹的重要結(jié)論n n0 0=(n=(n奇數(shù)奇數(shù)+1)/2+1)/2n n0 0=n=n偶數(shù)偶數(shù)/2/2一棵完全二叉樹有一棵完全二叉樹有50005000個(gè)結(jié)點(diǎn)，可以計(jì)算出個(gè)結(jié)點(diǎn)，可以計(jì)算出其葉結(jié)點(diǎn)的個(gè)數(shù)是（其葉結(jié)點(diǎn)的個(gè)數(shù)是（ ）。）。 練習(xí)練習(xí)2500兩邊同取對(duì)數(shù)得：兩邊同取對(duì)數(shù)得： h h1

13、log1log2 2n n h h證明：設(shè)完全二叉樹的深度為證明：設(shè)完全二叉樹的深度為 h h，則根據(jù)性質(zhì)則根據(jù)性質(zhì)2 2和完全二和完全二叉樹的定義叉樹的定義2 2h h1 1 - 1 n - 1 n 2 2h h - 1- 1由于由于n n是正整數(shù)因此上式等價(jià)于是正整數(shù)因此上式等價(jià)于2 2h h1 1 n 2 n 1, i1, 則其雙親則其雙親PAREBT(iPAREBT(i) )是結(jié)點(diǎn)是結(jié)點(diǎn) i/2i/2 。(2)(2) 如果如果2 2in,in,則結(jié)點(diǎn)則結(jié)點(diǎn)i i無左孩子無左孩子, ,否則其左孩子否則其左孩子LCHILD(i)LCHILD(i)是結(jié)點(diǎn)是結(jié)點(diǎn)2 2i i；(3) (3) 如

14、果如果2 2i+1n,i+1n,則結(jié)點(diǎn)則結(jié)點(diǎn)i i無右孩子無右孩子, ,否則其右孩子否則其右孩子RCHILD(i)RCHILD(i)是結(jié)點(diǎn)是結(jié)點(diǎn)2 2i+1i+1。 182345679 101.1.順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) # # define MAX-TREE-SIZE 100define MAX-TREE-SIZE 100 typedeftypedef TElemTypeTElemType SqBiTreeMAX_TREE_SIZESqBiTreeMAX_TREE_SIZE; SqBiTreeSqBiTree btbt; ; 用一組地址連續(xù)的存儲(chǔ)單元依次自上而下，自左用一組地址連續(xù)的存儲(chǔ)單

15、元依次自上而下，自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為上編號(hào)為 i i 的結(jié)點(diǎn)元素存儲(chǔ)在如上定義的一維數(shù)組的結(jié)點(diǎn)元素存儲(chǔ)在如上定義的一維數(shù)組中下標(biāo)為中下標(biāo)為 i-1 i-1 的分量中。的分量中。 6.2.3 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)完全二叉樹的順序存儲(chǔ)表示圖解完全二叉樹的順序存儲(chǔ)表示圖解完全二叉樹完全二叉樹1 2 3 4 5 6 7 8 91012489 1056730217365849 對(duì)于一般二叉樹，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉對(duì)于一般二叉樹，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)

16、分量中。樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。9123654789 10一般二叉樹一般二叉樹1 2 3 4 0 5 6 7 8 0 0 0 0 9 10 3 1310 2 1 0 11 9 8 7 6 5 4 14 12 在最壞的情況下，一棵深度為在最壞的情況下，一棵深度為k k且只有且只有k k個(gè)結(jié)點(diǎn)的單支樹，卻需要長(zhǎng)度為個(gè)結(jié)點(diǎn)的單支樹，卻需要長(zhǎng)度為2 2K K-1-1的一維數(shù)的一維數(shù)組。組。( (請(qǐng)思考那種情況是最壞的情況？為什么？請(qǐng)思考那種情況是最壞的情況？為什么？) ) 思思 考考左單支左單支123右單支右單支132datalChildrChild二叉鏈表lChild data

17、 rChild含兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)含兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)lChild data parent rChild含三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)含三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)parentdatalChildrChild三叉鏈表typedef char TreeData;/結(jié)點(diǎn)數(shù)據(jù)類型結(jié)點(diǎn)數(shù)據(jù)類型typedef struct node /結(jié)點(diǎn)定義結(jié)點(diǎn)定義 TreeData data; struct node * leftChild, * rightchild; BinTreeNode;typedef BinTreeNode * BinTree; /根指針根指針 二叉鏈表的定義二叉鏈表的定義單支樹的二叉鏈表（單支樹的二

18、叉鏈表（a a） BADCABCD 二叉鏈表二叉鏈表( (b)b)BAEDFCGABEDFGC觀察可得，n個(gè)結(jié)點(diǎn)的二叉鏈表具有n+1個(gè)空鏈域證明：對(duì)于具有證明：對(duì)于具有n n個(gè)結(jié)點(diǎn)的二叉鏈表共有個(gè)結(jié)點(diǎn)的二叉鏈表共有2n2n個(gè)鏈域，個(gè)鏈域，但僅有但僅有n-1n-1個(gè)非空鏈域。個(gè)非空鏈域。所以空鏈域數(shù)所以空鏈域數(shù)2n-2n-（n-1)n-1)性質(zhì)：含有性質(zhì)：含有n n個(gè)結(jié)點(diǎn)的二叉鏈表中有個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1n+1個(gè)空鏈域。個(gè)空鏈域。=n+1=n+1 重要性質(zhì)的證明重要性質(zhì)的證明6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷定義遍歷定義所謂遍歷即如何按某條搜索路徑巡所謂遍歷即

19、如何按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)訪樹中每個(gè)結(jié)點(diǎn), ,使得每個(gè)結(jié)點(diǎn)均被使得每個(gè)結(jié)點(diǎn)均被訪問一次訪問一次, ,且僅被訪問一次。且僅被訪問一次。遍歷用途遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。切運(yùn)算的基礎(chǔ)和核心。 ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD先左后右先左后右6.3.1 6.3.1 遍歷二叉樹遍歷二叉樹先序遍歷二叉樹算法的定義：先序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作；若二叉樹為空，則空操作； 否則否則訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (D)(D)；

20、先序遍歷左子樹先序遍歷左子樹 (L)(L)；先序遍歷右子樹先序遍歷右子樹 (R)(R)。先序遍歷先序遍歷 (Preorder Traversal)遍歷結(jié)果遍歷結(jié)果a+f*eb-/c-d先序遍歷二叉樹的遞歸算法先序遍歷二叉樹的遞歸算法void PreOrder( BinTreeNode *T ) if ( T != NULL ) Visit( T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); / PreOrder中序遍歷二叉樹算法的定義：中序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作；若二叉樹為空，則空操作； 否則否則

21、中序遍歷左子樹中序遍歷左子樹 (L)(L)；訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (D)(D)；中序遍歷右子樹中序遍歷右子樹 (R)(R)。中序遍歷中序遍歷 (Inorder Traversal)遍歷結(jié)果遍歷結(jié)果a+fbe*-/c-d中序遍歷二叉樹的遞歸算法中序遍歷二叉樹的遞歸算法void Inorder( BinTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); Visit( T-data); InOrder ( T-rightChild ); / InOrder后序遍歷二叉樹算法的定義：后序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作；若二叉樹

22、為空，則空操作； 否則否則后序遍歷左子樹后序遍歷左子樹 (L)(L)；后序遍歷右子樹后序遍歷右子樹 (R)(R)；訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (D)(D)。后序遍歷后序遍歷 (Postorder Traversal)遍歷結(jié)果遍歷結(jié)果a+fbe*-/c-d后序遍歷二叉樹的遞歸算法后序遍歷二叉樹的遞歸算法void Postorder( BinTreeNode *T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); Visit( T-data); / PostOrder二叉樹遍歷應(yīng)用二叉樹遍歷應(yīng)用n以遞歸方式

23、建立二叉樹。以遞歸方式建立二叉樹。n輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)先序遍歷的輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)先序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸結(jié)點(diǎn)的值以結(jié)束遞歸, , 此值在此值在RefValueRefValue中。例如用中。例如用“”或用或用“-1”-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。按先序建立二叉樹按先序建立二叉樹(遞歸算法遞歸算法)ABCDEGFA B C D E G F 如圖所示的二叉樹的先序遍歷順序?yàn)槿鐖D所示的二叉樹的先序遍歷順序?yàn)閂27.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)

24、圖的存儲(chǔ)結(jié)構(gòu)7.2.17.2.1 數(shù)組（鄰接矩陣）表示法數(shù)組（鄰接矩陣）表示法7.2.2 7.2.2 圖的鄰接表表示法圖的鄰接表表示法普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整棵樹。而遍歷整棵樹。例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H GB D C E A F H G，實(shí)際上，實(shí)際上已

25、將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！唯一后繼！可能是根、或最左（右）葉子可能是根、或最左（右）葉子6.3.2 6.3.2 線索二叉樹線索二叉樹兩種解決方法兩種解決方法增加兩個(gè)指針域：增加兩個(gè)指針域：fwdfwd和和bwdbwd；利用空鏈域（利用空鏈域（n+1n+1個(gè)空鏈域）個(gè)空鏈域）如何保存二叉樹遍歷過程中所得到如何保存二叉樹遍歷過程中所得到的前驅(qū)、后繼信息？的前驅(qū)、后繼信息？ 若結(jié)點(diǎn)有左子樹若結(jié)點(diǎn)有左子樹, ,則其則其leftChildleftChild域指示其左孩子域指示其左孩子, ,否否則令則令leftChildleftChild域

26、指示其前驅(qū)；域指示其前驅(qū)； 若結(jié)點(diǎn)有右子樹若結(jié)點(diǎn)有右子樹, ,則其則其rightChildrightChild域指示其右孩子域指示其右孩子, ,否否則令則令rightChildrightChild域指示其后繼。域指示其后繼。 為了避免混淆為了避免混淆, ,增加兩個(gè)標(biāo)志域增加兩個(gè)標(biāo)志域: :leftThreadleftThread和和rightThreadrightThread。為保存在遍歷中得到的為保存在遍歷中得到的動(dòng)態(tài)信息動(dòng)態(tài)信息, ,試作如下現(xiàn)定試作如下現(xiàn)定: :leftChildrightChildleftThreadrightThreaddata其中其中: : 0 leftChildl

27、eftChild 域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子 = 1 leftChildleftChild 域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū) 0 rightChildrightChild 域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子 = 1 rightChildrightChild 域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼leftThreadrightThread 以這種結(jié)點(diǎn)構(gòu)成的二叉樹鏈表作為二叉樹的存儲(chǔ)結(jié)以這種結(jié)點(diǎn)構(gòu)成的二叉樹鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)構(gòu), , 叫做叫做線索鏈表線索鏈表, ,其中指向結(jié)點(diǎn)其中指向結(jié)點(diǎn)前驅(qū)前驅(qū)和和后繼的指針后繼的指針, , 叫作叫作線索線索, , 加上線索的二叉樹稱之為加上線索的二叉

28、樹稱之為線索二叉樹線索二叉樹。中序線索二叉樹中序線索二叉樹BDAECBDAEC，如下圖所示：，如下圖所示： 對(duì)二叉樹以某種次序遍歷使其變成線索二對(duì)二叉樹以某種次序遍歷使其變成線索二叉樹的過程叫做叉樹的過程叫做線索化線索化. . 在線索樹中進(jìn)行遍歷時(shí)在線索樹中進(jìn)行遍歷時(shí), ,只要先找到序列中只要先找到序列中的第一個(gè)結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn), , 然后依次找結(jié)點(diǎn)后繼直至其后然后依次找結(jié)點(diǎn)后繼直至其后繼空時(shí)為止。繼空時(shí)為止。 后繼：結(jié)點(diǎn)標(biāo)志為后繼：結(jié)點(diǎn)標(biāo)志為1 1時(shí)，其右指針為其后繼；時(shí)，其右指針為其后繼；結(jié)點(diǎn)標(biāo)志為結(jié)點(diǎn)標(biāo)志為0 0時(shí)，其右子樹最左下結(jié)點(diǎn)為其時(shí)，其右子樹最左下結(jié)點(diǎn)為其后繼。后繼。abcde中

29、序線索二叉樹中序線索二叉樹 前驅(qū)：結(jié)點(diǎn)標(biāo)志為前驅(qū)：結(jié)點(diǎn)標(biāo)志為1 1時(shí)，其左指時(shí)，其左指針為其前驅(qū)；結(jié)點(diǎn)標(biāo)志為針為其前驅(qū)；結(jié)點(diǎn)標(biāo)志為0 0時(shí)，時(shí)，其左子樹最右下結(jié)點(diǎn)為其前驅(qū)。其左子樹最右下結(jié)點(diǎn)為其前驅(qū)。 由于線索化的實(shí)質(zhì)是將二叉樹鏈表中的空指針改由于線索化的實(shí)質(zhì)是將二叉樹鏈表中的空指針改為指向前驅(qū)或后繼的線索為指向前驅(qū)或后繼的線索, ,而前驅(qū)或后繼的信息只有而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到。因此在遍歷時(shí)才能得到。因此線索化的過程即為在遍歷的線索化的過程即為在遍歷的過程中修改空指針的過程。過程中修改空指針的過程。 為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系, ,

30、附設(shè)一附設(shè)一個(gè)指針個(gè)指針prepre始終指向剛剛訪問過的結(jié)點(diǎn)始終指向剛剛訪問過的結(jié)點(diǎn), ,若指針若指針p p指向當(dāng)指向當(dāng)前訪問過的結(jié)點(diǎn)前訪問過的結(jié)點(diǎn), ,則則prepre指向它的前驅(qū)。指向它的前驅(qū)。 線索化的實(shí)質(zhì)線索化的實(shí)質(zhì)StatusStatus InOrderThreading(InOrderThreading(BiThrTree&Thrt,BiThrTree T) ) /中序遍歷并線索化二叉樹，Thrt為頭結(jié)點(diǎn) if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW)；/建頭結(jié)點(diǎn) ThrtleftThread=lin

31、k； ThrtrightThread=Thread； ThrtrightChild=Thrt；/頭結(jié)點(diǎn)右指針回指 If(!T) ThrtleftChild=Thrt；/若二叉樹為空，則左指針也回指 Else ThrtleftChild=T; Pre=Thrt；/pre總是指向最后一個(gè)訪問過的結(jié)點(diǎn)，即其后要訪問結(jié)點(diǎn)的前驅(qū) InThreading(T)； /線索化的主過程 prerightChild=Thrt； prerightThread=Thread； ThrtrightThread=pre； /將最后一個(gè)結(jié)點(diǎn)線索化 return OK； 算法算法 6.6 中序線索二叉樹中序線索二叉樹V27.

32、2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)7.2.17.2.1 數(shù)組（鄰接矩陣）表示法數(shù)組（鄰接矩陣）表示法7.2.2 7.2.2 圖的鄰接表表示法圖的鄰接表表示法算法算法 2.2 順序有序表的合并順序有序表的合并6.4 6.4 樹和森林樹和森林1.1.樹的雙親表示法樹的雙親表示法2.2.孩子表示法孩子表示法( (多重鏈表多重鏈表) )3.3.孩子兄弟表示法孩子兄弟表示法6.4.16.4.1 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)typedef struct PTNode TElemType data ； int parent ；PTNode;1.1.樹的雙親表示法樹的雙親表示法#define MAX_TREE_

33、SIZE 100typedef struct PTNode nodes MAX_TREE_SIZE； int n；PTree；PARENT(T,X)PARENT(T,X)操作可以在常量時(shí)間內(nèi)實(shí)現(xiàn)，反復(fù)調(diào)用，操作可以在常量時(shí)間內(nèi)實(shí)現(xiàn)，反復(fù)調(diào)用，直到遇到無雙親的結(jié)點(diǎn)時(shí)，便找到了樹的根。直到遇到無雙親的結(jié)點(diǎn)時(shí)，便找到了樹的根。 BAGEIDHCFEDCBAHI440-1101654321078data parent樹的雙親表示法示例樹的雙親表示法示例typedef struct PTNode TElemType data ； int parent ；PTNode;樹的雙親表

34、示法形式說明如下：樹的雙親表示法形式說明如下：#define MAX_TREE_SIZE 100typedef struct PTNode nodes MAX_TREE_SIZE； int n；PTree；2.2.孩子表示法孩子表示法( (多重鏈表多重鏈表) )ABCDEFGBCDEFGAn(d-1)+1n(d-1)+1個(gè)空鏈域個(gè)空鏈域 第一種結(jié)點(diǎn)結(jié)構(gòu)第一種結(jié)點(diǎn)結(jié)構(gòu) 等數(shù)量的鏈域等數(shù)量的鏈域 (d為樹的度為樹的度) childd . child2 child1 data 第二種結(jié)點(diǎn)結(jié)構(gòu)第二種結(jié)點(diǎn)結(jié)構(gòu) 不同數(shù)量的鏈域不同數(shù)量的鏈域 childd . child2child1degree data

35、 若采用第二種結(jié)點(diǎn)格式，則多重鏈表中的結(jié)點(diǎn)是不若采用第二種結(jié)點(diǎn)格式，則多重鏈表中的結(jié)點(diǎn)是不同構(gòu)的，其中同構(gòu)的，其中dd為結(jié)點(diǎn)的度，為結(jié)點(diǎn)的度，degreedegree域的值同域的值同dd。 此時(shí)，雖能節(jié)約存儲(chǔ)空間，但操作不方便。此時(shí)，雖能節(jié)約存儲(chǔ)空間，但操作不方便。 孩子鏈表孩子鏈表G6F5E4D3C2B1A0123456ABCDEFG將每個(gè)結(jié)點(diǎn)將每個(gè)結(jié)點(diǎn)的孩子鏈在的孩子鏈在該結(jié)點(diǎn)之后該結(jié)點(diǎn)之后組成鏈表，組成鏈表，再將所有頭結(jié)點(diǎn)組再將所有頭結(jié)點(diǎn)組成一個(gè)線性表成一個(gè)線性表。結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)nextSiblingdata firstChildABCDEFGn+1n+1個(gè)空鏈域個(gè)空鏈域ABECFDG

36、3.3.孩子兄弟表示法孩子兄弟表示法typedef char TreeData;typedef struct node TreeData data; struct node *firstChild, *nextSibling; TreeNode;typedef TreeNode * Tree;用左孩子用左孩子- -右兄弟表示實(shí)現(xiàn)的樹定義右兄弟表示實(shí)現(xiàn)的樹定義6.4.26.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換BACDEFJHGI森林的二叉樹表示3 棵樹的森林BADCEFHGIJT1T2T3BACDEFJHGI各棵樹的二叉樹表示T1T2T3樹的先根樹的先根遍歷遍歷n當(dāng)樹非空時(shí)當(dāng)樹非空時(shí)u

37、訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)u 依次先根遍歷根的各棵依次先根遍歷根的各棵u 子樹子樹 n樹先根遍歷樹先根遍歷 A B E F C D GA B E F C D GABCEDGFABCDEFGn對(duì)應(yīng)二叉樹先根遍歷對(duì)應(yīng)二叉樹先根遍歷 A B E F C D GA B E F C D Gn樹的先根遍歷同其對(duì)應(yīng)二叉樹的先根遍樹的先根遍歷同其對(duì)應(yīng)二叉樹的先根遍歷歷n當(dāng)樹非空時(shí)當(dāng)樹非空時(shí)u 依次后根遍歷根的各棵依次后根遍歷根的各棵u 子樹子樹u訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) n樹后根遍歷樹后根遍歷 E F B C G D AE F B C G D AABCEDGF樹的后根遍歷樹的后根遍歷n對(duì)應(yīng)二叉樹中序遍歷對(duì)應(yīng)二叉樹中序遍

38、歷 E F B C G D AE F B C G D An樹的后根遍歷同其對(duì)應(yīng)二叉樹的中序遍樹的后根遍歷同其對(duì)應(yīng)二叉樹的中序遍歷歷ABCDEFG按照森林和樹相互遞歸的定義，按照森林和樹相互遞歸的定義，我們可以推出森林的兩種遍歷方法：我們可以推出森林的兩種遍歷方法：一、先序遍歷森林一、先序遍歷森林 若森林非空，則可按下述規(guī)則遍歷之：若森林非空，則可按下述規(guī)則遍歷之：(1) (1) 訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn); ;(2) (2) 先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；(3) (3) 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。先序遍歷除去

39、第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷森林的遍歷森林進(jìn)行先序遍歷的序列為：森林進(jìn)行先序遍歷的序列為：A B C D E F G H I J A B C D E F G H I J 森林的先序遍歷即為其對(duì)應(yīng)的二叉樹的先序遍歷。森林的先序遍歷即為其對(duì)應(yīng)的二叉樹的先序遍歷。BADCBACDHGIJJHGIEFEF二、中序遍歷森林二、中序遍歷森林 若森林非空，則可按下述規(guī)則遍歷之：若森林非空，則可按下述規(guī)則遍歷之： (1) (1) 中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林； (2) (2) 訪問第一棵樹的根結(jié)點(diǎn)；訪問第一棵樹的根結(jié)點(diǎn)； (3) (3) 中序

40、遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷森林的遍歷森林進(jìn)行中序遍歷的序列為森林進(jìn)行中序遍歷的序列為 B C D A F E H J I GB C D A F E H J I G森林的中序遍歷即為其對(duì)應(yīng)的二叉樹的中序遍歷。森林的中序遍歷即為其對(duì)應(yīng)的二叉樹的中序遍歷。BADCBACDHGIJJHGIEFEF帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度 (Weighted Path Length, WPL)二叉樹的帶權(quán)二叉樹的帶權(quán) (外部外部) 路徑長(zhǎng)度是樹的各葉結(jié)點(diǎn)所帶路徑長(zhǎng)度是樹的各葉結(jié)點(diǎn)所帶的權(quán)值的權(quán)值 wi 與該結(jié)點(diǎn)到根的路徑長(zhǎng)度與該結(jié)點(diǎn)到根的路徑長(zhǎng)度 li

41、 的乘積的和。的乘積的和。10niiilwWPL6.6.6 6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用 (a) WPL=7 (a) WPL=72 + 52 + 52 + 22 + 22 + 42 + 42 =362 =36 (b) WPL=7(b) WPL=73 + 53 + 53 + 23 + 21 + 41 + 42 =462 =46 (c) WPL=7 (c) WPL=71 + 51 + 52 + 22 + 23 + 43 + 43 =353 =35 其中（其中（c c）樹的帶權(quán)路徑長(zhǎng)度最小，）樹的帶權(quán)路徑長(zhǎng)度最小， 可以驗(yàn)證，它恰為哈夫曼樹。可以驗(yàn)證，它恰為哈夫曼樹。abcd7ab524ca

42、b4d2ab75a7ab5bcd24 (a) (b) (c) 赫夫曼樹赫夫曼樹n帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹即為赫夫曼樹。帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹即為赫夫曼樹。n在哈夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近在哈夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。(1) (1) 由給定的由給定的n n個(gè)權(quán)值個(gè)權(quán)值 ww0 0, w, w1 1, w, w2 2, , , w, wn-1n-1 ，構(gòu)造構(gòu)造具有具有n n棵二叉樹的森林棵二叉樹的森林 F= TF= T0 0, T, T1 1, T, T2 2, , , T, Tn-1 n-1 ，其中，其中每棵二叉樹每棵二叉樹 T Ti i 只有一只有一 個(gè)帶權(quán)值個(gè)帶權(quán)值 w

43、wi i 的根結(jié)點(diǎn)的根結(jié)點(diǎn), , 其左、右其左、右子樹均為空。子樹均為空。 赫夫曼赫夫曼算法算法 在在 F F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹, , 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。(2) (2) 重復(fù)以下步驟重復(fù)以下步驟, , 直到直到 F F 中僅剩下一棵樹為止。中僅剩下一棵樹為止。赫夫曼算法的具體步驟赫夫曼算法的具體步驟 在在 F F 中刪去這兩棵二叉樹。中刪去這兩棵二叉樹。 把新的二叉樹加入把新

44、的二叉樹加入 F F。F : 7 5 2 47524初始F : 7 5 6合并2 475246F : 7 11 1175246合并5 6F : 18 合并7 11527461118赫夫曼樹的構(gòu)造過程舉例赫夫曼樹的構(gòu)造過程舉例可以利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼，若約定左可以利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼，若約定左分支表示字符分支表示字符00，若約定右分支表示字符，若約定右分支表示字符11：可得A、B、C、D的二進(jìn)制前綴編碼A1ab0BCD0101A（0）B（10）C（110）D（111） 6.6.6.26.2 赫夫曼編碼赫夫曼編碼const int n = 20;/葉結(jié)點(diǎn)數(shù)葉結(jié)點(diǎn)數(shù)const int m = 2*n - -1;/結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) typedef struct float weight; int parent, leftChild, rightChild; HTNode; typedef HTNode HuffmanTreem;赫夫曼