樹(shù)和二叉樹(shù)講義

1、第六章第六章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.1 樹(shù)的概念及術(shù)語(yǔ)樹(shù)的概念及術(shù)語(yǔ)6.2 二叉樹(shù)二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林6.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用樹(shù)是樹(shù)是n(n0)n(n0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。 在任意一棵非空樹(shù)中：在任意一棵非空樹(shù)中： (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è)集合本身又是一棵樹(shù)其中每一個(gè)集合本身又是一棵樹(shù), , 并且稱為根的并且稱為根的子樹(shù)子樹(shù)( (SubTreeSubTree) )。樹(shù)的抽象數(shù)據(jù)類型定義如下：樹(shù)的抽象數(shù)據(jù)類型定義如下：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R: R: 若若D D為空集，則稱為空樹(shù)；為空集，則稱為空樹(shù)；6.1 6.1 樹(shù)的概念及術(shù)語(yǔ)樹(shù)的概念及術(shù)語(yǔ)樹(shù)的抽象數(shù)據(jù)類型定義如下：樹(shù)的抽象數(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為空集，則稱為空樹(shù)；為空集，則稱為空樹(shù)； 若若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下下無(wú)前驅(qū)無(wú)前驅(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)是一棵符合本定是一棵符合本定義的樹(shù)義的樹(shù), ,稱為根稱為根rootroot的子樹(shù)。的子樹(shù)。例如例如A只有根結(jié)點(diǎn)的樹(shù)只有根結(jié)點(diǎn)的樹(shù)ACGBD

5、EFKLHMIJ有有13個(gè)結(jié)點(diǎn)的樹(shù)個(gè)結(jié)點(diǎn)的樹(shù)其中：其中：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的子樹(shù)，且本身也是一棵樹(shù)。的子樹(shù)，且本身也是一棵樹(shù)。AJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)廣義表廣義表樹(shù)的其它表示方式樹(shù)的其它表示方式ACGBDEFKL

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

7、2.1 6.2.1 二叉樹(shù)的定義二叉樹(shù)的定義性質(zhì)性質(zhì)1 1 在二叉樹(shù)的第在二叉樹(shù)的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (i1)i1)。由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度至多為由于二叉樹(shù)的每個(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 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)性質(zhì)性質(zhì)2 2 深度為深度為k k的二叉樹(shù)至多有的二叉樹(shù)至多有2 2k k1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (k1)k1)。證明：由性質(zhì)證明：由性質(zhì)1 1可見(jiàn)，深度為可見(jiàn)，深度為k k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為 kii11220 + 21 + + 2k-1 = 2k - -1kii1(層上的最大結(jié)點(diǎn)數(shù)）第性質(zhì)性質(zhì)3 3 對(duì)任何一棵二叉樹(shù)對(duì)任何一棵二叉樹(shù)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ù)二叉樹(shù)的定義，則根據(jù)二叉樹(shù)的定義， 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 滿二叉樹(shù)滿二叉樹(shù) (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。兩種特殊形態(tài)的二叉樹(shù)兩種特殊形態(tài)的二叉樹(shù)621754389 10 1113 14 1512滿二叉樹(shù)滿二叉樹(shù)1. 滿二叉樹(shù)滿二叉樹(shù) (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。兩種特殊形態(tài)的二叉樹(shù)兩種特殊形態(tài)的二叉樹(shù)621754389 1

11、0 1113 14 1512滿二叉樹(shù)滿二叉樹(shù)若設(shè)二叉樹(shù)的高度為若設(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)，這就是完全二叉樹(shù)。，這就是完全二叉樹(shù)。6217543891011122. 完全二叉樹(shù)完全二叉樹(shù) (Complete Binary Tree)62175438910 111.1.深度為深度為h h的完全二叉樹(shù)其結(jié)點(diǎn)個(gè)數(shù)的取值范圍的完全二叉樹(shù)其結(jié)點(diǎn)個(gè)數(shù)的取值范圍2h-1h-1 2h h-12.2.完

12、全二叉樹(shù)中葉結(jié)點(diǎn)只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)完全二叉樹(shù)中葉結(jié)點(diǎn)只可能出現(xiàn)在倒數(shù)第一層和倒數(shù)第二層。第二層。3.3.且當(dāng)完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，有且僅有一個(gè)且當(dāng)完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，有且僅有一個(gè)單分支結(jié)點(diǎn)，為奇數(shù)時(shí)無(wú)單分支結(jié)點(diǎn)。單分支結(jié)點(diǎn)，為奇數(shù)時(shí)無(wú)單分支結(jié)點(diǎn)。有關(guān)完全二叉樹(shù)的重要結(jié)論有關(guān)完全二叉樹(shù)的重要結(jié)論n n0 0=(n=(n奇數(shù)奇數(shù)+1)/2+1)/2n n0 0=n=n偶數(shù)偶數(shù)/2/2一棵完全二叉樹(shù)有一棵完全二叉樹(shù)有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ù)的深度為證明：設(shè)完全二叉樹(shù)的深度為 h h，則根據(jù)性質(zhì)則根據(jù)性質(zhì)2 2和完全二和完全二叉樹(shù)的定義叉樹(shù)的定義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無(wú)左孩子無(wú)左孩子, ,否則其左孩子否則其左孩子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無(wú)右孩子無(wú)右孩子, ,否則其右孩子否則其右孩子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ǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素，即將完全二叉樹(shù)至右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素，即將完全二叉樹(shù)上編號(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)完全二叉樹(shù)的順序存儲(chǔ)表示圖解完全二叉樹(shù)的順序存儲(chǔ)表示圖解完全二叉樹(shù)完全二叉樹(shù)1 2 3 4 5 6 7 8 91012489 1056730217365849 對(duì)于一般二叉樹(shù)，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉對(duì)于一般二叉樹(shù)，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)

