樹和二叉樹講義

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

2、個集合本身又是一棵樹其中每一個集合本身又是一棵樹, , 并且稱為根的并且稱為根的子樹子樹( (SubTree)SubTree)。樹的抽象數(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ù)對象數(shù)據(jù)對象 D: DD: D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R: R: 若若D D為空集，則稱為空樹；為空集，則稱為空樹； 若若D D僅含一個數(shù)據(jù)元素僅

3、含一個數(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,則存在則存在, ,則存在則存在DrootDroot的一個的一個劃分劃分D D1 1,D,D2 2,D,Dm m(m0),(m0),對任意對任意jk(1j,km)jk(1j,km)有有D Dj jDDk k=,=,且對任意的且對任意的i(1im),i(1im), 唯一存在數(shù)據(jù)元素唯一存在數(shù)據(jù)元素

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

5、HMIJ有有13個結(jié)點的樹個結(jié)點的樹其中：其中：A A是根；其余結(jié)點分成三個互不相交的子集，是根；其余結(jié)點分成三個互不相交的子集，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)廣義表廣義表樹的其它表示方式樹的其它表示方式ACGBDEFKLHMIJ

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

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

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

9、 n0 0, ,度度為為2 2的結(jié)點數(shù)為的結(jié)點數(shù)為n n2 2, , 則則n n0 0= = n n2 2+1+1。 推出推出 n n2 2 = = n n0 0 - 1 - 1 證明：若度為證明：若度為1 1的結(jié)點有的結(jié)點有 n n1 1 個，總結(jié)點個數(shù)為個，總結(jié)點個數(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 + n

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

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

12、叉樹中葉結(jié)點只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)完全二叉樹中葉結(jié)點只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)第二層。第二層。3.3.且當完全二叉樹的結(jié)點個數(shù)為偶數(shù)時，有且僅有一個且當完全二叉樹的結(jié)點個數(shù)為偶數(shù)時，有且僅有一個單分支結(jié)點，為奇數(shù)時無單分支結(jié)點。單分支結(jié)點，為奇數(shù)時無單分支結(jié)點。有關(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個結(jié)點，可以計算出個結(jié)點，可以計算出其葉結(jié)點的個數(shù)是（其葉結(jié)點的個數(shù)是（ ）。）。 練習練習2500兩邊同取對數(shù)得：兩邊同取對數(shù)得： h h1lo

13、g1log2 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ù)因此上式等價于是正整數(shù)因此上式等價于2 2h h1 1 n 2 n 1, i1, 則其雙親則其雙親PAREBT(i)PAREBT(i)是結(jié)點是結(jié)點 i/2i/2 。(2)(2) 如果如果2 2in,in,則結(jié)點則結(jié)點i i無左孩子無左孩子, ,否則其左孩子否則其左孩子LCHILD(i)LCHILD(i)是結(jié)點是結(jié)點2 2i i；(3) (3) 如果如

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

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

