樹和二叉樹講義

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

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

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

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

5、EFKLHMIJ有有13個結點的樹個結點的樹其中：其中：A A是根；其余結點分成三個互不相交的子集，是根；其余結點分成三個互不相交的子集，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 樹的結構定義是一個遞歸的定義樹的結構定義是一個遞歸的定義, ,即在即在樹的定義中又用到樹的概念樹的定義中又用到樹的概念, ,它道出它道出了樹的固有特性了樹的固有特性。 結結 論論樹的基本術語樹的基本術語1層2層4層3層height= 4ACGBDEFKLHMIJ 二叉樹二叉樹( (Binary Tree)Binary Tree)是一種樹型結構是一種樹型結構, , 特點是每個特點是每個結點至多只有二棵子樹結點至多只有二棵子樹, ,并且二叉樹為有序樹。并且二叉樹為有序樹。 二叉樹的五種基本形態(tài)如下二叉樹的五種基本形態(tài)如下: :6.6.2 2 二叉樹二叉樹(a)(b)(c)(d)(e)6.

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

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

9、數(shù)為n n0 0, ,度度為為2 2的結點數(shù)為的結點數(shù)為n n2 2, , 則則n n0 0= = n n2 2+1+1。 推出推出 n n2 2 = = n n0 0 - 1 - 1 證明：若度為證明：若度為1 1的結點有的結點有 n n1 1 個，總結點個數(shù)為個，總結點個數(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個結點的二叉樹稱為滿二叉樹。個結點的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹621754389 10 1113 14 1512滿二叉樹滿二叉樹1. 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k -1個結點的二叉樹稱為滿二叉樹。個結點的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹621754389 1

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

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

13、log1log2 2n n h h證明：設完全二叉樹的深度為證明：設完全二叉樹的深度為 h h，則根據(jù)性質則根據(jù)性質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(iPAREBT(i) )是結點是結點 i/2i/2 。(2)(2) 如果如果2 2in,in,則結點則結點i i無左孩子無左孩子, ,否則其左孩子否則其左孩子LCHILD(i)LCHILD(i)是結點是結點2 2i i；(3) (3) 如

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

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

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

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

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

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

20、先序遍歷左子樹先序遍歷左子樹 (L)(L)；先序遍歷右子樹先序遍歷右子樹 (R)(R)。先序遍歷先序遍歷 (Preorder Traversal)遍歷結果遍歷結果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)；訪問根結點訪問根結點 (D)(D)；中序遍歷右子樹中序遍歷右子樹 (R)(R)。中序遍歷中序遍歷 (Inorder Traversal)遍歷結果遍歷結果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)；訪問根結點訪問根結點 (D)(D)。后序遍歷后序遍歷 (Postorder Traversal)遍歷結果遍歷結果a+fbe*-/c-d后序遍歷二叉樹的遞歸算法后序遍歷二叉樹的遞歸算法void Postorder( BinTreeNode *T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); Visit( T-data); / PostOrder二叉樹遍歷應用二叉樹遍歷應用n以遞歸方式

23、建立二叉樹。以遞歸方式建立二叉樹。n輸入結點值的順序必須對應二叉樹結點先序遍歷的輸入結點值的順序必須對應二叉樹結點先序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結點的值以結束遞歸結點的值以結束遞歸, , 此值在此值在RefValueRefValue中。例如用中。例如用“”或用或用“-1”-1”表示字符序列或正整數(shù)序列空結點。表示字符序列或正整數(shù)序列空結點。按先序建立二叉樹按先序建立二叉樹(遞歸算法遞歸算法)ABCDEGFA B C D E G F 如圖所示的二叉樹的先序遍歷順序為如圖所示的二叉樹的先序遍歷順序為V27.2 7.2 圖的存儲結構

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

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

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

27、eftChild 域指示結點的左孩子域指示結點的左孩子 = 1 leftChildleftChild 域指示結點的前驅域指示結點的前驅 0 rightChildrightChild 域指示結點的右孩子域指示結點的右孩子 = 1 rightChildrightChild 域指示結點的后繼域指示結點的后繼leftThreadrightThread 以這種結點構成的二叉樹鏈表作為二叉樹的存儲結以這種結點構成的二叉樹鏈表作為二叉樹的存儲結構構, , 叫做叫做線索鏈表線索鏈表, ,其中指向結點其中指向結點前驅前驅和和后繼的指針后繼的指針, , 叫作叫作線索線索, , 加上線索的二叉樹稱之為加上線索的二叉

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

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

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

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

32、2 7.2 圖的存儲結構圖的存儲結構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 樹的存儲結構樹的存儲結構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)操作可以在常量時間內實現(xiàn)，反復調用，操作可以在常量時間內實現(xiàn)，反復調用，直到遇到無雙親的結點時，便找到了樹的根。直到遇到無雙親的結點時，便找到了樹的根。 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個空鏈域個空鏈域 第一種結點結構第一種結點結構 等數(shù)量的鏈域等數(shù)量的鏈域 (d為樹的度為樹的度) childd . child2 child1 data 第二種結點結構第二種結點結構 不同數(shù)量的鏈域不同數(shù)量的鏈域 childd . child2child1degree data

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

36、3.3.孩子兄弟表示法孩子兄弟表示法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 森林與二叉樹的轉換森林與二叉樹的轉換BACDEFJHGI森林的二叉樹表示3 棵樹的森林BADCEFHGIJT1T2T3BACDEFJHGI各棵樹的二叉樹表示T1T2T3樹的先根樹的先根遍歷遍歷n當樹非空時當樹非空時u

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

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

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

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

41、 的乘積的和。的乘積的和。10niiilwWPL6.6.6 6 赫夫曼樹及其應用赫夫曼樹及其應用 (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）樹的帶權路徑長度最小，）樹的帶權路徑長度最小， 可以驗證，它恰為哈夫曼樹?？梢则炞C，它恰為哈夫曼樹。abcd7ab524ca

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

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