第6章 樹(shù)和二叉樹(shù)課件

第6章樹(shù)和二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。直觀地，樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息；在分析算法的行為時(shí)，可用樹(shù)來(lái)描述其執(zhí)行過(guò)程等等。本章將詳細(xì)討論樹(shù)和二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)，主要介紹樹(shù)和二叉樹(shù)的概念、術(shù)語(yǔ)，二叉樹(shù)的遍歷算法。樹(shù)和二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)以及建立在各種存儲(chǔ)結(jié)構(gòu)上的操作及應(yīng)用等。第6章樹(shù)和二叉樹(shù)6.1

樹(shù)的基本概念1樹(shù)的定義

樹(shù)(Tree)是n(n≧0)個(gè)結(jié)點(diǎn)的有限集合T，若n=0時(shí)稱為空樹(shù)，否則：⑴有且只有一個(gè)特殊的稱為樹(shù)的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹(shù)，稱其為根的子樹(shù)(Subtree)。這是樹(shù)的遞歸定義，即用樹(shù)來(lái)定義樹(shù)。

6.1.1

樹(shù)的定義和基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)A(a)只有一個(gè)根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM(b)一般的樹(shù)(b)是有13個(gè)結(jié)點(diǎn)的樹(shù)，其中A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：T1、T2和T3；T1、T2和T3都是根A的子樹(shù)，且本身也是一棵樹(shù)。T1T2T3對(duì)于T1,，其根為B，其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集：T11和T12。T11T12第6章樹(shù)和二叉樹(shù)上述樹(shù)結(jié)構(gòu)定義加上樹(shù)的一些基本操作就構(gòu)成了抽象數(shù)據(jù)類(lèi)型樹(shù)的定義。ADTTree{

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹(shù)；若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若D-{root}≠Φ，則存在D-{root}的一個(gè)劃分D1，D2，D3，…，Dm(m>0)，對(duì)任意j≠k(1<=j,k<=m)有Dj∩Dk=Φ，且對(duì)任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H；（3）對(duì)應(yīng)于D-{root}的劃分，H-{<root,x1>,<root,x2>,…,<root,xm>}有唯一的一個(gè)劃分H1，H2，…，Hm(m>0)，對(duì)任意j≠k(1≤j，k≤m)有Hj∩Hk=Φ，Hi是Di上的二元關(guān)系，（Di,{Hi}）是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。

基本操作P:書(shū)P119頁(yè)第6章樹(shù)和二叉樹(shù)樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。ABCDEFGHIJKLM(b)一般的樹(shù)2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)稱為結(jié)點(diǎn)的度。ABCDEFGHIJKLM(b)一般的樹(shù)結(jié)點(diǎn)A的度為3。結(jié)點(diǎn)B的度為2。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。ABCDEFGHIJKLM(b)一般的樹(shù)結(jié)點(diǎn)F、G、I、J、K、L和M均為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。ABCDEFGHIJKLM(b)一般的樹(shù)結(jié)點(diǎn)A、B、C、D、E和H均為分支結(jié)點(diǎn)。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)樹(shù)的度：是樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。ABCDEFGHIJKLM(b)一般的樹(shù)結(jié)點(diǎn)A、D的度為3；結(jié)點(diǎn)B的度為2；結(jié)點(diǎn)C的度為1；結(jié)點(diǎn)E的度為2；結(jié)點(diǎn)H的度為1；結(jié)點(diǎn)F、G、I、J、K、L和M的度為0。所以，樹(shù)（b）的度為3。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)孩子（子結(jié)點(diǎn)）：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子。ABCDEFGHIJKLM(b)一般的樹(shù)例如：結(jié)點(diǎn)B的子樹(shù)有兩棵，這兩棵子樹(shù)的根分別為E和F，則稱E和F為結(jié)點(diǎn)B的孩子（或子結(jié)點(diǎn)）。雙親（或父結(jié)點(diǎn)）：相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。反之，結(jié)點(diǎn)B稱為其孩子E和F的雙親。EF2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)兄弟：同一個(gè)雙親的孩子之間互稱兄弟。ABCDEFGHIJKLM(b)一般的樹(shù)2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。ABCDEFGHIJKLM(b)一般的樹(shù)結(jié)點(diǎn)K和L的祖先為：A、B和E。結(jié)點(diǎn)H、I和J的祖先為：A和D。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。ABCDEFGHIJKLM(b)一般的樹(shù)H、I、J和M都可稱為結(jié)點(diǎn)D的子孫。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第l層，則其子樹(shù)的根就在第l+1層。ABCDEFGHIJKLM(b)一般的樹(shù)第一層第二層第三層第四層堂兄弟：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。深度：樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度。若將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的（即不能互換），則稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)。2

