數(shù)據(jù)結(jié)構(gòu)第7課樹(shù)

1、Powered by yuanmayingdiyisucaidw2f樹(shù)樹(shù)數(shù)據(jù)結(jié)構(gòu)之四樹(shù)樹(shù) 樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的非線性非線性結(jié)構(gòu)結(jié)構(gòu) 樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。 樹(shù)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用樹(shù)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用例如在編譯程序中，用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系例如在編譯程序中，用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息；在分析算法的行為時(shí)，可用樹(shù)來(lái)描述統(tǒng)中，可用樹(shù)來(lái)組織信息；在分析算法的行為時(shí)，可用樹(shù)來(lái)描述其執(zhí)行過(guò)程等等。其執(zhí)行過(guò)程等等。7.1樹(shù)的定義和基本術(shù)語(yǔ)1 1 樹(shù)的定義樹(shù)的定

2、義 樹(shù)樹(shù)(Tree)是是n(n0)個(gè)結(jié)點(diǎn)的有限集合個(gè)結(jié)點(diǎn)的有限集合T，若，若n=0時(shí)稱(chēng)為空樹(shù)，否則：時(shí)稱(chēng)為空樹(shù)，否則： 有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(Root)結(jié)點(diǎn)；結(jié)點(diǎn)； 若若n1時(shí)，其余的結(jié)點(diǎn)被分為時(shí)，其余的結(jié)點(diǎn)被分為m(m0)個(gè)個(gè)互不相交的子集的子集T1, T2, T3Tm，其中每個(gè)子集本身又，其中每個(gè)子集本身又是一棵樹(shù)，稱(chēng)其為根的子樹(shù)是一棵樹(shù)，稱(chēng)其為根的子樹(shù)(Subtree)。 這是樹(shù)的遞歸定義，即用樹(shù)來(lái)定義樹(shù)，而只有這是樹(shù)的遞歸定義，即用樹(shù)來(lái)定義樹(shù)，而只有一個(gè)結(jié)點(diǎn)的樹(shù)必定僅由根組成，如圖一個(gè)結(jié)點(diǎn)的樹(shù)必定僅由根組成，如圖6-1(a)所示。所示。樹(shù)的定義和基本

3、術(shù)語(yǔ)2 樹(shù)的基本術(shù)語(yǔ) 結(jié)點(diǎn)(node)：一個(gè)數(shù)據(jù)元素及其若干指向其子樹(shù)的分支。 結(jié)點(diǎn)的度(degree) 、樹(shù)的度：結(jié)點(diǎn)所擁有的子樹(shù)的棵數(shù)稱(chēng)為結(jié)點(diǎn)的度。樹(shù)中結(jié)點(diǎn)度的最大值稱(chēng)為樹(shù)的度。 圖圖6-1 樹(shù)的示樹(shù)的示例形式例形式AABDCEGFHIMJNKL(a) 只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)(b) 一般的樹(shù)一般的樹(shù)如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)A的度是的度是3 ，結(jié)點(diǎn)，結(jié)點(diǎn)B的度是的度是2 ，結(jié)點(diǎn)，結(jié)點(diǎn)M的度是的度是0，樹(shù)的度是，樹(shù)的度是3 。樹(shù)的定義和基本術(shù)語(yǔ) 葉子(left)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)(或終端結(jié)點(diǎn))。相對(duì)應(yīng)地，度不為0的結(jié)點(diǎn)稱(chēng)為非葉子結(jié)點(diǎn)(分支結(jié)點(diǎn))。 如圖6-1(b)

4、中結(jié)點(diǎn)H、I、J、K、L、M、N是葉子結(jié)點(diǎn)，而所有其它結(jié)點(diǎn)都是分支結(jié)點(diǎn)。 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn) 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)B 、C、D是結(jié)點(diǎn)是結(jié)點(diǎn)A的子結(jié)點(diǎn)的子結(jié)點(diǎn)，而，而結(jié)點(diǎn)結(jié)點(diǎn)A是是結(jié)點(diǎn)結(jié)點(diǎn)B 、C、D的的父結(jié)點(diǎn)父結(jié)點(diǎn)；類(lèi)似地結(jié)點(diǎn)類(lèi)似地結(jié)點(diǎn)E 、F是是結(jié)點(diǎn)結(jié)點(diǎn)B的子結(jié)點(diǎn)的子結(jié)點(diǎn)，結(jié)點(diǎn)，結(jié)點(diǎn)B是是結(jié)點(diǎn)結(jié)點(diǎn)E 、F的的父父結(jié)點(diǎn)。結(jié)點(diǎn)。 同一雙親結(jié)點(diǎn)的所有子結(jié)點(diǎn)互稱(chēng)為同一雙親結(jié)點(diǎn)的所有子結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)。 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)B 、C、D是兄弟結(jié)點(diǎn)；結(jié)點(diǎn)是兄弟結(jié)點(diǎn)；結(jié)點(diǎn)E 、F是兄弟結(jié)點(diǎn)。是兄弟結(jié)點(diǎn)。樹(shù)的定義和基本術(shù)語(yǔ) 層次 規(guī)定樹(shù)中根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)