16、分量中。樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。9123654789 10一般二叉樹(shù)一般二叉樹(shù)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)的單支樹(shù)，卻需要長(zhǎng)度為個(gè)結(jié)點(diǎn)的單支樹(shù)，卻需要長(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; /根指針根指針 二叉鏈表的定義二叉鏈表的定義單支樹(shù)的二叉鏈表（單支樹(shù)的二

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 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)遍歷定義遍歷定義所謂遍歷即如何按某條搜索路徑巡所謂遍歷即

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

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

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

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

23、建立二叉樹(shù)。以遞歸方式建立二叉樹(shù)。n輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)先序遍歷的輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(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)。按先序建立二叉樹(shù)按先序建立二叉樹(shù)(遞歸算法遞歸算法)ABCDEGFA B C D E G F 如圖所示的二叉樹(shù)的先序遍歷順序?yàn)槿鐖D所示的二叉樹(shù)的先序遍歷順序?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 圖的鄰接表表示法圖的鄰接表表示法普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)開(kāi)始就能很快開(kāi)始就能很快“順藤摸瓜順藤摸瓜”而遍歷整棵樹(shù)。而遍歷整棵樹(shù)。例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H GB D C E A F H G，實(shí)際上，實(shí)際上已

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

26、指示其前驅(qū)；域指示其前驅(qū)； 若結(jié)點(diǎn)有右子樹(shù)若結(jié)點(diǎn)有右子樹(shù), ,則其則其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)成的二叉樹(shù)鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)以這種結(jié)點(diǎn)構(gòu)成的二叉樹(shù)鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)構(gòu), , 叫做叫做線索鏈表線索鏈表, ,其中指向結(jié)點(diǎn)其中指向結(jié)點(diǎn)前驅(qū)前驅(qū)和和后繼的指針后繼的指針, , 叫作叫作線索線索, , 加上線索的二叉樹(shù)稱之為加上線索的二叉

28、樹(shù)稱之為線索二叉樹(shù)線索二叉樹(shù)。中序線索二叉樹(shù)中序線索二叉樹(shù)BDAECBDAEC，如下圖所示：，如下圖所示： 對(duì)二叉樹(shù)以某種次序遍歷使其變成線索二對(duì)二叉樹(shù)以某種次序遍歷使其變成線索二叉樹(shù)的過(guò)程叫做叉樹(shù)的過(guò)程叫做線索化線索化. . 在線索樹(shù)中進(jìn)行遍歷時(shí)在線索樹(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í)，其右子樹(shù)最左下結(jié)點(diǎn)為其時(shí)，其右子樹(shù)最左下結(jié)點(diǎn)為其后繼。后繼。abcde中

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