樹(shù)的基本術(shù)語(yǔ)第6章樹(shù)和二叉樹(shù)森林：m(m>=0)棵互不相交的樹(shù)的集合。CGBEFKLDHIJM第6章樹(shù)和二叉樹(shù)3樹(shù)的表示形式⑴倒懸樹(shù)。是最常用的表示形式，如書(shū)上圖6.1(b)。⑵嵌套集合。是一些集合的集體，對(duì)于任何兩個(gè)集合，或者不相交，或者一個(gè)集合包含另一個(gè)集合。圖6-2(a)是書(shū)上圖6.1(b)樹(shù)的嵌套集合形式。⑶廣義表形式。圖6-2(b)是樹(shù)的廣義表形式。⑷凹入法表示形式。見(jiàn)P120

樹(shù)的表示方法的多樣化說(shuō)明了樹(shù)結(jié)構(gòu)的重要性。第6章樹(shù)和二叉樹(shù)圖6-2

樹(shù)的表示形式(a)

嵌套集合形式(b)廣義表形式(A(B(E(K,L),F),C(G),D(H(M),I,J)))HIJDFBKLECMGA第6章樹(shù)和二叉樹(shù)6.2

二叉樹(shù)6.2.1二叉樹(shù)的定義1

二叉樹(shù)的定義二叉樹(shù)（BinaryTree）是另一種樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。第6章樹(shù)和二叉樹(shù)

二叉樹(shù)在樹(shù)結(jié)構(gòu)中起著非常重要的作用。因?yàn)槎鏄?shù)結(jié)構(gòu)簡(jiǎn)單，存儲(chǔ)效率高，樹(shù)的操作算法相對(duì)簡(jiǎn)單，且任何樹(shù)都很容易轉(zhuǎn)化成二叉樹(shù)結(jié)構(gòu)。上節(jié)中引入的有關(guān)樹(shù)的術(shù)語(yǔ)也都適用于二叉樹(shù)。2

二叉樹(shù)的基本形態(tài)二叉樹(shù)有5種基本形態(tài)，如圖6-3所示。AAAA(a)(b)(c)(d)(e)(a)空二叉樹(shù)(b)單結(jié)點(diǎn)二叉樹(shù)(c)右子樹(shù)為空(d)左子樹(shù)為空(e)左、右子樹(shù)都不空?qǐng)D6-3

二叉樹(shù)的基本形態(tài)第6章樹(shù)和二叉樹(shù)6.2.2二叉樹(shù)的性質(zhì)（性質(zhì)1和性質(zhì)2）性質(zhì)1

在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>=1）。利用數(shù)學(xué)歸納法證明：i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然有2i-1=20=1。

假設(shè)i=k時(shí)命題成立，即第k層上至多有2k-1個(gè)結(jié)點(diǎn)，那么對(duì)于i=k+1來(lái)說(shuō)，至多有2k-1·2個(gè)結(jié)點(diǎn)，即第k+1層上至多有2k=2(k+1)-1個(gè)結(jié)點(diǎn)，命題成立。性質(zhì)2深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。（k>=1）證明1：由性質(zhì)1可知，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為∑(第i層上的最大結(jié)點(diǎn)數(shù))=∑2i-1證明2：第1層上至多有1個(gè)結(jié)點(diǎn)，第2層上至多有2個(gè)結(jié)點(diǎn)，第i層上至多有1·2i-1個(gè)結(jié)點(diǎn)，構(gòu)成一等比數(shù)列，則深度為k的二叉樹(shù)至多有∑(1+2+4+…+2k-1)=∑2i-1=1(1-2k)/(1-2)=2k-1。第6章樹(shù)和二叉樹(shù)性質(zhì)3對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

設(shè)n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù)。則二叉樹(shù)T的所有結(jié)點(diǎn)數(shù)為n=n0+n1+n2

(1)再看二叉樹(shù)的分支數(shù)。除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)B為分支總數(shù)，則n=B+1。由于這些分支是由度為1或2的結(jié)點(diǎn)（包括根結(jié)點(diǎn)）射出的，所以又有B=n1+2n2。于是得二叉樹(shù)T的結(jié)點(diǎn)總數(shù)為n=n1+2n2+1(2)由（1）、（2）兩式可得n0=n2+1第6章樹(shù)和二叉樹(shù)

完全二叉樹(shù)和滿二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)（除最后一層外其余各層上所有結(jié)點(diǎn)的度均為2）的二叉樹(shù)稱為滿二叉樹(shù)。完全二叉樹(shù)和滿二叉樹(shù)第6章樹(shù)和二叉樹(shù)123456789101112131415

可以對(duì)滿二叉樹(shù)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，自左至右。完全二叉樹(shù)