5、的層次等于其雙親結(jié)點(diǎn)的層次加1。 若某結(jié)點(diǎn)在第i(i1)層，則其子結(jié)點(diǎn)在第i+1層。 結(jié)點(diǎn)的層次路徑、祖先、子孫 從根結(jié)點(diǎn)開(kāi)始，到達(dá)某結(jié)點(diǎn)p所經(jīng)過(guò)的所有結(jié)點(diǎn)成為結(jié)點(diǎn)p的層次路徑(有且只有一條)。 結(jié)點(diǎn)p的層次路徑上的所有結(jié)點(diǎn)（p除外）稱(chēng)為p的祖先(ancester) 。 以某一結(jié)點(diǎn)為根的子樹(shù)中的任意結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)(descent)。 樹(shù)的定義和基本術(shù)語(yǔ) 樹(shù)的深度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次值，又稱(chēng)為樹(shù)的高度，如圖6-1(b)中樹(shù)的高度為4。 有序樹(shù)和無(wú)序樹(shù)：對(duì)于一棵樹(shù)，若其中每一個(gè)結(jié)點(diǎn)的子樹(shù)（若有）具有一定的次序，則該樹(shù)稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。 森林(forest)：是m(

6、m0)棵互不相交的樹(shù)的集合。顯然，若將一棵樹(shù)的根結(jié)點(diǎn)刪除，剩余的子樹(shù)就構(gòu)成了森林。樹(shù)的表示形式圖圖6-2 樹(shù)的表示樹(shù)的表示形式形式(c)嵌套集合嵌套集合形式形式(b) 廣義表廣義表形式形式(A(B(E(K,L),F),C(G(M,N),D(H,I,J)HIJDFBK LECM NGAABDCEGFHIMJNKL（a）倒懸樹(shù)）倒懸樹(shù)習(xí)習(xí) 題題 假設(shè)在樹(shù)中，假設(shè)在樹(shù)中， 結(jié)點(diǎn)結(jié)點(diǎn)x是結(jié)點(diǎn)是結(jié)點(diǎn)y的雙親時(shí)，用的雙親時(shí)，用(x,y)來(lái)來(lái)表示樹(shù)邊。已知一棵樹(shù)的樹(shù)邊集合為表示樹(shù)邊。已知一棵樹(shù)的樹(shù)邊集合為 (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h

7、,l), (c,h), (a,c) ，用樹(shù)型表示，用樹(shù)型表示法表示該樹(shù)，并回答下列問(wèn)題：法表示該樹(shù)，并回答下列問(wèn)題： 哪個(gè)是根結(jié)點(diǎn)哪個(gè)是根結(jié)點(diǎn)? 哪些是葉子結(jié)點(diǎn)哪些是葉子結(jié)點(diǎn)? 哪個(gè)是哪個(gè)是g的的雙親雙親? 哪些是哪些是g的祖先的祖先? 哪些是哪些是g的孩子的孩子? 那些是那些是e的子孫的子孫? 哪些是哪些是e的兄弟的兄弟? 哪些是哪些是f的兄弟的兄弟? b和和n的層次各是多少的層次各是多少? 樹(shù)的深度是多少樹(shù)的深度是多少? 以結(jié)以結(jié)點(diǎn)點(diǎn)c為根的子樹(shù)的深度是多少為根的子樹(shù)的深度是多少?7.2 二叉樹(shù)二叉樹(shù)1 1 二叉樹(shù)的定義二叉樹(shù)的定義 二叉樹(shù)二叉樹(shù)(Binary tree)(Binary t

8、ree)是是n(nn(n0)0)個(gè)個(gè)結(jié)點(diǎn)的有限集合。若結(jié)點(diǎn)的有限集合。若n=0n=0時(shí)稱(chēng)為空樹(shù)，時(shí)稱(chēng)為空樹(shù)，否則：否則： 有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(Root)(Root)結(jié)點(diǎn)；結(jié)點(diǎn)； 若若n1n1時(shí)，其余的結(jié)點(diǎn)被分成為時(shí)，其余的結(jié)點(diǎn)被分成為二個(gè)互不相交二個(gè)互不相交的子集的子集T T1 1,T,T2 2，分別稱(chēng)，分別稱(chēng)之為左、右子樹(shù)，并且左、右子樹(shù)之為左、右子樹(shù)，并且左、右子樹(shù)又都是二叉樹(shù)。又都是二叉樹(shù)。 由此可知，二叉樹(shù)的由此可知，二叉樹(shù)的定義是遞歸定義是遞歸的。的。二叉樹(shù)二叉樹(shù) 結(jié)構(gòu)簡(jiǎn)單結(jié)構(gòu)簡(jiǎn)單 存儲(chǔ)效率高，存儲(chǔ)效率高， 操作算法相對(duì)簡(jiǎn)單操作算法相對(duì)簡(jiǎn)單 任何

9、樹(shù)都很容易轉(zhuǎn)任何樹(shù)都很容易轉(zhuǎn)化成二叉樹(shù)結(jié)構(gòu)?；啥鏄?shù)結(jié)構(gòu)。二叉樹(shù)的基本形態(tài)二叉樹(shù)的基本形態(tài)二叉樹(shù)有二叉樹(shù)有5種基本形態(tài)：種基本形態(tài)：AAAA(a)(b)(c)(d)(e)(a) 空空二叉樹(shù)二叉樹(shù)(b) 單結(jié)點(diǎn)單結(jié)點(diǎn)二叉樹(shù)二叉樹(shù)(c) 右子樹(shù)為空右子樹(shù)為空(d) 左子樹(shù)為空左子樹(shù)為空(e) 左左、右子樹(shù)都不空右子樹(shù)都不空6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)性質(zhì)1：在非空二叉樹(shù)中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k1) 。性質(zhì)3：對(duì)任何一棵二叉樹(shù)，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。6.2.36.2.3滿二叉樹(shù)和完全二叉樹(shù)滿二

10、叉樹(shù)和完全二叉樹(shù) 一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿二叉樹(shù)(Full Binary Tree)。894101151213614157213(a) 滿二叉樹(shù)滿二叉樹(shù)滿二叉樹(shù)的特點(diǎn)：滿二叉樹(shù)的特點(diǎn)： 基本特點(diǎn)是每一層上的基本特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。 滿二叉樹(shù)的所有的支結(jié)滿二叉樹(shù)的所有的支結(jié)點(diǎn)都有左點(diǎn)都有左、右子樹(shù)。右子樹(shù)。 可對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)可對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，若規(guī)定從根結(jié)行連續(xù)編號(hào)，若規(guī)定從根結(jié)點(diǎn)開(kāi)始，按點(diǎn)開(kāi)始，按“自上而下自上而下、自自左至右左至右”的原則進(jìn)行。的原則進(jìn)行。6.2.36.2.3滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù)

11、完全二叉樹(shù)(Complete Binary Tree)：如果深度為k，由n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)，該二叉樹(shù)稱(chēng)為完全二叉樹(shù)。894101152112673(b) 完全二叉樹(shù)完全二叉樹(shù)1362455674213(c) 非完全二叉樹(shù)非完全二叉樹(shù)完全二叉樹(shù)是滿二叉樹(shù)的一部分完全二叉樹(shù)是滿二叉樹(shù)的一部分滿二叉樹(shù)是完全二叉樹(shù)的特例。滿二叉樹(shù)是完全二叉樹(shù)的特例。完全二叉樹(shù)的特點(diǎn)完全二叉樹(shù)的特點(diǎn) 若完全二叉樹(shù)的深度為若完全二叉樹(shù)的深度為k ，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k k層或?qū)踊騥-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的

12、最大層次為層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為l，則其左子樹(shù)的最大層次為，則其左子樹(shù)的最大層次為l或或l+1 1。 性質(zhì)4：n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為： 2n +1。 其中符號(hào)：其中符號(hào)： x 表示不大于表示不大于x的最大整數(shù)。的最大整數(shù)。 x 表示不小于表示不小于x的最小整數(shù)。的最小整數(shù)。完全二叉樹(shù)的特點(diǎn)完全二叉樹(shù)的特點(diǎn) 性質(zhì)5：若對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)(深度為2n+1)的結(jié)點(diǎn)按層（從第1層到第2n +1層)序自左至右進(jìn)行編號(hào),則對(duì)于編號(hào)為i（1in)的結(jié)點(diǎn)： 若i=1：則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親結(jié)點(diǎn)；否則，若i1，則其雙親結(jié)點(diǎn)編號(hào)是 i/2 。 如果2in：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)