16、的相應(yīng)分量中。樹上的結(jié)點相對照，存儲在一維數(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個結(jié)點的單支樹，卻需要長度為個結(jié)點的單支樹，卻需要長度為2 2K K-1-1的一維數(shù)的一維數(shù)組。組。( (請思考那種情況是最壞的情況？為什么？請思考那種情況是最壞的情況？為什么？) ) 思思 考考左單支左單支123右單支右單支132datalChildrChild二叉鏈表lChild d

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

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

19、遍歷即如何按某條搜索路徑巡訪樹中每個結(jié)點訪樹中每個結(jié)點, ,使得每個結(jié)點均被使得每個結(jié)點均被訪問一次訪問一次, ,且僅被訪問一次。且僅被訪問一次。遍歷用途遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。切運算的基礎(chǔ)和核心。 ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD先左后右先左后右6.3.1 6.3.1 遍歷二叉樹遍歷二叉樹先序遍歷二叉樹算法的定義：先序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；若二叉樹為空，則空操作；否則否則訪問根結(jié)點訪問根結(jié)點 (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é)點訪問根結(jié)點 (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é)點訪問根結(jié)點 (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é)點值的順序必須對應(yīng)二叉樹結(jié)點先序遍歷的輸入結(jié)點值的順序必須對應(yīng)二叉樹結(jié)點先序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點的值以結(jié)束遞歸結(jié)點的值以結(jié)束遞歸, , 此值在此值在RefValueRefValue中。例如用中。例如用“”或用或用“-1”-1”表示字符序列或正整數(shù)序列空結(jié)點。表示字符序列或正整數(shù)序列空結(jié)點。按先序建立二叉樹按先序建立二叉樹(遞歸算法遞歸算法)ABCDEGFA B C D E G F 如圖所示的二叉樹的先序遍歷順序為如圖所示的二叉樹的先序遍歷順序為V27.2 7.2 圖的存儲結(jié)構(gòu)圖的存

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

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

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

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

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

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

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

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

32、.2 圖的存儲結(jié)構(gòu)圖的存儲結(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 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)typedef struct PTNode TElemType data ； int parent ；PTNode;1.1.樹的雙親表示法樹的雙親表示法#define MAX_TREE_SIZ

33、E 100typedef struct PTNode nodes MAX_TREE_SIZE； int n；PTree；PARENT(T,X)PARENT(T,X)操作可以在常量時間內(nèi)實現(xiàn)，反復調(diào)用，操作可以在常量時間內(nèi)實現(xiàn)，反復調(diào)用，直到遇到無雙親的結(jié)點時，便找到了樹的根。直到遇到無雙親的結(jié)點時，便找到了樹的根。 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個空鏈域個空鏈域 第一種結(jié)點結(jié)構(gòu)第一種結(jié)點結(jié)構(gòu) 等數(shù)量的鏈域等數(shù)量的鏈域 (d為樹的度為樹的度) childd . child2 child1 data 第二種結(jié)點結(jié)構(gòu)第二種結(jié)點結(jié)構(gòu) 不同數(shù)量的鏈域不同數(shù)量的鏈域 childd . child2child1degree data 若采

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

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

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

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

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

40、去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷森林的遍歷森林進行中序遍歷的序列為森林進行中序遍歷的序列為 B C D A F E H J I GB C D A F E H J I G森林的中序遍歷即為其對應(yīng)的二叉樹的中序遍歷。森林的中序遍歷即為其對應(yīng)的二叉樹的中序遍歷。BADCBACDHGIJJHGIEFEF帶權(quán)路徑長度帶權(quán)路徑長度 (Weighted Path Length, WPL)二叉樹的帶權(quán)二叉樹的帶權(quán) (外部外部) 路徑長度是樹的各葉結(jié)點所帶路徑長度是樹的各葉結(jié)點所帶的權(quán)值的權(quán)值 wi 與該結(jié)點到根的路徑長度與該結(jié)點到根的路徑長度 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)路徑長度最小，）樹的帶權(quán)路徑長度最小， 可以驗證，它恰為哈夫曼樹。可以驗證，它恰為哈夫曼樹。abcd7ab524cab4d

42、2ab75a7ab5bcd24 (a) (b) (c) 赫夫曼樹赫夫曼樹n帶權(quán)路徑長度達到最小的二叉樹即為赫夫曼樹。帶權(quán)路徑長度達到最小的二叉樹即為赫夫曼樹。n在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。(1) (1) 由給定的由給定的n n個權(quán)值個權(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 只有一只有一 個帶權(quán)值個帶權(quán)值 w w

43、i i 的根結(jié)點的根結(jié)點, , 其左、右其左、右子樹均為空。子樹均為空。 赫夫曼赫夫曼算法算法 在在 F F 中選取兩棵根結(jié)點的權(quán)值最小的二叉樹中選取兩棵根結(jié)點的權(quán)值最小的二叉樹, , 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。(2) (2) 重復以下步驟重復以下步驟, , 直到直到 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è)計二進制的前綴編碼，若約定左可以利用二叉樹來設(shè)計二進制的前綴編碼，若約定左分支表示字符分支表示字符00，若約定右分支表示字符，若約定右分支表示字符11：可得A、B、C、D的二進制前綴編碼A1ab0BCD0101A（0）B（10）C（110）D（111） 6.6.6.26.2 赫夫曼編碼赫夫曼編碼const int n = 20;/葉結(jié)點數(shù)葉結(jié)點數(shù)const int m = 2*n - -1;/結(jié)點數(shù)結(jié)點數(shù) typedef struct float weight; int parent, leftChild, rightChild; HTNode; typedef HTNode HuffmanTreem;赫夫曼樹