深度為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í)，稱之為完全二叉樹(shù)。12345678（1）完全二叉樹(shù)的葉子結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層（即倒數(shù)第一層和倒數(shù)第二層上）出現(xiàn)。（2）對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。（即只能缺少滿二叉樹(shù)中最大層次上右方連續(xù)的若干個(gè)葉子結(jié)點(diǎn)。）第6章樹(shù)和二叉樹(shù)894101151213614157213894101152112673(a)滿二叉樹(shù)(b)完全二叉樹(shù)1362455674213(c)非完全二叉樹(shù)圖6-4特殊形態(tài)的二叉樹(shù)第6章樹(shù)和二叉樹(shù)完全二叉樹(shù)的性質(zhì)（性質(zhì)4與性質(zhì)5）完全二叉樹(shù)的兩個(gè)重要特性性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為└log2n┘+1。不大于其本身的最大整數(shù)證明：假設(shè)完全二叉樹(shù)的深度為k，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有2k-1-1<n<=2k-1即n比k-1層滿二叉樹(shù)的結(jié)點(diǎn)數(shù)多，否則與k層的假設(shè)矛盾。此完全二叉樹(shù)的結(jié)點(diǎn)數(shù)至多與具有相同深度（k）的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)一樣多（即為特殊的完全二叉樹(shù)。）

或2k-1<=n<2k具有最少結(jié)點(diǎn)數(shù)的深度為k的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)（即最后一層上只有最左邊一個(gè)葉子結(jié)點(diǎn)的情況）。比深度為k的滿二叉樹(shù)還多一個(gè)結(jié)點(diǎn)的表達(dá)式就是2k。于是k-1<=log2n<k因?yàn)閗是整數(shù)，所以k=└log2n┘+1。性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為└log2n┘+1）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第└log2n┘+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i（1<=i<=n），有（1）如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親PARENT（i）是結(jié)點(diǎn)└i/2┘。（2）如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子LCHILD（i）是結(jié)點(diǎn)2i。（3）如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子RCHILD（i）是結(jié)點(diǎn)2i+1。第6章樹(shù)和二叉樹(shù)6.2.3

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1

順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義：#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;

用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下、自左至右”存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。

第6章樹(shù)和二叉樹(shù)abcdhiejklfg(a)完全二叉樹(shù)01234567891011abcdefghijkl

(c)完全二叉樹(shù)的順序存儲(chǔ)形式圖6-6二叉樹(shù)及其順序存儲(chǔ)形式對(duì)于完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為i-1的分量中，如圖6-6(c)所示。對(duì)于一般的二叉樹(shù)，又如何存儲(chǔ)呢？第6章樹(shù)和二叉樹(shù)例題1：現(xiàn)有如圖A所示的一般二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，請(qǐng)畫(huà)出對(duì)應(yīng)的二叉樹(shù)的邏輯結(jié)構(gòu)對(duì)應(yīng)的圖。圖A紅黃蘭大中小正負(fù)紅黃蘭大中小正負(fù)紅黃蘭大正小中負(fù)結(jié)論：對(duì)應(yīng)的邏輯結(jié)構(gòu)圖不唯一。01234567紅黃蘭大中小正負(fù)第6章樹(shù)和二叉樹(shù)例題2：現(xiàn)有如圖B所示的一般二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，請(qǐng)畫(huà)出對(duì)應(yīng)的二叉樹(shù)的邏輯結(jié)構(gòu)對(duì)應(yīng)的圖。圖B0123456789101112紅黃蘭大0中小正0000負(fù)紅黃蘭大0中小正0000負(fù)去掉實(shí)際上不存在的0結(jié)點(diǎn)所得圖結(jié)構(gòu)為紅黃蘭大中小正負(fù)結(jié)論：所得邏輯結(jié)構(gòu)對(duì)應(yīng)的圖形具有唯一性。因?yàn)椴捎昧送耆鏄?shù)存儲(chǔ)的思想。第6章樹(shù)和二叉樹(shù)(b)非完全二叉樹(shù)abcdefgh???012345678910abcde?h?

?