13、，無(wú)左孩子；否則，其左孩子結(jié)點(diǎn)編號(hào)是2i。 如果2i+1n：則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子結(jié)點(diǎn)編號(hào)是2i+1。6.2.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義：二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義：#define MAX 100sqbitreeMAX; 用一組地址連續(xù)的存儲(chǔ)單元依次用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下自上而下、自左自左至右至右”存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。 對(duì)于完全二叉樹(shù)上編號(hào)為對(duì)于完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為數(shù)組的下標(biāo)值為i-1的分量中的分量中，如圖，如圖6-6(c

14、)所示。所示。 對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中存儲(chǔ)在一維數(shù)組中，如圖，如圖6-6(d)所示。所示。abcdhiejklfg(a) 完全二叉樹(shù)完全二叉樹(shù)(b) 非完全二叉樹(shù)非完全二叉樹(shù)abcdefgh1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l (c) 完全二叉樹(shù)的順序存儲(chǔ)形式完全二叉樹(shù)的順序存儲(chǔ)形式1 2 3 4 5 6 7 8 9 10 11a b c d e h f g(d) 非完全二叉樹(shù)的順序存儲(chǔ)形式非完全二叉樹(shù)的順序存儲(chǔ)形式圖圖6

15、-6 二叉二叉樹(shù)及其樹(shù)及其順序存儲(chǔ)形式順序存儲(chǔ)形式最壞的情況下，最壞的情況下，一個(gè)深度為一個(gè)深度為k且且只有只有k個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度單支樹(shù)需要長(zhǎng)度為為2k-1的一維數(shù)的一維數(shù)組組。設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(1) 結(jié)點(diǎn)的類(lèi)型及其定義結(jié)點(diǎn)的類(lèi)型及其定義 二叉鏈表結(jié)點(diǎn)二叉鏈表結(jié)點(diǎn)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域，如圖別指向左右子結(jié)點(diǎn)的指針域，如圖6-7(a)所示。所示。 struct BTNode int data ; BTNode *Lchild , *Rchild ;

16、2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 三三叉鏈表結(jié)點(diǎn)叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個(gè)域外，再增加一。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖6-7(b)所示。所示。struct BTNode_3 int data ; BTNode_3 *Lchild , *Rchild , *parent ; Lchild data RchildLchild data parent Rchild(a) 二叉鏈表結(jié)點(diǎn)二叉鏈表結(jié)點(diǎn)(b) 三三叉鏈表結(jié)點(diǎn)叉鏈表結(jié)點(diǎn)圖圖6-7 鏈表結(jié)點(diǎn)結(jié)構(gòu)鏈表結(jié)點(diǎn)結(jié)構(gòu)形式形式例有一棵一般的二叉樹(shù)，如圖例有一棵一般的二叉樹(shù)，如圖 (a)

17、所示。以二叉鏈表和三所示。以二叉鏈表和三叉鏈表方式存儲(chǔ)的結(jié)構(gòu)圖分別如圖叉鏈表方式存儲(chǔ)的結(jié)構(gòu)圖分別如圖 (b) 、 (c)所示。所示。圖圖6-8 二叉樹(shù)及其二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(a) 二叉樹(shù)二叉樹(shù)afedcbg(c) 三三叉鏈表叉鏈表 a b c d e f g T(b) 二二叉鏈表叉鏈表 a b c d e g f T(2) 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)形式二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)形式6.3 遍歷二叉樹(shù)及其應(yīng)用遍歷二叉樹(shù)及其應(yīng)用遍歷二叉樹(shù)遍歷二叉樹(shù)(Traversing Binary Tree)：是指是指按指按指定的規(guī)律定的規(guī)律對(duì)二叉樹(shù)中的對(duì)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅

18、訪問(wèn)一次。 所謂所謂訪問(wèn)訪問(wèn)是指對(duì)結(jié)點(diǎn)做某種處理。如：輸出信息是指對(duì)結(jié)點(diǎn)做某種處理。如：輸出信息、修改結(jié)點(diǎn)的值等修改結(jié)點(diǎn)的值等。 二叉樹(shù)是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都可能有左二叉樹(shù)是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都可能有左、右兩棵子樹(shù)，因此，需要尋找一種規(guī)律，使二叉樹(shù)上的右兩棵子樹(shù)，因此，需要尋找一種規(guī)律，使二叉樹(shù)上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。 二叉樹(shù)的基本組成：根結(jié)點(diǎn)二叉樹(shù)的基本組成：根結(jié)點(diǎn)、左子樹(shù)左子樹(shù)、右子樹(shù)。若右子樹(shù)。若能依次遍歷這三部分，就是遍歷了二叉樹(shù)。能依次遍歷這三部分，就是遍歷了二叉樹(shù)。 若以若以L、D、R分別表示遍歷左子樹(shù)、遍

19、歷根結(jié)點(diǎn)和分別表示遍歷左子樹(shù)、遍歷根結(jié)點(diǎn)和遍歷右子樹(shù)，遍歷右子樹(shù)，則有六種遍歷方案：則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定若規(guī)定先左后右先左后右，則只有，則只有前三種前三種情況情況三種情況，分別是：三種情況，分別是：DLR先先( (根根) )序遍歷。序遍歷。LDR中中( (根根) )序遍歷。序遍歷。LRD后后( (根根) )序遍歷。序遍歷。 對(duì)于二叉樹(shù)的遍歷，遞歸遍歷算法具有非常清晰的對(duì)于二叉樹(shù)的遍歷，遞歸遍歷算法具有非常清晰的結(jié)構(gòu)。實(shí)際上，遞歸算法是由系統(tǒng)通過(guò)使用堆棧來(lái)實(shí)現(xiàn)結(jié)構(gòu)。實(shí)際上，遞歸算法是由系統(tǒng)通過(guò)使用堆棧來(lái)實(shí)現(xiàn)控制的?？刂频?。6.3.1 先序遍歷二

20、叉樹(shù)先序遍歷二叉樹(shù)1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； 先序遍歷左子樹(shù)先序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 先序遍歷右子樹(shù)先序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)。void PreorderTraverse(BTNode *T) if (T!=NULL) coutdata ; /* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 說(shuō)明：說(shuō)明：樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量樹(shù)

21、采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T T來(lái)指來(lái)指向。向。先序遍歷的遞歸算法(a) 二叉樹(shù)二叉樹(shù)afedcbg先序遍歷的結(jié)果？abcdegf 中序遍歷二叉樹(shù)1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 中序遍歷左子樹(shù)中序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； 中序遍歷右子樹(shù)中序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)。void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;coutdata ; /* 訪

22、問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */InorderTraverse(T-Rchild) ;中序遍歷的遞歸算法中序遍歷的遞歸算法(a) 二叉樹(shù)二叉樹(shù)afedcbg中序遍歷的結(jié)果？cbegdfa 6.3.3 后序遍歷二叉樹(shù)后序遍歷二叉樹(shù)1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 后序遍歷左子樹(shù)后序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 后序遍歷右子樹(shù)后序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法) ； 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) 。void PostorderTraverse(BTNode *T) if (T!=NULL) Postor