30、附設(shè)一附設(shè)一個(gè)指針個(gè)指針prepre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn), ,若指針若指針p p指向當(dāng)指向當(dāng)前訪問(wèn)過(guò)的結(jié)點(diǎn)前訪問(wèn)過(guò)的結(jié)點(diǎn), ,則則prepre指向它的前驅(qū)。指向它的前驅(qū)。 線索化的實(shí)質(zhì)線索化的實(shí)質(zhì)StatusStatus InOrderThreading(InOrderThreading(BiThrTree&Thrt,BiThrTree T) ) /中序遍歷并線索化二叉樹(shù)，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；/若二叉樹(shù)為空，則左指針也回指 Else ThrtleftChild=T; Pre=Thrt；/pre總是指向最后一個(gè)訪問(wèn)過(guò)的結(jié)點(diǎn)，即其后要訪問(wèn)結(jié)點(diǎn)的前驅(qū) InThreading(T)； /線索化的主過(guò)程 prerightChild=Thrt； prerightThread=Thread； ThrtrightThread=pre； /將最后一個(gè)結(jié)點(diǎn)線索化 return OK； 算法算法 6.6 中序線索二叉樹(shù)中序線索二叉樹(shù)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 樹(shù)和森林樹(shù)和森林1.1.樹(shù)的雙親表示法樹(shù)的雙親表示法2.2.孩子表示法孩子表示法( (多重鏈表多重鏈表) )3.3.孩子兄弟表示法孩子兄弟表示法6.4.16.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef struct PTNode TElemType data ； int parent ；PTNode;1.1.樹(shù)的雙親表示法樹(shù)的雙親表示法#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)用，直到遇到無(wú)雙親的結(jié)點(diǎn)時(shí)，便找到了樹(shù)的根。直到遇到無(wú)雙親的結(jié)點(diǎn)時(shí)，便找到了樹(shù)的根。 BAGEIDHCFEDCBAHI440-1101654321078data parent樹(shù)的雙親表示法示例樹(shù)的雙親表示法示例typedef struct PTNode TElemType data ； int parent ；PTNode;樹(shù)的雙親表

34、示法形式說(shuō)明如下：樹(shù)的雙親表示法形式說(shuō)明如下：#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為樹(shù)的度為樹(shù)的度) 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ù)定義右兄弟表示實(shí)現(xiàn)的樹(shù)定義6.4.26.4.2 森林與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換BACDEFJHGI森林的二叉樹(shù)表示3 棵樹(shù)的森林BADCEFHGIJT1T2T3BACDEFJHGI各棵樹(shù)的二叉樹(shù)表示T1T2T3樹(shù)的先根樹(shù)的先根遍歷遍歷n當(dāng)樹(shù)非空時(shí)當(dāng)樹(shù)非空時(shí)u

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

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

39、第一棵樹(shù)之后剩余的樹(shù)構(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)的二叉樹(shù)的先序遍歷。森林的先序遍歷即為其對(duì)應(yīng)的二叉樹(shù)的先序遍歷。BADCBACDHGIJJHGIEFEF二、中序遍歷森林二、中序遍歷森林 若森林非空，則可按下述規(guī)則遍歷之：若森林非空，則可按下述規(guī)則遍歷之： (1) (1) 中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林； (2) (2) 訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)； (3) (3) 中序

40、遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(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)的二叉樹(shù)的中序遍歷。森林的中序遍歷即為其對(duì)應(yīng)的二叉樹(shù)的中序遍歷。BADCBACDHGIJJHGIEFEF帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度 (Weighted Path Length, WPL)二叉樹(shù)的帶權(quán)二叉樹(shù)的帶權(quán) (外部外部) 路徑長(zhǎng)度是樹(shù)的各葉結(jié)點(diǎn)所帶路徑長(zhǎng)度是樹(shù)的各葉結(jié)點(diǎn)所帶的權(quán)值的權(quán)值 wi 與該結(jié)點(diǎn)到根的路徑長(zhǎng)度與該結(jié)點(diǎn)到根的路徑長(zhǎng)度 li

41、 的乘積的和。的乘積的和。10niiilwWPL6.6.6 6 赫夫曼樹(shù)及其應(yīng)用赫夫曼樹(shù)及其應(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）樹(shù)的帶權(quán)路徑長(zhǎng)度最小，）樹(shù)的帶權(quán)路徑長(zhǎng)度最小， 可以驗(yàn)證，它恰為哈夫曼樹(shù)?？梢则?yàn)證，它恰為哈夫曼樹(shù)。abcd7ab524ca

42、b4d2ab75a7ab5bcd24 (a) (b) (c) 赫夫曼樹(shù)赫夫曼樹(shù)n帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹(shù)即為赫夫曼樹(shù)。帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹(shù)即為赫夫曼樹(shù)。n在哈夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近在哈夫曼樹(shù)中，權(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棵二叉樹(shù)的森林棵二叉樹(shù)的森林 F= TF= T0 0, T, T1 1, T, T2 2, , , T, Tn-1 n-1 ，其中，其中每棵二叉樹(shù)每棵二叉樹(shù) T Ti i 只有一只有一 個(gè)帶權(quán)值個(gè)帶權(quán)值 w

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

44、的二叉樹(shù)加入 F F。F : 7 5 2 47524初始F : 7 5 6合并2 475246F : 7 11 1175246合并5 6F : 18 合并7 11527461118赫夫曼樹(shù)的構(gòu)造過(guò)程舉例赫夫曼樹(shù)的構(gòu)造過(guò)程舉例可以利用二叉樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼，若約定左可以利用二叉樹(shù)來(lái)設(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;赫夫曼