fg(d)非完全二叉樹(shù)的順序存儲(chǔ)形式圖6-6二叉樹(shù)及其順序存儲(chǔ)形式因此，對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中，如圖6-6(d)所示。第6章樹(shù)和二叉樹(shù)評(píng)價(jià)：在最壞情況下，一個(gè)深度為K且只有K個(gè)結(jié)點(diǎn)的單支樹(shù)（樹(shù)中不存在度為2的結(jié)點(diǎn)）即需要長(zhǎng)度為2k-1的一維數(shù)組。例如（最壞情況）：有如圖所示的5層單支二叉樹(shù)。00000000000000000000000000EDCBA欲采用順序存儲(chǔ)結(jié)構(gòu)，需將其與5層完全二叉樹(shù)對(duì)應(yīng)起來(lái)。此時(shí)的結(jié)點(diǎn)數(shù)為25-1=32-1=31。結(jié)論：雖然這棵二叉樹(shù)總共只有5個(gè)結(jié)點(diǎn)，但需長(zhǎng)度為31的一維數(shù)組存放。為了存儲(chǔ)一般二叉樹(shù)，現(xiàn)介紹二叉樹(shù)的另一種存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為2k-1的一維數(shù)組。第6章樹(shù)和二叉樹(shù)2鏈?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)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域，如圖6-7(a)所示。typedefstruct{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針

}BiTNode,*BiTree;LchilddataRchild(a)二叉鏈表結(jié)點(diǎn)圖6-7鏈表結(jié)點(diǎn)結(jié)構(gòu)形式第6章樹(shù)和二叉樹(shù)②三叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖6-7(b)所示。typedefstruct{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指針structTriTNode*parent;//雙親指針

}TriTNode,*TriTree;LchilddataparentRchild(b)三叉鏈表結(jié)點(diǎn)圖6-7鏈表結(jié)點(diǎn)結(jié)構(gòu)形式第6章樹(shù)和二叉樹(shù)(2)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)形式例如有一棵一般的二叉樹(shù)，如圖6-8(a)所示。以二叉鏈表和三叉鏈表方式存儲(chǔ)的結(jié)構(gòu)圖分別如圖6-8(b)、6-8(c)所示。圖6-8二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(a)二叉樹(shù)afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T第6章樹(shù)和二叉樹(shù)6.3

遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)(TraversingBinaryTree)：是指按指定的規(guī)律對(duì)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。所謂訪問(wèn)是指對(duì)結(jié)點(diǎn)做某種處理。如：輸出信息、修改結(jié)點(diǎn)的值等。二叉樹(shù)是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都可能有左、右兩棵子樹(shù)，因此，需要尋找一種規(guī)律，使二叉樹(shù)上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。二叉樹(shù)的基本組成：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)。若能依次遍歷這三部分，就是遍歷了二叉樹(shù)。第6章樹(shù)和二叉樹(shù)若以L、D、R分別表示遍歷左子樹(shù)、遍歷根結(jié)點(diǎn)和遍歷右子樹(shù)，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定先左后右，則只有前三種情況三種情況，分別是：DLR——先(根)序遍歷。LDR——中(根)序遍歷。LRD——后(根)序遍歷。對(duì)于二叉樹(shù)的遍歷，有遞歸遍歷算法和非遞歸遍歷算法。在此我們只介紹遞歸遍歷算法。遞歸遍歷算法具有非常清晰的結(jié)構(gòu)，但初學(xué)者往往難以接受或懷疑，不敢使用。實(shí)際上，遞歸算法是由系統(tǒng)通過(guò)使用堆棧來(lái)實(shí)現(xiàn)控制的。而非遞歸算法中的控制是由設(shè)計(jì)者定義和使用堆棧來(lái)實(shí)現(xiàn)的。第6章樹(shù)和二叉樹(shù)6.3.1

遍歷二叉樹(shù)1

先序遍歷二叉樹(shù)遞歸算法算法的遞歸定義是：

若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴訪問(wèn)根結(jié)點(diǎn)；⑵先序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑶先序遍歷右子樹(shù)(遞歸調(diào)用本算法)。第6章樹(shù)和二叉樹(shù)寫(xiě)出如下二叉樹(shù)的先序遍歷結(jié)點(diǎn)序列：abcedfghij此二叉樹(shù)先序遍歷的結(jié)點(diǎn)序列為：a-b-c-e-d-f-h-g-i-j第6章樹(shù)和二叉樹(shù)先序遍歷的遞歸算法voidPreorderTraverse(BiTNode*T){if(T!=NULL){visit(T->data);/*訪問(wèn)根結(jié)點(diǎn)*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}說(shuō)明：visit()函數(shù)是訪問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問(wèn)題而定。樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T來(lái)指向。第6章樹(shù)和二叉樹(shù)先序遍歷二叉樹(shù)基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)。//-----------二叉樹(shù)的二叉鏈表存儲(chǔ)表示-------------typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針

}BiTNode,*BiTree;StatusPreOrdefTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。//先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)函數(shù)Visit。//最簡(jiǎn)單的Visit函數(shù)是：

StatusPrintElement(TElemTypee){//輸出元素e的值

printf(e);//實(shí)際應(yīng)用時(shí)，加上格式串

returnOK;}第6章樹(shù)和二叉樹(shù)//調(diào)用實(shí)例：PreOrderTraverse(T,PrintElement);if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse第6章樹(shù)和二叉樹(shù)2

中序遍歷二叉樹(shù)遞歸算法算法的遞歸定義是：

若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵訪問(wèn)根結(jié)點(diǎn)；⑶中序遍歷右子樹(shù)(遞歸調(diào)用本算法)。第6章樹(shù)和二叉樹(shù)例題：寫(xiě)出如下二叉樹(shù)中序遍歷的結(jié)點(diǎn)序列。abcedfghij中序遍歷的結(jié)點(diǎn)序列為：e-c-b-h-f-d-j-i-g-a第6章樹(shù)和二叉樹(shù)中序遍歷的遞歸算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問(wèn)根結(jié)點(diǎn)*/InorderTraverse(T->Rchild);}}