23、derTraverse(T-Lchild) ;PostorderTraverse(T-Rchild) ; coutdata) ; /* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */ 無(wú)論是哪種次序的遍歷，對(duì)有無(wú)論是哪種次序的遍歷，對(duì)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為間復(fù)雜度均為O(n) 。后序遍歷的遞歸算法后序遍歷的遞歸算法(a) 二叉樹(shù)二叉樹(shù)afedcbg后序遍歷的結(jié)果？cgefdba 如圖如圖6-9所示的二叉樹(shù)表示表達(dá)式：所示的二叉樹(shù)表示表達(dá)式：(a+b*(c-d)-e/f)按不同的次序遍歷此二叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序按不同的次序遍歷此二叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序排列起來(lái)的次序是

24、：排列起來(lái)的次序是：/fe-dcb*a+圖圖6-9表達(dá)式表達(dá)式 (a+b*(c-d)-e/f)二叉樹(shù)二叉樹(shù)其先序序列為：其先序序列為： -+a*b-cd/ef其中序序列為：其中序序列為： a+b*c-d-e/f其后序序列為：其后序序列為： abcd-*+ef/-6.3.4 層次遍歷二叉樹(shù)層次遍歷二叉樹(shù) 層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次序序“自上而下自上而下，從左至右從左至右”訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。 為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列。為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算是指

25、向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算法是：法是：若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T，p入隊(duì)；入隊(duì)； 隊(duì)首元素出隊(duì)到隊(duì)首元素出隊(duì)到p；訪問(wèn)訪問(wèn)p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； 將將p所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止。到隊(duì)空為止。#define MAX 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根結(jié)點(diǎn)入隊(duì)根結(jié)點(diǎn)入隊(duì) */w

26、hile (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ （1 1） 設(shè)有如圖設(shè)有如圖6-27所示的二叉樹(shù)。所示的二叉樹(shù)。 分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫(huà)出該二分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫(huà)出該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。 寫(xiě)出該二叉樹(shù)的先序、中序、后序遍歷序列。寫(xiě)出該二叉樹(shù)的先序、中序、后序遍歷序列。（2 2）已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序）已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別

27、為列分別為ABDGHCEFI和和GDHBAECIF，請(qǐng)畫(huà)出這棵二，請(qǐng)畫(huà)出這棵二叉樹(shù)，然后給出該樹(shù)的后序遍歷序列。叉樹(shù)，然后給出該樹(shù)的后序遍歷序列。（3 3） 設(shè)一棵二叉樹(shù)的中序遍歷序設(shè)一棵二叉樹(shù)的中序遍歷序列和后序遍歷序列分別為列和后序遍歷序列分別為BDCEAFHG和和DECBHGFA ，請(qǐng)，請(qǐng)畫(huà)出這棵二叉樹(shù)，然后給出該樹(shù)的先畫(huà)出這棵二叉樹(shù)，然后給出該樹(shù)的先序序列。序序列。圖圖6-27 二叉樹(shù)二叉樹(shù)adebfgchkmn6.5 樹(shù)與森林樹(shù)與森林 本節(jié)將討論樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)及森林與二叉樹(shù)之間本節(jié)將討論樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)及森林與二叉樹(shù)之間的相互轉(zhuǎn)換、樹(shù)的遍歷等。的相互轉(zhuǎn)換、樹(shù)的遍歷等。6.5.1 樹(shù)

28、的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)結(jié)構(gòu)根據(jù)應(yīng)用的不同而不同樹(shù)的存儲(chǔ)結(jié)構(gòu)根據(jù)應(yīng)用的不同而不同。1 雙親表示法雙親表示法(順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)) 用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器指示器(整數(shù)域整數(shù)域) ，用以指示雙親結(jié)用以指示雙親結(jié)點(diǎn)的位置點(diǎn)的位置(下標(biāo)值下標(biāo)值) 。數(shù)組元素及數(shù)組的類(lèi)型定義如下。數(shù)組元素及數(shù)組的類(lèi)型定義如下：#define MAX 100struct PTNode int data ;int parent ;Struct Ptree PTNode NodesMAX ;int root;

29、/* 根結(jié)點(diǎn)位置根結(jié)點(diǎn)位置 */int num ; /* 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) */ ; 圖圖6-13所示是一棵樹(shù)及其雙親所示是一棵樹(shù)及其雙親表示的存儲(chǔ)結(jié)構(gòu)表示的存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)結(jié)構(gòu)利這種存儲(chǔ)結(jié)構(gòu)利用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)?？梢苑奖愕刂苯诱业娇梢苑奖愕刂苯诱业饺我唤Y(jié)點(diǎn)的父任一結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)，但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組描整個(gè)數(shù)組。FGHIRABCDE圖圖6-13 樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)R -10A 01B 02C 03D 14E 15F 36G 67H 68I 692 孩子鏈表表示法孩子鏈表表示法 樹(shù)中每個(gè)結(jié)點(diǎn)有多個(gè)指針域

30、，每個(gè)指針指向其一棵樹(shù)中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其一棵子樹(shù)的根結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)。有。有兩種結(jié)點(diǎn)結(jié)構(gòu)兩種結(jié)點(diǎn)結(jié)構(gòu)。 定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu) 指針域的數(shù)目就是樹(shù)的度指針域的數(shù)目就是樹(shù)的度。 其特點(diǎn)是其特點(diǎn)是：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯。結(jié)點(diǎn)結(jié)構(gòu)如圖結(jié)點(diǎn)結(jié)構(gòu)如圖6-14(a) 所示所示。在一棵有在一棵有n個(gè)結(jié)點(diǎn)，度為個(gè)結(jié)點(diǎn)，度為k的樹(shù)中必有的樹(shù)中必有n(k-1)+1空指針域空指針域。 不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu) 樹(shù)中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度，樹(shù)中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度，如圖如圖6-14(b) 所示。沒(méi)有多余的指針域，

31、但操作不便。所示。沒(méi)有多余的指針域，但操作不便。圖圖6-14 孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)data child1 child2 childn(a) 定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)(b) 不不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)data k child1 child2 childk 復(fù)合鏈表結(jié)構(gòu)復(fù)合鏈表結(jié)構(gòu) 對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用帶頭結(jié)點(diǎn)的對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用帶頭結(jié)點(diǎn)的單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖6-15所示所示。 n個(gè)結(jié)點(diǎn)的樹(shù)有個(gè)結(jié)點(diǎn)的樹(shù)有n個(gè)個(gè)(孩子孩子)單鏈表單鏈表(葉子結(jié)點(diǎn)的孩子鏈葉子結(jié)點(diǎn)的孩子鏈表為空表為空)，而，而n個(gè)頭結(jié)點(diǎn)