第6章樹(shù)和二叉樹(shù)3后序遍歷二叉樹(shù)遞歸算法算法的遞歸定義是：

若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(shù)(遞歸調(diào)用本算法)；⑶訪問(wèn)根結(jié)點(diǎn)。第6章樹(shù)和二叉樹(shù)后序遍歷二叉樹(shù)的定義：若二叉樹(shù)為空，則空操作；否則（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)；abcedfghij后序遍歷的結(jié)點(diǎn)序列為：e-c-h-f-j-i-g-d-b-a第6章樹(shù)和二叉樹(shù)后序遍歷的遞歸算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問(wèn)根結(jié)點(diǎn)*/

}}

遍歷二叉樹(shù)的算法中基本操作是訪問(wèn)結(jié)點(diǎn)，因此，無(wú)論是哪種次序的遍歷，對(duì)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為O(n)。第6章樹(shù)和二叉樹(shù)如圖6-9所示的二叉樹(shù)表示表達(dá)式：(a+b*(c-d)-e/f)按不同的次序遍歷此二叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序排列起來(lái)的次序是：其先序序列為：-+a*b-cd/ef(波蘭式)

其中序序列為：a+b*c-d-e/f

其后序序列為：abcd-*+ef/-（逆波蘭式）－/fe-dcb*a+圖6-9

表達(dá)式(a+b*(c-d)-e/f)二叉樹(shù)第6章樹(shù)和二叉樹(shù)通過(guò)二叉樹(shù)只能找到結(jié)點(diǎn)的左、右孩子，不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼結(jié)點(diǎn)。要獲取結(jié)點(diǎn)前驅(qū)和后繼只能通過(guò)遍歷。遍歷二叉樹(shù)是按一定的規(guī)則將樹(shù)中的結(jié)點(diǎn)排列成一個(gè)線性序列，即是對(duì)非線性結(jié)構(gòu)的線性化操作。如何保存遍歷過(guò)程中動(dòng)態(tài)得到的每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼(第一個(gè)和最后一個(gè)除外)?一個(gè)最簡(jiǎn)單的辦法是在每個(gè)結(jié)點(diǎn)上增加兩個(gè)指針域fwd和bkwd，分別指示結(jié)點(diǎn)在依任一次序遍歷時(shí)得到的前驅(qū)和后繼信息。顯然，這樣做使得結(jié)構(gòu)的存儲(chǔ)密度大大降低。

注意到，一棵二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則有n-1條邊(指針連線)，而n個(gè)結(jié)點(diǎn)共有2n個(gè)指針域(Lchild和Rchild)，顯然有n+1個(gè)空閑指針域未用。則可以利用這些空閑的指針域來(lái)存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。6.3.2

線索二叉樹(shù)第6章樹(shù)和二叉樹(shù)對(duì)結(jié)點(diǎn)的指針域做如下規(guī)定：◆若結(jié)點(diǎn)有左孩子，則Lchild指向其左孩子，否則，指向其直接前驅(qū)；◆若結(jié)點(diǎn)有右孩子，則Rchild指向其右孩子，否則，指向其直接后繼；為避免混淆,對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域，如圖6-10所示。LchildLTagdataRchildRTag圖6-10線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)0：Lchild域指示結(jié)點(diǎn)的左孩子1：Lchild域指示結(jié)點(diǎn)的前驅(qū)LTag=0：Rchild域指示結(jié)點(diǎn)的右孩子1：Rchild域指示結(jié)點(diǎn)的后繼RTag=第6章樹(shù)和二叉樹(shù)用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹(shù)稱之為線索二叉樹(shù)。線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)與示例typedefstructBiThrNode{TElemTypedata;structBiTreeNode*Lchild,*Rchild;intLTag,RTag;}BiThrNode;

如圖6-11是二叉樹(shù)及相應(yīng)的各種線索樹(shù)示例。第6章樹(shù)和二叉樹(shù)AFHIEGBDC(a)二叉樹(shù)

(b)先序線索樹(shù)的邏輯形式結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDCNIL(d)后序線索樹(shù)的邏輯形式結(jié)點(diǎn)序列：DBGEHIFCA(c)中序線索樹(shù)的邏輯形式結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL第6章樹(shù)和二叉樹(shù)

0A0

0B1

0C0?

1D1

0E1

0F0

1G1

1H1

1F1?(e)中序線索樹(shù)的鏈表結(jié)構(gòu)圖6-11線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)說(shuō)明：畫(huà)線索二叉樹(shù)時(shí)，實(shí)線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅(qū)或直接后繼。在線索樹(shù)上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。第6章樹(shù)和二叉樹(shù)如何在線索樹(shù)中找結(jié)點(diǎn)的直接后繼?以圖6-11(c)所示的中序線索樹(shù)為例：◆樹(shù)中所有葉子結(jié)點(diǎn)的右鏈都是線索。右鏈直接指示了結(jié)點(diǎn)的直接后繼，如結(jié)點(diǎn)G的直接后繼是結(jié)點(diǎn)E?！魳?shù)中一部分非葉子結(jié)點(diǎn)的右鏈都是指針，無(wú)法得到后繼信息。根據(jù)中序遍歷的規(guī)律，這些結(jié)點(diǎn)的直接后繼是遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)，即右子樹(shù)中最左下的(葉子)結(jié)點(diǎn)。如結(jié)點(diǎn)C的直接后繼：沿右指針找到右子樹(shù)的根結(jié)點(diǎn)F，然后沿左鏈往下直到Ltag=1的結(jié)點(diǎn)即為C的直接后繼結(jié)點(diǎn)H。AFHIEGBDC(a)二叉樹(shù)

(c)中序線索樹(shù)的邏輯形式結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNIL第6章樹(shù)和二叉樹(shù)如何在線索樹(shù)中找結(jié)點(diǎn)的直接前驅(qū)?若結(jié)點(diǎn)的Ltag=1，則左鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷左子樹(shù)時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)(即沿左子樹(shù)中最右往下的結(jié)點(diǎn))為其直接前驅(qū)結(jié)點(diǎn)。為方便起見(jiàn)，依照線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)的線索鏈表上也添加一個(gè)頭結(jié)點(diǎn)，并令其lchild域的指針指向二叉樹(shù)的根結(jié)點(diǎn)，其rchild域的指針指向中序遍歷時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)。反之，令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchild域指針和最后一個(gè)結(jié)點(diǎn)rchild域的指針均指向頭結(jié)點(diǎn)。第6章樹(shù)和二叉樹(shù)6.4

樹(shù)與森林

本節(jié)將討論樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)及森林與二叉樹(shù)之間的相互轉(zhuǎn)換、樹(shù)的遍歷等。第6章樹(shù)和二叉樹(shù)6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)根據(jù)應(yīng)用的不同而不同。

在大量的應(yīng)用中，人們?cè)褂枚喾N形式的存儲(chǔ)結(jié)構(gòu)來(lái)表示樹(shù)。這里，我們介紹三種常用的鏈表結(jié)構(gòu)。1

雙親表示法(順序存儲(chǔ)結(jié)構(gòu))

用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器(整數(shù)域)

，用以指示雙親結(jié)點(diǎn)的位置(下標(biāo)值)。數(shù)組元素及數(shù)組的類(lèi)型定義如下：第6章樹(shù)和二叉樹(shù)//-----------------樹(shù)的雙親表存儲(chǔ)結(jié)構(gòu)----#defineMAX_TREE_SIZE100typedefstructPTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;intparent;}PTNode;typedefstruct{//樹(shù)結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE]；

intr,n;//根的位置和結(jié)點(diǎn)數(shù)}PTree;第6章樹(shù)和二叉樹(shù)圖6-13所示是一棵樹(shù)及其雙親表示的存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)結(jié)構(gòu)利用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)。可以方便地直接找到任一結(jié)點(diǎn)的父結(jié)點(diǎn)，但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組。FGHKRABCDE圖6-13樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)R-10A01B02C03D14E15F36G67H68K69第6章樹(shù)和二叉樹(shù)2孩子鏈表表示法

樹(shù)中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其一棵子樹(shù)的根結(jié)點(diǎn)。有兩種結(jié)點(diǎn)結(jié)構(gòu)。⑴定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)

指針域的數(shù)目就是樹(shù)的度。其特點(diǎn)是：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯。結(jié)點(diǎn)結(jié)構(gòu)如圖6-14(a)所示。由于樹(shù)可能有很多結(jié)點(diǎn)的度會(huì)小于d，所以鏈表中有很多空鏈域，空間較浪費(fèi)。⑵不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)

樹(shù)中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度，如圖6-14(b)所示。沒(méi)有多余的指針域，但操作不便。第6章樹(shù)和二叉樹(shù)圖6-14孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)datachild1child2

?childn(a)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)(b)不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)datadegreechild1child2

?childk⑶復(fù)合鏈表結(jié)構(gòu)

另一種方法是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）。而n個(gè)頭指針又組成一個(gè)線性表，為了便于查找，可采用順序存儲(chǔ)結(jié)構(gòu)。第6章樹(shù)和二叉樹(shù)//---------樹(shù)的孩子鏈表存儲(chǔ)表示------typedefstructCTNode{//孩子結(jié)點(diǎn)

intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子鏈表頭指針}CTBox;Typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根的位置}CTree;第6章樹(shù)和二叉樹(shù)RABCDEFGKHAB^CD^RE^FG^H^K^012345678935^6^012^789^