32、又組成一個(gè)線性表且以順序存儲(chǔ)個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)結(jié)構(gòu)表示結(jié)構(gòu)表示。data firstchild(a) 頭結(jié)點(diǎn)頭結(jié)點(diǎn)childno next(b) 表結(jié)點(diǎn)表結(jié)點(diǎn)圖圖6-15 孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)類(lèi)型定義如下：數(shù)據(jù)結(jié)構(gòu)類(lèi)型定義如下：#define MAX 100struct listnode int childno ; /* 孩子結(jié)點(diǎn)編號(hào)孩子結(jié)點(diǎn)編號(hào) */listno *next ;CTNode; /* 表結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)結(jié)構(gòu) */struct int data ;CTNode *firstchild ;HNode; /* 頭結(jié)點(diǎn)結(jié)構(gòu)頭結(jié)點(diǎn)結(jié)構(gòu) */struct

33、 HNode nodesMAX ;int root; /* 根結(jié)點(diǎn)位置根結(jié)點(diǎn)位置 */int num ; /* 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) */CLinkList; /* 頭結(jié)點(diǎn)結(jié)構(gòu)頭結(jié)點(diǎn)結(jié)構(gòu) */ 圖圖6-13所示的樹(shù)所示的樹(shù)T的孩子鏈表表示的存儲(chǔ)結(jié)構(gòu)如圖的孩子鏈表表示的存儲(chǔ)結(jié)構(gòu)如圖6-16所示。所示。CLinkListnodes789 35 012 6 0123456789MAX_NODE-1rootnumA B C D E F G H I R 49圖圖6-16 圖圖6-13的樹(shù)的樹(shù)T的孩子鏈表存儲(chǔ)結(jié)構(gòu)的孩子鏈表存儲(chǔ)結(jié)構(gòu)3 孩子兄弟表示法孩子兄弟表示法(二叉樹(shù)表示法二叉樹(shù)表示法)以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)

34、構(gòu)，其結(jié)點(diǎn)形式如圖以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)形式如圖6-17(a)所示所示。 兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類(lèi)型定義如下：個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類(lèi)型定義如下：struct CSnode int data ;CSnode *firstchild, *nextsibing ; 圖圖6-17(b)所示樹(shù)的孩子兄弟表示的存儲(chǔ)結(jié)構(gòu)如圖所示樹(shù)的孩子兄弟表示的存儲(chǔ)結(jié)構(gòu)如圖6-17(c)。圖圖6-17 樹(shù)及孩子兄弟存儲(chǔ)結(jié)構(gòu)樹(shù)及孩子兄弟存儲(chǔ)結(jié)構(gòu)(b) 樹(shù)樹(shù) FGRABCDE(c) 孩子兄弟存儲(chǔ)結(jié)構(gòu)孩子兄弟存儲(chǔ)結(jié)構(gòu) R A D C G B

35、 F E 孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchild data nextsibing(a) 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)6.5.2 森林與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換 由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。 從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相同從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而已。的，只是對(duì)指針的邏輯解釋不同而已。 從樹(shù)的二叉鏈表表示的定義

36、可知，任何一棵和樹(shù)從樹(shù)的二叉鏈表表示的定義可知，任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。 圖圖6-18直觀地展示了樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。直觀地展示了樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。圖圖6-18 樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系二叉樹(shù)二叉樹(shù) CERADB R A D C B E 樹(shù)樹(shù) RABCDE對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系 R A D C B E C B E R A D 存儲(chǔ)存儲(chǔ)解釋解釋存儲(chǔ)存儲(chǔ)解釋解釋1 樹(shù)轉(zhuǎn)換成二叉樹(shù)樹(shù)轉(zhuǎn)換成二叉樹(shù) 對(duì)于一般的樹(shù)，可以方便地轉(zhuǎn)換成一棵唯一的二對(duì)于一般的樹(shù)，可以方便地轉(zhuǎn)換成一棵唯一的二叉樹(shù)與之對(duì)應(yīng)。將樹(shù)轉(zhuǎn)換成二叉樹(shù)在叉樹(shù)與之對(duì)應(yīng)。

37、將樹(shù)轉(zhuǎn)換成二叉樹(shù)在“孩子兄弟表示法孩子兄弟表示法”中已給出，其詳細(xì)步驟是：中已給出，其詳細(xì)步驟是： 加虛線加虛線。在樹(shù)的每層按從。在樹(shù)的每層按從“左至右左至右”的順序在兄的順序在兄弟結(jié)點(diǎn)之間加虛線相連。弟結(jié)點(diǎn)之間加虛線相連。 去連線去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線都去掉。有其它子結(jié)點(diǎn)的連線都去掉。 旋轉(zhuǎn)旋轉(zhuǎn)。將樹(shù)順時(shí)針旋轉(zhuǎn)。將樹(shù)順時(shí)針旋轉(zhuǎn)450，原有的實(shí)線左斜。，原有的實(shí)線左斜。 整型整型。將旋轉(zhuǎn)后樹(shù)中的所有虛線改為實(shí)線，并向。將旋轉(zhuǎn)后樹(shù)中的所有虛線改為實(shí)線，并向右斜。該轉(zhuǎn)換過(guò)程如圖右斜。該轉(zhuǎn)換過(guò)程如圖6-19所示。所示。 這樣轉(zhuǎn)

38、換后的二叉樹(shù)的特點(diǎn)是這樣轉(zhuǎn)換后的二叉樹(shù)的特點(diǎn)是： 二叉樹(shù)的二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)根結(jié)點(diǎn)沒(méi)有右子樹(shù)，只有左，只有左子樹(shù)；子樹(shù)； 左子結(jié)點(diǎn)仍然是原來(lái)樹(shù)中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)仍然是原來(lái)樹(shù)中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)左子結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)均是原來(lái)樹(shù)中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。均是原來(lái)樹(shù)中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。圖圖6-19 樹(shù)向二叉樹(shù)的轉(zhuǎn)換過(guò)程樹(shù)向二叉樹(shù)的轉(zhuǎn)換過(guò)程(a) 一般的樹(shù)一般的樹(shù) FGRABCDEFGRABCDE(b) 加虛線加虛線，去連線后去連線后 (C) 轉(zhuǎn)換后的二叉樹(shù)轉(zhuǎn)換后的二叉樹(shù)FGRACDBE2 二叉樹(shù)轉(zhuǎn)換成樹(shù)二叉樹(shù)轉(zhuǎn)換成樹(shù) 對(duì)于一棵轉(zhuǎn)換后的二叉樹(shù)，如何還原成原來(lái)