與雙親表示法相反，孩子表示法便于那些涉及孩子的操作的實(shí)現(xiàn)，卻不適用于PARENT(T,x)操作。為此，我們可以把雙親表示法和孩子表示法結(jié)合起來(lái)，即將雙親表示和孩子鏈表結(jié)合在一起。圖6-13樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)圖6.15（a）孩子鏈表第6章樹(shù)和二叉樹(shù)4A4B^4C0D^-1R0E^2F6G^6H^6K^012345678935^6^012^789^RABCDEFGKH圖6-13樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)圖6.15（b）帶雙親的孩子鏈表第6章樹(shù)和二叉樹(shù)3孩子兄弟表示法(二叉樹(shù)表示法)

以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)形式如圖6-17(a)所示。兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類(lèi)型定義如下：//--------------樹(shù)的二叉鏈表（孩子—兄弟）存儲(chǔ)表示---------typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;圖6-17(b)所示樹(shù)的孩子兄弟表示的存儲(chǔ)結(jié)構(gòu)如圖6-17(c)。第6章樹(shù)和二叉樹(shù)RABCDEFGKHR^A^D^B^E^C^F^^G^H^H^利用這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹(shù)的操作。孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchilddatanextsibing(a)結(jié)點(diǎn)結(jié)構(gòu)第6章樹(shù)和二叉樹(shù)6.4.2

森林與二叉樹(shù)的轉(zhuǎn)換由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。也就是說(shuō)，給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)?！?/p>

從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而已。

◆

從樹(shù)的二叉鏈表表示的定義可知，任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。第6章樹(shù)和二叉樹(shù)若把森林中第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟，則同樣可導(dǎo)出森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系。森林轉(zhuǎn)換成二叉樹(shù)第6章樹(shù)和二叉樹(shù)轉(zhuǎn)換步驟：

①將F={T1,T2,?,Tn}中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)。②按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)，依次類(lèi)推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹(shù)的根結(jié)點(diǎn)，如圖6-21所示。ACBDGMLHK(a)森林圖6-21森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程(b)森林中每棵樹(shù)對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM(c)森林對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM第6章樹(shù)和二叉樹(shù)二叉樹(shù)轉(zhuǎn)換成森林若B=(root，LB，RB)是一棵二叉樹(shù)，則可以將其轉(zhuǎn)換成由若干棵樹(shù)構(gòu)成的森林：F={T1,T2,?,Tn}。轉(zhuǎn)換算法：①若B是空樹(shù)，則F為空。②若B非空，則F中第一棵樹(shù)T1的根root(T1)就是二叉樹(shù)的根root，T1中根結(jié)點(diǎn)的子森林F1是由樹(shù)B的左子樹(shù)LB轉(zhuǎn)換而成的森林；F中除T1外其余樹(shù)組成的的森林F’={T2,T3,?,Tn}是由B右子樹(shù)RB轉(zhuǎn)換得到的森林。上述轉(zhuǎn)換規(guī)則是遞歸的，可以寫(xiě)出其遞歸算法。以下給出具體的還原步驟。第6章樹(shù)和二叉樹(shù)①去連線。將二叉樹(shù)B的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線全部去掉，得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林F中的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)，如圖6-22(b)所示。②二叉樹(shù)的還原。將各棵孤立的二叉樹(shù)按二叉樹(shù)還原為樹(shù)的方法還原成一般的樹(shù)，如圖6-22(c)所示。圖6-22二叉樹(shù)還原成森林的過(guò)程ACBDMGLHK(c)還原成森林(a)二叉樹(shù)ABCDGLKHM(b)去連線后ABCDMGLKH第6章樹(shù)和二叉樹(shù)6.4.3樹(shù)和森林的遍歷1樹(shù)的遍歷由樹(shù)結(jié)構(gòu)的定義可知，樹(shù)的遍歷有二種方法。⑴先序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹(shù)。如圖6-23的樹(shù)，先序遍歷的次序是：

ABCDEFGIJHK⑵后序遍歷：先依次后序遍歷完每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。如圖6-23的樹(shù)，后序遍歷的次序是：CDBFIJGHEKAABDCKGJIFHE圖6-23樹(shù)第6章樹(shù)和二叉樹(shù)說(shuō)明：◆樹(shù)的先序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的先序遍歷相同?！魳?shù)的后序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的中序遍歷相同。ABDCKGJIFHE圖6-23樹(shù)ABDCKGJIFHE圖6-24圖6-23對(duì)應(yīng)的二叉樹(shù)先序遍歷的次序是：ABCDEFGIJHK后序遍歷的次序是：CDBFIJGHEKA第6章樹(shù)和二叉樹(shù)2森林的遍歷設(shè)F={T1,T2,?,Tn}是森林，對(duì)F的遍歷有二種方法。⑴先序遍歷：按先序遍歷樹(shù)的方式依次遍歷F中的每棵樹(shù)。⑵中序遍歷：按后序遍歷樹(shù)的方式依次遍歷F中的每棵樹(shù)。如書(shū)上P138頁(yè)圖6.17的森林。第6章樹(shù)和二叉樹(shù)6.6