39、的樹(shù)對(duì)于一棵轉(zhuǎn)換后的二叉樹(shù)，如何還原成原來(lái)的樹(shù)? 其步驟是：其步驟是： 加虛線加虛線。若某結(jié)點(diǎn)。若某結(jié)點(diǎn)i是其父結(jié)點(diǎn)的左子樹(shù)的根結(jié)是其父結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)點(diǎn)，則將該結(jié)點(diǎn)i的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜索所有的右子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與索所有的右子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與i結(jié)點(diǎn)的結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相連，父結(jié)點(diǎn)之間加虛線相連，如圖如圖6-20(a)所示所示。 去連線去連線。去掉二叉樹(shù)中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)。去掉二叉樹(shù)中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之間的連線，之間的連線，如圖如圖6-20(b)所示所示。 規(guī)整化規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的

40、虛。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線，線變成實(shí)線，如圖如圖6-20(c)所示。所示。圖圖6-20 二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程(C) 還原后的樹(shù)還原后的樹(shù)FGRABCDE(b) 去連線后去連線后 (a) 加虛線后加虛線后 FGRACDBECFGRADBE3 森林轉(zhuǎn)換成二叉樹(shù)森林轉(zhuǎn)換成二叉樹(shù) 當(dāng)一般的樹(shù)轉(zhuǎn)換成二叉樹(shù)后，二叉樹(shù)的右子樹(shù)必當(dāng)一般的樹(shù)轉(zhuǎn)換成二叉樹(shù)后，二叉樹(shù)的右子樹(shù)必為空為空。若把森林中的第二棵樹(shù)。若把森林中的第二棵樹(shù)( (轉(zhuǎn)換成二叉樹(shù)后轉(zhuǎn)換成二叉樹(shù)后) )的根結(jié)的根結(jié)點(diǎn)作為第一棵樹(shù)點(diǎn)作為第一棵樹(shù)(二叉樹(shù)二叉樹(shù))的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則可導(dǎo)的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則可導(dǎo)

41、出森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換算法如下：出森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換算法如下： 設(shè)設(shè)F=T1, T2, ,Tn是森林，則按以下規(guī)則可轉(zhuǎn)換成是森林，則按以下規(guī)則可轉(zhuǎn)換成一棵二叉樹(shù)一棵二叉樹(shù)B=(root，LB，RB) 若若n=0，則，則B是空樹(shù)是空樹(shù)。 若若n0，則二叉樹(shù)，則二叉樹(shù)B的根是森林的根是森林T1的根的根root(T1)，B的左子樹(shù)的左子樹(shù)LB是是B(T11,T12, ,T1m) ，其中，其中T11,T12, ,T1m是是T1的子樹(shù)的子樹(shù)(轉(zhuǎn)換后轉(zhuǎn)換后)，而其右子樹(shù)，而其右子樹(shù)RB是從森是從森林林F=T2, T3, ,Tn轉(zhuǎn)換而成的二叉樹(shù)轉(zhuǎn)換而成的二叉樹(shù)。轉(zhuǎn)換步驟轉(zhuǎn)換步驟： 將將F=T1, T2

42、, ,Tn 中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)。 按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右子始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)，依次類(lèi)推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生樹(shù)，依次類(lèi)推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹(shù)的根結(jié)點(diǎn)，成的二叉樹(shù)的根結(jié)點(diǎn)，如圖如圖6-21所示所示。ACBDGMLHK(a) 森林森林圖圖6-21 森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程(b) 森林中每棵樹(shù)森林中每棵樹(shù) 對(duì)應(yīng)的二叉樹(shù)對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM(c) 森林對(duì)應(yīng)的二叉樹(shù)森林對(duì)應(yīng)的二叉樹(shù)ABC

43、DGLKHM4 二叉樹(shù)轉(zhuǎn)換成森林二叉樹(shù)轉(zhuǎn)換成森林 若若B=(root，LB，RB)是一棵二叉樹(shù)，則可以將其是一棵二叉樹(shù)，則可以將其轉(zhuǎn)換成由若干棵樹(shù)構(gòu)成的森林：轉(zhuǎn)換成由若干棵樹(shù)構(gòu)成的森林：F=T1, T2, ,Tn 。轉(zhuǎn)換算法轉(zhuǎn)換算法： 若若B是空樹(shù)，則是空樹(shù)，則F為空為空。 若若B非空，則非空，則F中第一棵樹(shù)中第一棵樹(shù)T1的根的根root(T1)就是二就是二叉樹(shù)的根叉樹(shù)的根root， T1中根結(jié)點(diǎn)的子森林中根結(jié)點(diǎn)的子森林F1是由樹(shù)是由樹(shù)B的左的左子樹(shù)子樹(shù)LB轉(zhuǎn)換而成的森林轉(zhuǎn)換而成的森林；F中除中除T1外其余樹(shù)組成的外其余樹(shù)組成的的森林的森林F=T2, T3, ,Tn 是由是由B右子樹(shù)右子樹(shù)RB

44、轉(zhuǎn)換得到的轉(zhuǎn)換得到的森林森林。 上述轉(zhuǎn)換規(guī)則是遞歸的上述轉(zhuǎn)換規(guī)則是遞歸的，可以寫(xiě)出其遞歸算法。以可以寫(xiě)出其遞歸算法。以下給出具體的還原步驟。下給出具體的還原步驟。 去連線去連線。將二叉樹(shù)。將二叉樹(shù)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)的連線全部去掉，得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林F中中的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)，的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)，如圖如圖6-22(b)所示所示。 二叉樹(shù)的還原二叉樹(shù)的還原。將各棵孤立的二叉樹(shù)按二叉樹(shù)還。將各棵孤立的二叉樹(shù)按二叉樹(shù)還原為樹(shù)的方

45、法還原成一般的樹(shù)，原為樹(shù)的方法還原成一般的樹(shù)，如圖如圖6- 22(c)所示所示。圖圖6-22 二叉樹(shù)還原成森林的過(guò)程二叉樹(shù)還原成森林的過(guò)程ACBDMGLHK(c) 還原成森林還原成森林(a) 二叉樹(shù)二叉樹(shù)ABCDGLKHM(b) 去連線后去連線后ABCDMGLKH6.5.3 樹(shù)和森林的遍歷樹(shù)和森林的遍歷1 樹(shù)的遍歷樹(shù)的遍歷 由樹(shù)結(jié)構(gòu)的定義可知，樹(shù)的遍歷有二種方法。由樹(shù)結(jié)構(gòu)的定義可知，樹(shù)的遍歷有二種方法。 先序遍歷先序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后：先訪問(wèn)根結(jié)點(diǎn)，然后依次先序遍歷依次先序遍歷完完每棵子樹(shù)。每棵子樹(shù)。如圖如圖6-23的樹(shù)，先序遍歷的次序是的樹(shù)，先序遍歷的次序是：ABDCKGJIFHE圖圖

46、6-23 樹(shù)樹(shù)ABCDEFGIJHK6.5.3 樹(shù)和森林的遍歷樹(shù)和森林的遍歷1 樹(shù)的遍歷樹(shù)的遍歷 后序遍歷后序遍歷：先：先依次后序遍歷完依次后序遍歷完每棵子樹(shù)，然后訪每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。問(wèn)根結(jié)點(diǎn)。如圖如圖6-23的樹(shù)，后序遍歷的次序是的樹(shù)，后序遍歷的次序是：ABDCKGJIFHE圖圖6-23 樹(shù)樹(shù)CDBFGIJHEKA說(shuō)明說(shuō)明： 樹(shù)的樹(shù)的先序遍歷先序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的叉樹(shù)后對(duì)二叉樹(shù)的先序遍歷先序遍歷相同。相同。 樹(shù)的樹(shù)的后序遍歷后序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的叉樹(shù)后對(duì)二叉樹(shù)的中序遍歷中序遍歷相同。相同。2 森林的遍

47、歷森林的遍歷 設(shè)設(shè)F=T1, T2, ,Tn是森林，對(duì)是森林，對(duì)F的遍歷有二種方法。的遍歷有二種方法。 先序遍歷先序遍歷：按：按先序遍歷先序遍歷樹(shù)的方式樹(shù)的方式依次依次遍歷遍歷F中的中的每棵樹(shù)。每棵樹(shù)。 中序遍歷中序遍歷：按：按后序遍歷后序遍歷樹(shù)的方式樹(shù)的方式依次依次遍歷遍歷F中的中的每棵樹(shù)。每棵樹(shù)。6.6 赫夫曼樹(shù)及其應(yīng)用赫夫曼樹(shù)及其應(yīng)用 赫夫曼赫夫曼(Huffman)樹(shù)又稱(chēng)最優(yōu)樹(shù)，是一類(lèi)帶權(quán)路徑樹(shù)又稱(chēng)最優(yōu)樹(shù)，是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)，有著廣泛的應(yīng)用。長(zhǎng)度最短的樹(shù)，有著廣泛的應(yīng)用。6.6.1 最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)(Huffman樹(shù)樹(shù))1 基本概念基本概念 結(jié)點(diǎn)路徑結(jié)點(diǎn)路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到

48、另一個(gè)結(jié)點(diǎn)的之間的分：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。 路徑長(zhǎng)度路徑長(zhǎng)度：結(jié)點(diǎn)路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度：結(jié)點(diǎn)路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。 樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。ABDCKGJIFHE圖圖6-23 樹(shù)樹(shù)例圖例圖6-23的樹(shù)的樹(shù)。A到到F ：結(jié)點(diǎn)路徑：結(jié)點(diǎn)路徑 AEF ；路徑長(zhǎng)度路徑長(zhǎng)度( (即邊的數(shù)目即邊的數(shù)目) ) 2 ；樹(shù)的路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度：3 3 1+5 2+2 3=19 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)的到樹(shù)的根結(jié)點(diǎn)：從該結(jié)點(diǎn)的到樹(shù)

49、的根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)( (值值) )的乘積的乘積。權(quán)權(quán)( (值值) )：各種：各種開(kāi)銷(xiāo)開(kāi)銷(xiāo)、代價(jià)代價(jià)、頻度頻度等的抽象稱(chēng)呼等的抽象稱(chēng)呼。 樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中：樹(shù)中所有葉子結(jié)點(diǎn)所有葉子結(jié)點(diǎn)的帶權(quán)路的帶權(quán)路徑長(zhǎng)度之和，記做：徑長(zhǎng)度之和，記做： WPL=w1 l1+w2 l2+ +wn ln=wi li (i=1,2, ,n)其中：其中：n為葉子結(jié)點(diǎn)的個(gè)數(shù)為葉子結(jié)點(diǎn)的個(gè)數(shù)；wi為第為第i個(gè)結(jié)點(diǎn)的權(quán)值個(gè)結(jié)點(diǎn)的權(quán)值； li為第為第i個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度。個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度。 Huffman樹(shù)樹(shù)：具有：具有n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值每個(gè)結(jié)點(diǎn)的權(quán)

50、值為為wi) 的二叉樹(shù)不止一棵，但在所有的這些二叉樹(shù)中，的二叉樹(shù)不止一棵，但在所有的這些二叉樹(shù)中，必定存在一棵必定存在一棵WPL值最小值最小的樹(shù)，稱(chēng)這棵樹(shù)為的樹(shù)，稱(chēng)這棵樹(shù)為Huffman樹(shù)樹(shù)(或稱(chēng)最優(yōu)樹(shù)或稱(chēng)最優(yōu)樹(shù)) 。 在許多判定問(wèn)題時(shí)，利用在許多判定問(wèn)題時(shí)，利用Huffman樹(shù)可以得到最佳判斷算法。樹(shù)可以得到最佳判斷算法。 如圖如圖6-24是權(quán)值分別為是權(quán)值分別為2、3、6、7，具有，具有4個(gè)葉子結(jié)點(diǎn)的二個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，它們的帶權(quán)路徑長(zhǎng)度分別為叉樹(shù)，它們的帶權(quán)路徑長(zhǎng)度分別為：(a) WPL=2 2+3 2+6 2+7 2=36 ；(b) WPL=2 1+3 2+6 3+7 3=47 ；(

51、c) WPL=7 1+6 2+2 3+3 3=34 。 其中其中(c)的的 WPL值最小，可以證明是值最小，可以證明是Huffman樹(shù)。樹(shù)。236736726723(a)(b)(c)圖圖6-24 具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)2 Huffman樹(shù)的構(gòu)造樹(shù)的構(gòu)造 根據(jù)根據(jù)n個(gè)權(quán)值個(gè)權(quán)值w1, w2, ,wn，構(gòu)造成，構(gòu)造成n棵二叉樹(shù)棵二叉樹(shù)的集合的集合F=T1, T2, ,Tn，其中每棵二叉樹(shù)只有一個(gè)，其中每棵二叉樹(shù)只有一個(gè)權(quán)值為權(quán)值為wi的根結(jié)點(diǎn)，沒(méi)有左、右子樹(shù)；的根結(jié)點(diǎn)，沒(méi)有左、右子樹(shù)； 在在F中中選取兩棵根結(jié)點(diǎn)權(quán)值最小選取兩棵根結(jié)點(diǎn)權(quán)值