赫夫曼樹(shù)及其應(yīng)用赫夫曼(Huffman)樹(shù)又稱最優(yōu)樹(shù)，是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)，有著廣泛的應(yīng)用。6.6.1最優(yōu)二叉樹(shù)(Huffman樹(shù))1

基本概念①結(jié)點(diǎn)路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。②路徑長(zhǎng)度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長(zhǎng)度。③樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。第6章樹(shù)和二叉樹(shù)例圖6-23的樹(shù)。A到F：結(jié)點(diǎn)路徑AEF；路徑長(zhǎng)度(即邊的數(shù)目)2

；樹(shù)的路徑長(zhǎng)度：31+52+23=19

ABDCKGJIFHE圖6-23樹(shù)第6章樹(shù)和二叉樹(shù)④

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)的根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)(值)的乘積。權(quán)(值)：各種開(kāi)銷(xiāo)、代價(jià)、頻度等的抽象稱呼。⑤

樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記做：

WPL=w1

l1+w2

l2+?+wn

ln=∑wi

li(i=1,2,?,n)其中：n為葉子結(jié)點(diǎn)的個(gè)數(shù)；wi為第i個(gè)結(jié)點(diǎn)的權(quán)值；

li為第i個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度。⑥

Huffman樹(shù)：具有n個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值為wi)的二叉樹(shù)不止一棵，但在所有的這些二叉樹(shù)中，必定存在一棵WPL值最小的樹(shù)，稱這棵樹(shù)為Huffman樹(shù)(或稱最優(yōu)樹(shù))。第6章樹(shù)和二叉樹(shù)在許多判定問(wèn)題時(shí)，利用Huffman樹(shù)可以得到最佳判斷算法。如圖6-24是權(quán)值分別為2、3、6、7，具有4個(gè)葉子結(jié)點(diǎn)的二叉樹(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；(c)WPL=7

1+6

2+2

3+3

3=34。其中(c)的WPL值最小，可以證明是Huffman樹(shù)。236736726723(a)(b)(c)圖6-24具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)第6章樹(shù)和二叉樹(shù)②在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且新的二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；③在F中刪除這兩棵樹(shù)，同時(shí)將新得到的樹(shù)加入F中；④重復(fù)②、③，直到F只含一顆樹(shù)為止。構(gòu)造Huffman樹(shù)時(shí)，為了規(guī)范，規(guī)定F={T1,T2,?,Tn}中權(quán)值小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的左子樹(shù)，權(quán)值大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的右子樹(shù)；在取值相等時(shí)，深度小的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的左子樹(shù)，深度大的二叉樹(shù)作為新構(gòu)造的二叉樹(shù)的右子樹(shù)。2Huffman樹(shù)的構(gòu)造①根據(jù)n個(gè)權(quán)值{w1,w2,?,wn}，構(gòu)造成n棵二叉樹(shù)的集合F={T1,T2,?,Tn}，其中每棵二叉樹(shù)只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，沒(méi)有左、右子樹(shù)；第6章樹(shù)和二叉樹(shù)

圖6-25是權(quán)值集合W={8,3,4,6,5,5}構(gòu)造Huffman樹(shù)的過(guò)程。所構(gòu)造的Huffman樹(shù)的WPL是：

WPL=6

2+3

3+4

3+8

2+5

3+5

3=79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331圖6-25Huffman樹(shù)的構(gòu)造過(guò)程第五步8551018634713第6章樹(shù)和二叉樹(shù)6.6.2

赫夫曼編碼及其算法1Huffman編碼

在電報(bào)收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的字符串來(lái)傳輸。為了使收發(fā)的速度提高，就要求電文編碼要盡可能地短。此外，要設(shè)計(jì)長(zhǎng)短不等的編碼，還必須保證任意字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼。第6章樹(shù)和二叉樹(shù)Huffman樹(shù)可以用來(lái)構(gòu)造編碼長(zhǎng)度不等且譯碼不產(chǎn)生二義性的編碼。設(shè)電文中的字符集C={c1,c2,?,ci,?,cn}，各個(gè)字符出現(xiàn)的次數(shù)或頻度集W={w1,w2,?,wi,?,wn}。如在傳送電文時(shí)，希望總長(zhǎng)盡可能地短。如果設(shè)計(jì)A、B、C、D的編碼分別為0、00、1和01，則電文’ABACCDA’可轉(zhuǎn)換成總長(zhǎng)為9的字符串‘000011010’。但是，這樣的電文無(wú)法翻譯，例如傳送過(guò)去的