52、最小的樹(shù)作為左的樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且新的二叉樹(shù)根結(jié)右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且新的二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和； 在在F中刪除這兩棵樹(shù)，同時(shí)將新得到的樹(shù)加入中刪除這兩棵樹(shù)，同時(shí)將新得到的樹(shù)加入F中；中； 重復(fù)、，直到重復(fù)、，直到F只含一顆樹(shù)為止。只含一顆樹(shù)為止。構(gòu)造構(gòu)造Huffman樹(shù)時(shí)樹(shù)時(shí)，為了規(guī)范為了規(guī)范，規(guī)定規(guī)定F=T1,T2, ,Tn中權(quán)值小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的左子樹(shù)中權(quán)值小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的左子樹(shù)，權(quán)值大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的右子樹(shù)權(quán)值大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的右子樹(shù)；在；在取值相等時(shí)

53、，取值相等時(shí)，深度小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)深度小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的左子樹(shù)的左子樹(shù)，深度大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的深度大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的右子樹(shù)右子樹(shù)。 圖圖6-25是權(quán)值集合是權(quán)值集合W=8, 3, 4, 6, 5, 5構(gòu)造構(gòu)造Huffman樹(shù)的過(guò)程樹(shù)的過(guò)程。所構(gòu)造的所構(gòu)造的Huffman樹(shù)的樹(shù)的WPL是是： WPL=6 2+3 3+4 3+8 2+5 3+5 3 =79345568第一步第一步5568第二步第二步34768第三步第三步34755108第四步第四步5510634713第六步第六步1111100000855101863471331圖圖6-25 Huff

54、man樹(shù)的構(gòu)造過(guò)程樹(shù)的構(gòu)造過(guò)程第五步第五步85510186347136.6.2 赫夫曼編碼及其算法赫夫曼編碼及其算法1 Huffman編碼編碼 在電報(bào)收發(fā)等數(shù)據(jù)通訊中在電報(bào)收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符轉(zhuǎn)換成由二進(jìn)制字符0、1組成的字符串來(lái)傳輸組成的字符串來(lái)傳輸。為了使為了使收發(fā)的速度提高收發(fā)的速度提高，就要求電文就要求電文編碼要盡可能地短編碼要盡可能地短。此外，。此外，要設(shè)計(jì)要設(shè)計(jì)長(zhǎng)短不等長(zhǎng)短不等的編碼，還必須保證的編碼，還必須保證任意字符的編碼都任意字符的編碼都不是另一個(gè)字符編碼的前綴不是另一個(gè)字符編碼的前綴，這種編碼稱(chēng)為，這種編碼稱(chēng)為前綴編碼前綴

55、編碼。 Huffman樹(shù)可以用來(lái)構(gòu)造編碼長(zhǎng)度不等且譯碼不樹(shù)可以用來(lái)構(gòu)造編碼長(zhǎng)度不等且譯碼不產(chǎn)生二義性的編碼產(chǎn)生二義性的編碼。 設(shè)電文中的字符集設(shè)電文中的字符集C=c1,c2, ,ci, ,cn，各個(gè)字，各個(gè)字符出現(xiàn)的次數(shù)或頻度集符出現(xiàn)的次數(shù)或頻度集W=w1,w2, ,wi, ,wn。以以字符集字符集C作為葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)，次數(shù)或頻度集次數(shù)或頻度集W作為結(jié)點(diǎn)的作為結(jié)點(diǎn)的權(quán)值權(quán)值來(lái)構(gòu)造來(lái)構(gòu)造 Huffman樹(shù)樹(shù)。規(guī)定。規(guī)定Huffman樹(shù)中左分支代樹(shù)中左分支代表表“0”，右分支代表，右分支代表“1” 。 從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷的路徑分支上的從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷的路徑分支上的“0”

56、或或“1”所組成的字符串所組成的字符串，為該結(jié)點(diǎn)所對(duì)應(yīng)的編碼為該結(jié)點(diǎn)所對(duì)應(yīng)的編碼，稱(chēng)之為稱(chēng)之為Huffman編碼編碼。 由于每個(gè)字符都是葉子結(jié)點(diǎn)，不可能出現(xiàn)在根結(jié)點(diǎn)由于每個(gè)字符都是葉子結(jié)點(diǎn)，不可能出現(xiàn)在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的Huffman編編碼不可能是另一個(gè)字符的碼不可能是另一個(gè)字符的Huffman編碼的前綴編碼的前綴。Huffman編碼方法編碼方法 若字符集若字符集C=a, b, c, d, e, f所對(duì)應(yīng)的權(quán)值集合為所對(duì)應(yīng)的權(quán)值集合為W=8, 3, 4, 6, 5, 5，如圖，如圖6-25所示所示，則字符，則字符a,b, c,d,

57、 e,f所對(duì)應(yīng)的所對(duì)應(yīng)的Huffman編碼分別是編碼分別是：10，010，011，00 ，110，111。2 Huffman編碼算法實(shí)現(xiàn)編碼算法實(shí)現(xiàn)(1) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) Huffman樹(shù)中沒(méi)有度為樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)棵有的結(jié)點(diǎn)棵有n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)的的Huffman樹(shù)共有樹(shù)共有2n-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，則可存儲(chǔ)在大小為，則可存儲(chǔ)在大小為2n-1的一維數(shù)組中。實(shí)現(xiàn)編碼的結(jié)點(diǎn)結(jié)構(gòu)如圖的一維數(shù)組中。實(shí)現(xiàn)編碼的結(jié)點(diǎn)結(jié)構(gòu)如圖6-26所示所示。原因原因： 求編碼需從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路求編碼需從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑；徑； 譯碼需從根結(jié)點(diǎn)出發(fā)走一條到葉子結(jié)點(diǎn)的路徑。譯碼

58、需從根結(jié)點(diǎn)出發(fā)走一條到葉子結(jié)點(diǎn)的路徑。 結(jié)點(diǎn)類(lèi)型定義結(jié)點(diǎn)類(lèi)型定義：#define MAX 200 /* Max_Node2n-1 */ struct HTNode unsigned int Weight ; /* 權(quán)值域權(quán)值域 */unsinged int Parent , Lchild , Rchild ; ;Weight Parent Lchild RchildWeight：權(quán)值域；：權(quán)值域； Parent：雙親結(jié)點(diǎn)下標(biāo)：雙親結(jié)點(diǎn)下標(biāo)Lchild, Rchild：分別標(biāo)識(shí)左：分別標(biāo)識(shí)左、右子樹(shù)的下標(biāo)右子樹(shù)的下標(biāo)圖圖6-26 Huffman編碼的結(jié)點(diǎn)結(jié)構(gòu)編碼的結(jié)點(diǎn)結(jié)構(gòu)算法算法實(shí)現(xiàn)實(shí)現(xiàn)void Create_Huffman(unsigned n, HTNode HT , unsigned m) /* 創(chuàng)建一棵葉子結(jié)點(diǎn)數(shù)為創(chuàng)建一棵葉子結(jié)點(diǎn)數(shù)為n的的Huffman樹(shù)樹(shù) */ unsigned int w ; int k , j ;for (k=1 ; km ; k+) if (k=n) coutw ;HTk.weight=w ; /*