《《算法與數(shù)據(jù)結(jié)構(gòu)》第4章樹(shù)與二叉樹(shù)ppt.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第4章樹(shù)與二叉樹(shù)ppt.ppt（163頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu),第4章 樹(shù)與二叉樹(shù),樹(shù)和二叉樹(shù),在前兩章討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)各種運(yùn)算和操作，主要用于描述客觀世界中具有單一前趨和單一后繼的數(shù)據(jù)關(guān)系。 然而，客觀世界中的許多事物的關(guān)系并非如此簡(jiǎn)單，如人類(lèi)社會(huì)中的族譜、各種社會(huì)組織機(jī)構(gòu)、交通道路和通訊網(wǎng)絡(luò)等，其中的聯(lián)系都是較為復(fù)雜的非線性關(guān)系，宜用非線性結(jié)構(gòu)來(lái)描述其數(shù)據(jù)關(guān)系。 樹(shù)與二叉樹(shù)中，每個(gè)數(shù)據(jù)元素至多只有一個(gè)前趨，但可以有多個(gè)后繼；數(shù)據(jù)元素間的關(guān)系是一對(duì)多的層次關(guān)系，主要用于描述客觀世界中具有層次結(jié)構(gòu)的數(shù)據(jù)關(guān)系。,第4章 樹(shù)與二叉樹(shù),4.1 樹(shù)的基本概念 4.2 二叉樹(shù) 4.3 二叉樹(shù)的遍歷 4.4

2、 線索二叉樹(shù) 4.5 樹(shù)和森林 4.6 哈夫曼樹(shù),4.1 樹(shù)的基本概念,4.1.1 樹(shù)的定義及表示 4.1.2 樹(shù)的常用術(shù)語(yǔ)及運(yùn)算,樹(shù)的定義及表示,客觀世界中的許多事物的關(guān)系可以用樹(shù)來(lái)描述，如人類(lèi)社會(huì)中家族成員之間的血緣關(guān)系，以英國(guó)女王家族為例可表示成如下圖所示。 上圖看上去很像一棵倒置的樹(shù)，樹(shù)型結(jié)構(gòu)便由此而得名。,樹(shù)的遞歸定義,樹(shù)（tree）是n（n0）個(gè)結(jié)點(diǎn)的有限集合T。 當(dāng)n=0時(shí)稱(chēng)為空樹(shù)，否則稱(chēng)為非空樹(shù)。 在任一非空樹(shù)中，有且僅有一個(gè)稱(chēng)為樹(shù)的根的結(jié)點(diǎn)；除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m（m0）個(gè)互不相交的集合T1，T2，Tm，其中每個(gè)集合本身又都是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。 這是一個(gè)遞歸定

3、義，即在樹(shù)的定義中又用到了樹(shù)這個(gè)術(shù)語(yǔ)，它反映了樹(shù)的固有特性： 即一棵樹(shù)由若干棵子樹(shù)構(gòu)成，而每棵子樹(shù)又都分別由若干棵更小的子樹(shù)構(gòu)成。,樹(shù)的遞歸定義（續(xù)）,這個(gè)樹(shù)的遞歸定義可以從如下三點(diǎn)來(lái)理解： 沒(méi)有任何結(jié)點(diǎn)的樹(shù)稱(chēng)為空樹(shù)，這是樹(shù)的特例。 非空樹(shù)中至少有一個(gè)結(jié)點(diǎn)，只有一個(gè)結(jié)點(diǎn)時(shí)它就是樹(shù)的根，只有根結(jié)點(diǎn)的樹(shù)稱(chēng)為最小非空樹(shù)。 在含有多個(gè)結(jié)點(diǎn)的樹(shù)中，除根結(jié)點(diǎn)外其余結(jié)點(diǎn)構(gòu)成若干棵子樹(shù)，且各子樹(shù)間互不相交。,樹(shù)的示例,下圖中，(a)是只有一個(gè)根結(jié)點(diǎn)的樹(shù)。(b)是有六個(gè)結(jié)點(diǎn)的一般樹(shù)，其中A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：T1=B，T2=C，E，F(xiàn)，T3=D；T1、T2和T3是A的子樹(shù)，且其本身也都是一棵樹(shù)

4、；其中，T1的根為B其子樹(shù)為空樹(shù)，T3的根為D其子樹(shù)為空樹(shù)，T2的根為C剩余結(jié)點(diǎn)分成兩個(gè)互不相交的子集T21=E和T22=F，T21和T22都是C的子樹(shù)。,樹(shù)的非遞歸定義,樹(shù)的非遞歸定義可以敘述為：稱(chēng)數(shù)據(jù)結(jié)構(gòu)tree(D,R)為樹(shù)，則R中只有一個(gè)關(guān)系，且滿(mǎn)足以下條件： (1) 有且僅有一個(gè)沒(méi)有前趨的結(jié)點(diǎn)w，稱(chēng)為樹(shù)的根； (2) 除根w外的每一個(gè)結(jié)點(diǎn)都有且只有一個(gè)前趨； (3) 對(duì)于除根w外的每一個(gè)結(jié)點(diǎn)K，都有一個(gè)從根w到k的一個(gè)結(jié)點(diǎn)序列K0(w)，K1，K2，Ki-1，Ki，Kn(k)（n1），其中Ki是Ki-1的后繼。 這個(gè)非遞歸定義中的(1)和(2)容易理解；對(duì)于(3)以前一頁(yè)的圖(b)中

5、的任一結(jié)點(diǎn)如E說(shuō)明一下，從根A到E存在一個(gè)線性序列A、C、E，序列中后一個(gè)結(jié)點(diǎn)是它前面一個(gè)結(jié)點(diǎn)的后繼，即C是A的后繼，E是C的后繼。,樹(shù)的表示,通常樹(shù)的表示方法有樹(shù)形表示、嵌套集合表示、凹入表示和廣義表表示四種，如下圖所示：,4.1 樹(shù)的基本概念,4.1.1 樹(shù)的定義及表示 4.1.2 樹(shù)的常用術(shù)語(yǔ)及運(yùn)算,樹(shù)常用的基本術(shù)語(yǔ),樹(shù)的結(jié)點(diǎn)：是指一個(gè)數(shù)據(jù)元素及其若干指向其子樹(shù)的分支，通常用一個(gè)記錄或結(jié)構(gòu)體來(lái)描述，在樹(shù)形表示中用一個(gè)圓圈及短線來(lái)表示。 結(jié)點(diǎn)的度：是指結(jié)點(diǎn)擁有的子樹(shù)數(shù)目。如右圖中，結(jié)點(diǎn)A的度為3，C的度為2，B、D、E、F的度為0。 葉子或終端結(jié)點(diǎn)：是指度為0的結(jié)點(diǎn)，如右圖)中的B、D、E

6、、F都是葉子結(jié)點(diǎn)。 分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)：是指度不為0的結(jié)點(diǎn)，如右圖中的A和C結(jié)點(diǎn)；通常又把非根的分支結(jié)點(diǎn)稱(chēng)為內(nèi)部結(jié)點(diǎn)，如右圖中的C結(jié)點(diǎn)。 樹(shù)的度：是指樹(shù)中各結(jié)點(diǎn)度的最大值，如右圖中的樹(shù)的度為3。,樹(shù)常用的基本術(shù)語(yǔ)（續(xù)）,結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始，根為第一層，根的孩子為第二層，依次類(lèi)推。如右上圖中的A在第一層，B、C、D在第二層，E和F在第三層。 樹(shù)的深度或高度：是樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。如右上圖中的樹(shù)高度為3。 有序樹(shù)和無(wú)序樹(shù)：如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成是從左到右依次有序且不能交換，則稱(chēng)該樹(shù)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。如右下圖給出了兩棵不同的有序樹(shù)。 森林：是m棵互不相交的樹(shù)的集合。刪除一棵樹(shù)的

7、根就會(huì)得到由子樹(shù)構(gòu)成的森林；反之，給森林加上一個(gè)根就會(huì)變成為一棵樹(shù)。,樹(shù)的其它術(shù)語(yǔ),有時(shí)也引用家族樹(shù)中的一些習(xí)慣用語(yǔ)，如孩子、雙親、祖先、子孫、兄弟等。如稱(chēng)結(jié)點(diǎn)的子樹(shù)的根為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱(chēng)為孩子的雙親； 同一個(gè)雙親的孩子之間互稱(chēng)為兄弟；從結(jié)點(diǎn)向上到達(dá)根結(jié)點(diǎn)所途經(jīng)的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的祖先，從結(jié)點(diǎn)向下所能到達(dá)的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子孫。如右圖中，A是B、C和D的雙親，B、C和D都是A的孩子，B、C和D三者之間互為兄弟；A和C是E的祖先，A的子孫是B、C、D、E和F。,樹(shù)的基本運(yùn)算,setnull(T)：置T為空樹(shù)，即初始化一棵樹(shù)T。 root(T)或root(x)：求根函數(shù)。求樹(shù)T的根或求

8、結(jié)點(diǎn)x所在樹(shù)的根結(jié)點(diǎn)，若T為空樹(shù)或x不在樹(shù)T中，則函數(shù)值為NULL。 parent(T，x)：求雙親函數(shù)。求樹(shù)T中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)，若x是樹(shù)T的根結(jié)點(diǎn)或x不在樹(shù)T中，則函數(shù)值為NULL。 child(T，x，i)：求孩子函數(shù)。求樹(shù)T中結(jié)點(diǎn)x的第i個(gè)孩子結(jié)點(diǎn)，若結(jié)點(diǎn)x無(wú)第i個(gè)孩子則函數(shù)值為NULL。 create(x，F(xiàn))：建樹(shù)函數(shù)。生成一棵以x為根結(jié)點(diǎn)，以森林F為子樹(shù)森林的樹(shù)。 rsibling(T，x)：求右兄弟函數(shù)。求樹(shù)T中結(jié)點(diǎn)x的右邊兄弟，若x是其雙親的最右孩子或x不在T中，則函數(shù)值為NULL。,樹(shù)的基本運(yùn)算（續(xù)）,addchild(y，i，x)：插入子樹(shù)操作。把以結(jié)點(diǎn)x為根的樹(shù)置為結(jié)點(diǎn)

9、y的第i棵子樹(shù)。若樹(shù)中無(wú)結(jié)點(diǎn)y或它的子樹(shù)個(gè)數(shù)小于i-1，則為空操作。 delchild(x，i)：刪除子樹(shù)操作。刪除結(jié)點(diǎn)x的第i棵子樹(shù)，若無(wú)結(jié)點(diǎn)x或x的子樹(shù)個(gè)數(shù)小于i，則為空操作。 traverse(T)：遍歷操作。按某個(gè)次序依次訪問(wèn)樹(shù)中各個(gè)結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。也就是說(shuō)，遍歷操作的結(jié)果是對(duì)非線性結(jié)構(gòu)樹(shù)中各結(jié)點(diǎn)，按某個(gè)次序給出一個(gè)線性化的結(jié)點(diǎn)序列。,第4章 樹(shù)與二叉樹(shù),4.1 樹(shù)的基本概念 4.2 二叉樹(shù) 4.3 二叉樹(shù)的遍歷 4.4 線索二叉樹(shù) 4.5 樹(shù)和森林 4.6 哈夫曼樹(shù),4.2 二叉樹(shù),4.2.1 二叉樹(shù)的概念 4.2.2 二叉樹(shù)的性質(zhì) 4.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 4.

10、2.4 二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn),二叉樹(shù)的概念,二叉樹(shù)是另一種重要的樹(shù)型結(jié)構(gòu)。它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，即二叉樹(shù)中任何結(jié)點(diǎn)的度不得大于2。 二叉樹(shù)的定義： 二叉樹(shù)（binary tree）是n（n0）個(gè)結(jié)點(diǎn)的有限集合，它或者（n=0時(shí)）為空樹(shù)，或者（n0時(shí)）由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱(chēng)為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。,二叉樹(shù)的概念（續(xù)）,由定義顯見(jiàn)二叉樹(shù)的遞歸性質(zhì)。 應(yīng)該指出的是，二叉樹(shù)與樹(shù)是兩個(gè)不同的概念，它不是樹(shù)的特殊情況；這是因?yàn)槎鏄?shù)的子樹(shù)有左右之分，而樹(shù)的子樹(shù)不必區(qū)分次序。 另外二叉樹(shù)與度為2的有序樹(shù)也是不同的概念；因?yàn)閷?duì)于二叉樹(shù)的子樹(shù)而言，要么是根的左子樹(shù)，要么是根的右

11、子樹(shù)，即使只有一棵子樹(shù)也要區(qū)分是左是右；而度為2的有序樹(shù)中，當(dāng)一個(gè)結(jié)點(diǎn)有兩棵子樹(shù)時(shí)有左右之分，而只有一棵子樹(shù)時(shí)就無(wú)左右之分。,二叉樹(shù)與度為2的普通樹(shù)的區(qū)別舉例,在下圖中，(a)和(b)所示的兩棵二叉樹(shù)雖然與(c)所示的普通樹(shù)相似，但卻不等同于這棵普通樹(shù)。,二叉樹(shù)的五種基本形態(tài),二叉樹(shù)可以是空樹(shù)，根也可以有空的左子樹(shù)、空的右子樹(shù)或左右子樹(shù)均為空，因此二叉樹(shù)有五種基本形態(tài)，如下圖所示：,二叉樹(shù)的基本運(yùn)算,樹(shù)的術(shù)語(yǔ)對(duì)于二叉樹(shù)都適用。 與樹(shù)的基本運(yùn)算類(lèi)似，二叉樹(shù)也有如下的一些基本運(yùn)算： 求二叉樹(shù)的根root(bt)； 求二叉樹(shù)中結(jié)點(diǎn)x的雙親parent(bt,x)； 求二叉樹(shù)中結(jié)點(diǎn)x的左孩子或右孩子l

12、child(bt,x)和rchild(bt,x)； 設(shè)置空二叉樹(shù)setnull(bt)； 建立以x為根，以二叉樹(shù)lbt和rbt為左右子樹(shù)的一棵二叉樹(shù)create(x,lbt,rbt)；,二叉樹(shù)的基本運(yùn)算（續(xù)）,置以y為根的二叉樹(shù)為結(jié)點(diǎn)x的左子樹(shù)或右子樹(shù)addlchild(bt,x,y)和addrchild(bt,x,y)； 刪除結(jié)點(diǎn)x的左子樹(shù)或右子樹(shù)dellchild(bt,x)和delrchild(bt,x)； 在二叉樹(shù)中查找結(jié)點(diǎn)x的運(yùn)算search(bt,x)； 按照某種次序遍歷二叉樹(shù)中的所有結(jié)點(diǎn)traverse(bt)。,4.2 二叉樹(shù),4.2.1 二叉樹(shù)的概念 4.2.2 二叉樹(shù)的性質(zhì)

13、 4.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 4.2.4 二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn),二叉樹(shù)的性質(zhì),二叉樹(shù)具有一些重要性質(zhì)。 性質(zhì)1 二叉樹(shù)的第i（i1）層上至多有2i-1個(gè)結(jié)點(diǎn)。 證明：用數(shù)學(xué)歸納法證明如下： 當(dāng)i=1時(shí)只有一個(gè)結(jié)點(diǎn)，2i-1=20=1，命題成立。 設(shè)對(duì)于任意的j，1ji時(shí)命題成立，即第j層上至多含有2j-1個(gè)結(jié)點(diǎn)。 則由歸納假設(shè)第i-1層上至多含有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，故第i層上的最大結(jié)點(diǎn)數(shù)應(yīng)為第i-1層上最大結(jié)點(diǎn)數(shù)的二倍，即2*2i-2=2i-1成立，故命題成立。,二叉樹(shù)的性質(zhì)（續(xù)）,性質(zhì)2 深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k1）。 證明：深度為k的二叉樹(shù)

14、最多含有的結(jié)點(diǎn)數(shù)應(yīng)是每層含有的最多結(jié)點(diǎn)數(shù)之和，由性質(zhì)1應(yīng)為20+21+2k-1=2k-1。 性質(zhì)3 對(duì)任意一棵二叉樹(shù)，若終端結(jié)點(diǎn)數(shù)為n，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 證明：設(shè)二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為n1，二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為n，則有 n=n0+n1+n2 再考慮孩子結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的結(jié)點(diǎn)都是一個(gè)結(jié)點(diǎn)的孩子，二叉樹(shù)中孩子結(jié)點(diǎn)總數(shù)為n-1；而度為1的結(jié)點(diǎn)有一個(gè)孩子，度為2的結(jié)點(diǎn)有兩個(gè)孩子，因此二叉樹(shù)中孩子結(jié)點(diǎn)的總數(shù)又為n1+2n2，即 n-1=n1+2n2 聯(lián)立以上二等式可得n0=n2+1，原命題得證。,二叉樹(shù)的特殊形態(tài)滿(mǎn)二叉樹(shù),滿(mǎn)二叉樹(shù)（full binary tree）是指深度為

15、k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。 下圖給出了深度為3的滿(mǎn)二叉樹(shù)。顯然，滿(mǎn)二叉樹(shù)的每層含有結(jié)點(diǎn)數(shù)為最大值，不存在度為1的結(jié)點(diǎn)，除葉子結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都有左右孩子，且葉子結(jié)點(diǎn)全部在第k層上。,二叉樹(shù)的特殊形態(tài)完全二叉樹(shù),完全二叉樹(shù)（complete binary tree）是指深度為k的、有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)。下圖給出了一棵深度為3的完全二叉樹(shù)示例。 顯然，完全二叉樹(shù)中前k-1層含有結(jié)點(diǎn)數(shù)為最大值，第k層不一定滿(mǎn)但全部集中在左邊而空缺留在右邊，葉子結(jié)點(diǎn)只可能在第k層和第k-1層上出現(xiàn)。 顯而易見(jiàn)，滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的特殊情況，滿(mǎn)

16、二叉樹(shù)一定是完全二叉樹(shù)，反之不然。,二叉樹(shù)的性質(zhì)（續(xù)）,性質(zhì)4 具有n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 。 證明：設(shè)該完全二叉樹(shù)的深度為k，由完全二叉樹(shù)的定義及性質(zhì)2有2k-1-1n2k-1，即有 2k-1n2k 同時(shí)取對(duì)數(shù)后有 k-1log2nk 因?yàn)閗為整數(shù)，故有 ，即 。,二叉樹(shù)的性質(zhì)（續(xù)）,性質(zhì)5 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照自上而下自左至右的順序?qū)λ薪Y(jié)點(diǎn)從1到n編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有： 如果i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親；如果i1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)編號(hào)為 。 如果2in，則結(jié)點(diǎn)i的左孩子編號(hào)為2i；否則無(wú)左孩子。 如果2i+1n，則結(jié)點(diǎn)i的右孩子編號(hào)為2i+1

17、；否則無(wú)右孩子。 如果i為奇數(shù)且不為1，則結(jié)點(diǎn)i的左兄弟編號(hào)為i-1；否則無(wú)左兄弟。 如果i為偶數(shù)且小于n，則結(jié)點(diǎn)i的右兄弟編號(hào)為i+1；否則無(wú)右兄弟。,4.2 二叉樹(shù),4.2.1 二叉樹(shù)的概念 4.2.2 二叉樹(shù)的性質(zhì) 4.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 4.2.4 二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn),順序存儲(chǔ)結(jié)構(gòu),二叉樹(shù)的順序存儲(chǔ)是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的數(shù)據(jù)元素。 一般是按從根結(jié)點(diǎn)開(kāi)始自上而下自左至右的順序來(lái)存儲(chǔ)，然而按這種方法存儲(chǔ)后結(jié)點(diǎn)在物理上的鄰接關(guān)系一般不能反映出它們?cè)谶壿嬌系那摆吅秃罄^關(guān)系。 只有通過(guò)某種方法能夠確定出結(jié)點(diǎn)之間的邏輯關(guān)系，這種存儲(chǔ)方法才有意義。,順序存儲(chǔ)結(jié)構(gòu)（續(xù)）,由二叉樹(shù)

18、的性質(zhì)5我們知道，完全二叉樹(shù)以及它的特殊形態(tài)滿(mǎn)二叉樹(shù)中的結(jié)點(diǎn)，可以由結(jié)點(diǎn)的序號(hào)惟一確定結(jié)點(diǎn)之間的邏輯關(guān)系，如雙親、左孩子、右孩子、左兄弟、右兄弟等關(guān)系； 所以可以采用一維數(shù)組a1n按結(jié)點(diǎn)編號(hào)依次存儲(chǔ)完全二叉樹(shù)中各結(jié)點(diǎn)，這樣既可用一維數(shù)組的下標(biāo)確定結(jié)點(diǎn)位置和結(jié)點(diǎn)之間的關(guān)系，又可節(jié)省存儲(chǔ)空間。,完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)示意圖,其中：a2的雙親是a1，左孩子是a4，右孩子是a5，無(wú)左兄弟其右兄弟是a3。,一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),對(duì)于一般的二叉樹(shù)，如果仍按順序存儲(chǔ)依次存放各結(jié)點(diǎn)于數(shù)組中，通過(guò)數(shù)組下標(biāo)不能反映出結(jié)點(diǎn)之間的邏輯關(guān)系；只有通過(guò)添加一些并不存在的空結(jié)點(diǎn)，使之成為完全二叉樹(shù)形式才行。 顯然，會(huì)

19、造成許多存儲(chǔ)空間的浪費(fèi)，最壞情況下是單右枝樹(shù)，一棵深度為k的單右枝樹(shù)，只有k個(gè)結(jié)點(diǎn)卻需分配2k-1個(gè)存儲(chǔ)單元。 所以，不宜用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一般的二叉樹(shù)。,一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)示意圖,單右枝二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)示意圖,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用鏈表來(lái)存儲(chǔ)二叉樹(shù)，用鏈指針來(lái)指示元素間的邏輯關(guān)系。 常用的鏈?zhǔn)酱鎯?chǔ)方法有雙鏈法和三鏈法兩種。 所謂雙鏈法即二叉鏈表表示法，它為每一個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針域，分別指向該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)；當(dāng)無(wú)左子樹(shù)或右子樹(shù)時(shí)，其指針域值為NULL（或）。其結(jié)點(diǎn)結(jié)構(gòu)如下： 其中：data域存放結(jié)點(diǎn)的數(shù)據(jù)信息，lchild域存放指向左孩子的指針，rchild域存

20、放指向右孩子的指針。,二叉樹(shù)的二叉鏈表表示示意圖,二叉鏈表的類(lèi)型定義,顯然，二叉鏈表表示法是存儲(chǔ)二叉樹(shù)的最自然的方法，對(duì)于要經(jīng)常做插入或刪除運(yùn)算的二叉樹(shù)尤為合適。 二叉鏈表表示法的類(lèi)型定義為 typedef struct btnode elemtype data; /*數(shù)據(jù)域*/ struct btnode *lchild,*rchild; /*左、右孩子域*/ bitnode; typedef bitnode *bitree; 二叉鏈表表示法便于從根往下查找，即便于查找孩子或子孫。,二叉樹(shù)的三叉鏈表表示,若需要頻繁查找雙親或祖先，二叉鏈表就不太方便，需要由根結(jié)點(diǎn)開(kāi)始向下查找，其效率較低。 解

21、決這一類(lèi)問(wèn)題的辦法是采用三鏈法，即三叉鏈表表示法，增加一個(gè)指針域用來(lái)指向雙親結(jié)點(diǎn)。其結(jié)點(diǎn)結(jié)構(gòu)如下： 其中：parent是存放指向雙親結(jié)點(diǎn)的指針域。 三叉鏈表表示法既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)，這種方便是以增加存儲(chǔ)開(kāi)銷(xiāo)為代價(jià)的。,二叉樹(shù)的三叉鏈表表示示意圖,4.2 二叉樹(shù),4.2.1 二叉樹(shù)的概念 4.2.2 二叉樹(shù)的性質(zhì) 4.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 4.2.4 二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn),二叉樹(shù)的基本運(yùn)算實(shí)現(xiàn),二叉樹(shù)基本運(yùn)算的實(shí)現(xiàn)算法，依賴(lài)于具體的存儲(chǔ)結(jié)構(gòu)；采用不同的存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的基本運(yùn)算實(shí)現(xiàn)的算法是不同的。這里我們討論的運(yùn)算實(shí)現(xiàn)算法，是以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的。 求二叉樹(shù)中結(jié)點(diǎn)x的雙

22、親、左孩子、右孩子以及查找結(jié)點(diǎn)x的運(yùn)算，都涉及要按照某種次序遍歷二叉樹(shù)中所有結(jié)點(diǎn)，在遍歷的過(guò)程中完成的運(yùn)算和操作；由于二叉樹(shù)的遍歷運(yùn)算在下一節(jié)我們專(zhuān)門(mén)討論，所以這些運(yùn)算我們穿插安排在下一節(jié)討論。 只討論簡(jiǎn)化了的問(wèn)題，即把一個(gè)結(jié)點(diǎn)插入到二叉樹(shù)中作為左右孩子或刪除二叉樹(shù)中左右孩子的算法。,1.設(shè)置空二叉樹(shù),設(shè)置空二叉樹(shù)setnull(bt) void setnull(bitree bt) /*設(shè)置一棵空二叉樹(shù)，即置頭結(jié)點(diǎn)的左右孩子鏈域?yàn)榭?/ bt-lchild=NULL; /*左鏈域置空*/ bt-rchild=NULL; /*右鏈域置空*/ ,2.求二叉樹(shù)的根,求二叉樹(shù)的根root(bt) e

23、lemtype root(bitree bt) /*該運(yùn)算返回二叉樹(shù)根結(jié)點(diǎn)的值， 當(dāng)二叉樹(shù)為空樹(shù)時(shí)返回NULL*/ if(bt-lchild=NULL) return NULL; else return bt-lchild-data; ,3.建立二叉樹(shù)操作,建立二叉樹(shù)操作create(x,lbt,rbt) bitree create(elemtype x,bitree lbt,bitree rbt) /*該運(yùn)算生成一棵以x為根結(jié)點(diǎn)， lbt和rbt分別為左右子樹(shù)的二叉樹(shù)*/ bitree p; p=(bitree)malloc(sizeof(bitnode); p-data=x; p-lchi

24、ld=lbt; p-rchild=rbt; return p; /*返回建成的二叉樹(shù)*/ ,4.插入左孩子,插入左孩子addlchild(bt,x) void addlchild(bitree bt,elemtype x) /*把元素x插入到二叉樹(shù)bt中成為它的左孩子*/ bitree p; p=(bitree)malloc(sizeof(bitnode); p-data=x; p-lchild=NULL; p-rchild=NULL; bt-lchild=p; /*插入bt的左孩子域*/ ,5.刪除左孩子,刪除左孩子dellchild(bt) void dellchild(bitree bt

25、) /*刪除二叉樹(shù)bt的左孩子，整個(gè)左子樹(shù)全部被刪除*/ bitree p; p=bt-lchild; *保存左子樹(shù)指針*/ bt-lchild=NULL; free (p); /*釋放左子樹(shù)空間*/ ,第4章 樹(shù)與二叉樹(shù),4.1 樹(shù)的基本概念 4.2 二叉樹(shù) 4.3 二叉樹(shù)的遍歷 4.4 線索二叉樹(shù) 4.5 樹(shù)和森林 4.6 哈夫曼樹(shù),4.3 二叉樹(shù)的遍歷,4.3.1 遍歷二叉樹(shù)的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹(shù)的復(fù)原 4.3.4 基于遍歷的幾種二叉樹(shù)運(yùn)算的 實(shí)現(xiàn)和應(yīng)用舉例,二叉樹(shù)的遍歷,二叉樹(shù)的遍歷是指按照某種次序巡訪二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)

26、點(diǎn)都被訪問(wèn)一次且只被訪問(wèn)一次。遍歷是二叉樹(shù)中經(jīng)常要用到的一種操作。在許多實(shí)際應(yīng)用問(wèn)題中，常常需要查找具有某一特征的結(jié)點(diǎn)，或者對(duì)二叉樹(shù)中每個(gè)結(jié)點(diǎn)逐個(gè)訪問(wèn)，在訪問(wèn)的過(guò)程中對(duì)某些結(jié)點(diǎn)或全部結(jié)點(diǎn)進(jìn)行相應(yīng)的處理。 遍歷對(duì)于線性結(jié)構(gòu)來(lái)說(shuō)是非常簡(jiǎn)單的，只需順序掃描每個(gè)數(shù)據(jù)元素一次即可。由于二叉樹(shù)是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有可能有兩棵子樹(shù)，這就需要尋找一種規(guī)律，使二叉樹(shù)中結(jié)點(diǎn)信息由非線性排列變成為某種意義上的線性排列次序序列。 所以我們可以說(shuō)，遍歷操作的實(shí)質(zhì)就是使非線性結(jié)構(gòu)線性化。,二叉樹(shù)的遍歷（續(xù)）,由二叉樹(shù)的定義分析二叉樹(shù)的結(jié)構(gòu)特征可知，一棵非空的二叉樹(shù)是由根結(jié)點(diǎn)（D）、左子樹(shù)（L）和右子樹(shù)（R）三個(gè)基

27、本部分組成的。 只要依次遍歷這三個(gè)部分，就可以遍歷整個(gè)二叉樹(shù)；而對(duì)這三個(gè)部分的遍歷有六種可能的次序，即DLR、DRL、LDR、RDL、LRD和RLD。 如果限定先左后右則只有三種情況，即DLR、LDR和LRD三種，分別稱(chēng)為前序遍歷、中序遍歷和后序遍歷。,1.前序遍歷,前序遍歷（preorder traversal） 前序遍歷二叉樹(shù)的遞歸定義為：若二叉樹(shù)為空樹(shù)則遍歷結(jié)束，否則 訪問(wèn)根結(jié)點(diǎn)； 前序遍歷根結(jié)點(diǎn)的左子樹(shù)； 前序遍歷根結(jié)點(diǎn)的右子樹(shù)； 例如對(duì)下圖的二叉樹(shù)，前序遍歷得到的結(jié)點(diǎn)序列為ABDFCEG。,前序遍歷的遞歸算法描述,void preorder(bitree bt) if(bt=NULL

28、) return ; /*遞歸結(jié)束條件*/ else printf(“%dt”,bt-data); preorder(bt-lchild); /*前序遍歷左子樹(shù)*/ preorder(bt-rchild); /*前序遍歷右子樹(shù)*/ ,2.中序遍歷,中序遍歷（inorder traversal） 中序遍歷二叉樹(shù)的遞歸定義為：若二叉樹(shù)為空樹(shù)則遍歷結(jié)束，否則 中序遍歷根結(jié)點(diǎn)的左子樹(shù)； 訪問(wèn)根結(jié)點(diǎn)； 中序遍歷根結(jié)點(diǎn)的右子樹(shù)； 例如對(duì)下圖的二叉樹(shù)，中序遍歷得到的結(jié)點(diǎn)序列為BFDAEGC。,中序遍歷的遞歸算法描述,void inorder(bitree bt) if(bt=NULL) return ; /

29、*遞歸結(jié)束條件*/ else inorder(bt-lchild); /*中序遍歷左子樹(shù)*/ printf(“%dt”,bt-data); /*訪問(wèn)根結(jié)點(diǎn)*/ inorder(bt-rchild); /*中序遍歷右子樹(shù)*/ ,3.后序遍歷,后序遍歷（postorder traversal） 后序遍歷二叉樹(shù)的遞歸定義為：若二叉樹(shù)為空樹(shù)則遍歷結(jié)束，否則 后序遍歷根結(jié)點(diǎn)的左子樹(shù)； 后序遍歷根結(jié)點(diǎn)的右子樹(shù)； 訪問(wèn)根結(jié)點(diǎn)； 例如對(duì)下圖的二叉樹(shù)，后序遍歷得到的結(jié)點(diǎn)序列為FDBGECA。,后序遍歷的遞歸算法描述,void postorder(bitree bt) if(bt=NULL) return ; /

30、*遞歸結(jié)束條件*/ else postorder(bt-lchild); /*后序遍歷左子樹(shù)*/ postorder(bt-rchild); /*后序遍歷右子樹(shù)*/ printf(“%dt”,bt-data); /*訪問(wèn)根結(jié)點(diǎn)*/ ,二叉樹(shù)的遍歷（續(xù)）,二叉樹(shù)的前序、中序和后序三種次序遍歷，都是從根結(jié)點(diǎn)開(kāi)始的，并且在遍歷過(guò)程中所經(jīng)過(guò)的結(jié)點(diǎn)路線也是相同的，僅僅只是訪問(wèn)的時(shí)機(jī)不同而已。 如左下圖所示的二叉樹(shù)，其三種遍歷的巡訪路線和訪問(wèn)時(shí)機(jī)可示意如右下圖所示。,二叉樹(shù)的遍歷舉例,4.3 二叉樹(shù)的遍歷,4.3.1 遍歷二叉樹(shù)的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹(shù)的

31、復(fù)原 4.3.4 基于遍歷的幾種二叉樹(shù)運(yùn)算的 實(shí)現(xiàn)和應(yīng)用舉例,遍歷二叉樹(shù)的非遞歸算法,遞歸算法簡(jiǎn)潔精練、可讀性好、易理解，但其執(zhí)行效率較低；另外，并非所有程序設(shè)計(jì)語(yǔ)言都提供遞歸的功能設(shè)施。所以，我們有必要討論遍歷二叉樹(shù)的非遞歸算法。 我們注意觀察前面給出的三種次序的巡訪路線，它是從根結(jié)點(diǎn)開(kāi)始沿左子樹(shù)深入直到最左下端時(shí)，返回進(jìn)入剛剛遇到結(jié)點(diǎn)的右子樹(shù)； 在右子樹(shù)中，也是先深入到它的最左下結(jié)點(diǎn)時(shí)返回剛遇到結(jié)點(diǎn)的右子樹(shù)，如此深入和返回，直到從根結(jié)點(diǎn)的右子樹(shù)返回到根結(jié)點(diǎn)時(shí)止。 在這一過(guò)程中，返回結(jié)點(diǎn)的順序恰與深入結(jié)點(diǎn)的順序相反，先深入的后返回，正好符合棧的特點(diǎn)。 所以我們可以用棧來(lái)保存遍歷過(guò)程中的結(jié)點(diǎn)信

32、息來(lái)實(shí)現(xiàn)遍歷二叉樹(shù)的非遞歸算法，并且假定棧空間足夠大不會(huì)發(fā)生棧上溢以簡(jiǎn)化算法。,1.前序遍歷二叉樹(shù)的非遞歸算法,前序遍歷二叉樹(shù)的非遞歸算法思想是：從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直深入到最左下結(jié)點(diǎn)時(shí)止，在深入的過(guò)程中訪問(wèn)所遇到的結(jié)點(diǎn)，并把所遇到結(jié)點(diǎn)的非空右孩子進(jìn)棧；當(dāng)左子樹(shù)結(jié)點(diǎn)全部處理完之后，從棧頂退出當(dāng)前最近訪問(wèn)過(guò)結(jié)點(diǎn)的右孩子，再按上述過(guò)程遍歷該結(jié)點(diǎn)的右子樹(shù)；如此重復(fù)，直到?？諘r(shí)為止。 在下面的算法中，二叉樹(shù)以二叉鏈表存儲(chǔ)，用一維數(shù)組stackMAXSIZE作為棧來(lái)保存結(jié)點(diǎn)的右孩子信息，top為棧頂指針，p始終指向巡訪過(guò)程中當(dāng)前要處理的結(jié)點(diǎn)。,前序遍歷的非遞歸算法描述,#define MAX

33、SIZE 100 void nrpreorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) printf(“%dt”,p-data); if(p-rchild!=NULL) /*如果右子樹(shù)不空*/ stack+top=p-rchild; /*右孩子進(jìn)棧*/ p=p-lchild; if(top0) p=stacktop-; while(top0); /*當(dāng)棧不空時(shí)繼續(xù)遍歷*/ ,2.中序遍歷二叉樹(shù)的非遞歸算法,中序遍歷二叉樹(shù)的非遞歸算法，其基本思想與前序遍歷類(lèi)同，只是沿左子樹(shù)向下搜索的過(guò)程中先將所遇

34、結(jié)點(diǎn)進(jìn)棧，待遍歷完左子樹(shù)返回時(shí)從棧頂退出結(jié)點(diǎn)并訪問(wèn)，然后再遍歷右子樹(shù)。,中序遍歷的非遞歸算法描述,#define MAXSIZE 100 void nrinorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) stack+top=p; /*所遇結(jié)點(diǎn)進(jìn)棧*/ p=p-lchild; /*繼續(xù)搜索p的左子樹(shù)*/ if(top0) p=stacktop-; /*出棧一個(gè)結(jié)點(diǎn)*/ printf(“%dt”,p-data); /*訪問(wèn)結(jié)點(diǎn)*/ p=p-rchild; /*繼續(xù)搜索右子樹(shù)*/ while(top

35、0); ,3.后序遍歷二叉樹(shù)的非遞歸算法,后序遍歷二叉樹(shù)的非遞歸算法要比前序和中序遍歷稍復(fù)雜些。 在后序遍歷中，當(dāng)搜索指針指向一個(gè)結(jié)點(diǎn)時(shí)不能馬上訪問(wèn)，需要先遍歷左子樹(shù)，所以結(jié)點(diǎn)需要進(jìn)棧保存； 當(dāng)遍歷完左子樹(shù)返回再次搜索到該結(jié)點(diǎn)時(shí)還不能進(jìn)行訪問(wèn)，還需要遍歷其右子樹(shù)，所以結(jié)點(diǎn)需要再次進(jìn)棧保存；即一個(gè)結(jié)點(diǎn)在兩次進(jìn)棧兩次出棧之后才能訪問(wèn)。,后序遍歷二叉樹(shù)的非遞歸算法續(xù),為了區(qū)別某一結(jié)點(diǎn)指針的兩次出棧，需設(shè)置一標(biāo)志flag同結(jié)點(diǎn)同時(shí)進(jìn)出棧，flag定義如下： 棧中數(shù)據(jù)類(lèi)型可定義為指向結(jié)點(diǎn)的指針和flag組成的結(jié)構(gòu)體類(lèi)型： typedef struct stackelem bitree link; int

36、 flag; stackelemtype;,后序遍歷的非遞歸算法描述,#define MAXSIZE 100 void nrpostorder(bitree bt) stackelemtype stackMAXSIZE; /*定義棧*/ bitree p; int top=0,sign; p=bt; /*巡訪指針指向二叉樹(shù)的根結(jié)點(diǎn)*/ do while(p!=NULL) stack+top.link=p; /*結(jié)點(diǎn)第一次入棧*/ stacktop.flag=0; /*置標(biāo)志為0*/ p=p-lchild; /*遍歷左子樹(shù)準(zhǔn)備*/ ,后序遍歷的非遞歸算法描述續(xù),if(top0) sign=sta

37、cktop.flag; /*標(biāo)志出棧存于sign*/ p=stacktop-.link; if(sign=0) /*flag為0，是第一次出棧*/ stack+top.link=p; stacktop.flag=1; /*置標(biāo)志為1*/ p=p-rchild; else /*flag為1，是第二次出棧*/ printf(“%dt”,p-data); p=NULL; while(top0); ,4.二叉樹(shù)的層次遍歷,所謂層次遍歷（levelorder traversal）是指從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始從上到下逐層遍歷該二叉樹(shù)，在同一層次中從左到右依次訪問(wèn)各個(gè)結(jié)點(diǎn)。例如對(duì)右圖的二叉樹(shù)，按層次遍歷得到的結(jié)

38、點(diǎn)序列為ABCDEFG。,由層次遍歷的定義可知，層次遍歷是從根結(jié)點(diǎn)開(kāi)始訪問(wèn)，然后訪問(wèn)它的左孩子和右孩子，接下來(lái)是它左孩子的左孩子和右孩子，右孩子的左孩子和右孩子，。即在訪問(wèn)完某個(gè)結(jié)點(diǎn)后，一般不能馬上訪問(wèn)它的左孩子和右孩子（除根結(jié)點(diǎn)等特殊情況外），需要把它的左右孩子信息保存起來(lái)。,二叉樹(shù)的層次遍歷（續(xù)）,這種方式正好與隊(duì)列的操作特點(diǎn)吻合，所以可利用一個(gè)隊(duì)列結(jié)構(gòu)來(lái)實(shí)現(xiàn)層次遍歷，其做法是： (1) 首先將根結(jié)點(diǎn)入隊(duì)列； (2) 當(dāng)隊(duì)列不空，從隊(duì)列中取出隊(duì)頭結(jié)點(diǎn)訪問(wèn)它，并在其左右孩子非空時(shí)，把它的左孩子和右孩子結(jié)點(diǎn)依次入隊(duì)列； (3) 反復(fù)執(zhí)行(2)，直到隊(duì)列為空時(shí)止。 在下面的層次遍歷算法中，二叉樹(shù)

39、以二叉鏈表存儲(chǔ)，用一維數(shù)組queueMAXSIZE實(shí)現(xiàn)循環(huán)隊(duì)列，變量front和rear為分別表示隊(duì)頭指針和隊(duì)尾指針的指示器變量，并假定隊(duì)列有足夠空間不會(huì)發(fā)生上溢。,二叉樹(shù)的層次遍歷算法描述,#define MAXSIZE 100 void levelorder(bitree bt) bitree queueMAXSIZE; int front,rear; if(bt=NULL) return; front=0; rear=0; queue+rear=bt; /*根結(jié)點(diǎn)入隊(duì)列*/ while(front!=rear) front=(front+1)%MAXSIZE; printf(“%dt”,

40、queuefront-data);,二叉樹(shù)的層次遍歷算法描述續(xù),if(queuefront-lchild!=NULL) rear=(rear+1)%MAXSIZE; /*修改隊(duì)尾指針*/ queuerear=queuefront-lchild; if(queuefront-rchild!=NULL) rear=(rear+1)%MAXSIZE; queuerear=queuefront-rchild; ,4.3 二叉樹(shù)的遍歷,4.3.1 遍歷二叉樹(shù)的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹(shù)的復(fù)原 4.3.4 基于遍歷的幾種二叉樹(shù)運(yùn)算的 實(shí)現(xiàn)和應(yīng)用舉例,二叉樹(shù)的

41、復(fù)原,由前面的討論可知，任意一棵二叉樹(shù)中結(jié)點(diǎn)的前序、中序、后序和層次遍歷次序都是惟一的。 反過(guò)來(lái)講，由一種遍歷次序能否惟一確定一棵二叉樹(shù)呢？回答是否定的。 然而，我們可以由兩種遍歷次序惟一確定一棵二叉樹(shù)，這就是二叉樹(shù)的復(fù)原問(wèn)題。,1.利用前序序列和中序序列恢復(fù)二叉樹(shù),二叉樹(shù)的前序遍歷是先訪問(wèn)根結(jié)點(diǎn)，再按前序遍歷方式遍歷根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)，即由前序序列可以確定二叉樹(shù)的根結(jié)點(diǎn)。 另一方面，中序遍歷是先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)；根結(jié)點(diǎn)在中序序列中必然將結(jié)點(diǎn)分割成為兩個(gè)子序列，根結(jié)點(diǎn)前的子序列是其左子樹(shù)的中序序列，而根結(jié)點(diǎn)后的子序列是其右子樹(shù)的中序序列。,利用前序序列和中

42、序序列恢復(fù)二叉樹(shù)續(xù),現(xiàn)在可以根據(jù)這兩個(gè)子序列在前序序列中找到對(duì)應(yīng)的左子序列和右子序列，兩個(gè)子序列在前序中的第一個(gè)結(jié)點(diǎn)分別是根結(jié)點(diǎn)的左孩子和右孩子結(jié)點(diǎn)，即左子樹(shù)和右子樹(shù)的根結(jié)點(diǎn)；此時(shí)左右子樹(shù)的根結(jié)點(diǎn)又分別把左右子序列各劃分成兩個(gè)子序列。 如此一直做下去，由前序序列確定各級(jí)子樹(shù)的根結(jié)點(diǎn)，由中序序列確定隸屬于各級(jí)子樹(shù)的左右子樹(shù)中的結(jié)點(diǎn)，當(dāng)取盡前序序列中的所有結(jié)點(diǎn)時(shí)，各級(jí)子樹(shù)中的左右孩子都惟一確定了，二叉樹(shù)也就恢復(fù)了；而且這種恢復(fù)是惟一的。,利用前序、中序序列恢復(fù)二叉樹(shù)舉例,已知一棵二叉樹(shù)的前序序列為ABDCEFG，中序序列為DBAFEGC，其二叉樹(shù)的恢復(fù)過(guò)程是： 先由前序序列知A為根結(jié)點(diǎn)，由中序序列

43、知DB為左子樹(shù)而FEGC為右子樹(shù)，如下圖(a)； 其次由前序序列確定左右子樹(shù)的根結(jié)點(diǎn)為B和C，由中序序列知D為B的左孩子B無(wú)右孩子，F(xiàn)EG為C的左子樹(shù)C無(wú)右子樹(shù)，如上圖(b)；,利用前序、中序序列恢復(fù)二叉樹(shù)舉例續(xù),現(xiàn)在由前序序列確定C的左子樹(shù)的根結(jié)點(diǎn)為E，由中序序列知F為E的左孩子而G為E的右孩子，這樣就得到了最終恢復(fù)的二叉樹(shù)，如下圖(c)。,2.利用后序序列和中序序列恢復(fù)二叉樹(shù),同利用前序序列和中序序列恢復(fù)二叉樹(shù)的道理一樣，利用后序序列和中序序列也可以惟一確定一棵二叉樹(shù)。 在恢復(fù)二叉樹(shù)的過(guò)程中，后序序列的作用如同前面的前序序列一樣是確定各級(jí)子樹(shù)的根結(jié)點(diǎn)；無(wú)非是前序序列中第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)而后

44、序序列中最后一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)。 中序序列的作用仍然是確定隸屬于各級(jí)子樹(shù)的左右子樹(shù)中的結(jié)點(diǎn)，當(dāng)各級(jí)子樹(shù)中的左右孩子都惟一確定時(shí)，二叉樹(shù)就完全恢復(fù)了。,利用后序、中序序列恢復(fù)二叉樹(shù)舉例,對(duì)于后序序列DBFGECA和中序序列BDAFEGC，可以這樣恢復(fù)二叉樹(shù)： 首先由后序序列知A為根結(jié)點(diǎn)，由中序序列知BD和FEGC分別為左右子樹(shù)，如下圖(a)； 其次由后序序列知B和C為左右子樹(shù)的根結(jié)點(diǎn)，由中序序列知D為B的右孩子B無(wú)左孩子，F(xiàn)EG為C的左子樹(shù)C無(wú)右子樹(shù)，如上圖(b)；,利用后序、中序序列恢復(fù)二叉樹(shù)舉例續(xù),現(xiàn)在由后序序列確定C的左子樹(shù)的根結(jié)點(diǎn)是E，由中序序列知F為E的左孩子而G為E的右孩子，最后得到的

45、二叉樹(shù)，如下圖(c)。,3.利用層次序列和中序序列恢復(fù)二叉樹(shù),利用層次序列和中序序列也可以惟一確定（或恢復(fù)）一棵二叉樹(shù)。 層次遍歷是從上到下處于不同層次的各級(jí)子樹(shù)根結(jié)點(diǎn)的前后順序排列，在同層中是從左到右依次順序排列的。 先由層次序列知其第一個(gè)結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn)，由中序序列區(qū)分隸屬于左右子樹(shù)中的結(jié)點(diǎn)序列；這樣的過(guò)程一直進(jìn)行下去，直到其每一級(jí)子樹(shù)的孩子結(jié)點(diǎn)都惟一確定，二叉樹(shù)就恢復(fù)了。,利用層次、中序序列恢復(fù)二叉樹(shù)舉例,設(shè)有層次序列ABCDEFGH和中序序列BDAFEHGC，恢復(fù)過(guò)程： 由層次序列知根結(jié)點(diǎn)為A，由中序序列知其左子樹(shù)為BD而右子樹(shù)為FEHGC，如下圖(a)； 再由層次序列知B為A的左

46、孩子而C為A的右孩子，由中序序列知D為B的右孩子而B(niǎo)無(wú)左孩子，F(xiàn)EHG為C的左子樹(shù)而C無(wú)右子樹(shù)，如下圖(b)；,利用層次、中序序列恢復(fù)二叉樹(shù)舉例續(xù),現(xiàn)在由層次序列可知FEG的根為E即E為C的左孩子，由中序序列知F是E的左孩子而HG是E的右子樹(shù)，如下圖(c)； 最后由層次序列知G是HG的根結(jié)點(diǎn)即G是E的右孩子，由中序序列知H是G的左孩子，即為所求的二叉樹(shù)，如下圖(d)。,二叉樹(shù)的復(fù)原（續(xù)）,在上面討論的二叉樹(shù)的恢復(fù)過(guò)程中，中序序列所起作用是很重要的，只有利用中序序列才能區(qū)分各級(jí)子樹(shù)中隸屬于左右子樹(shù)中的各結(jié)點(diǎn)，而前序序列、后序序列或?qū)哟涡蛄械淖饔脙H在于確定各級(jí)子樹(shù)的根結(jié)點(diǎn)。 所以，利用前序、后序和

47、層次序列中的任何兩種序列或三種序列全用都不能惟一確定（或恢復(fù)）一棵二叉樹(shù)，這是因?yàn)橹恢Y(jié)點(diǎn)而無(wú)法區(qū)分左右子樹(shù)之緣故。,4.3 二叉樹(shù)的遍歷,4.3.1 遍歷二叉樹(shù)的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹(shù)的復(fù)原 4.3.4 基于遍歷的幾種二叉樹(shù)運(yùn)算的 實(shí)現(xiàn)和應(yīng)用舉例,1.查找結(jié)點(diǎn)x的運(yùn)算,查找二叉樹(shù)bt中的結(jié)點(diǎn)x，可以結(jié)合在四種遍歷算法中的任何一個(gè)算法中進(jìn)行。在此我們以前序遍歷來(lái)實(shí)現(xiàn)查找運(yùn)算的遞歸算法。 bitree search(bitree bt,elemtype x) if(bt!=NULL) if(bt-data=x) return bt; sear

48、ch(bt-lchild,x); /*在左子樹(shù)中查找*/ search(bt-rchild,x); /*在右子樹(shù)中查找*/ else return NULL; ,2.求二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)目,二叉樹(shù)中葉子結(jié)點(diǎn)即終端結(jié)點(diǎn)，它的度為0或者說(shuō)左子樹(shù)和右子樹(shù)均為空?？梢岳萌我环N遍歷方法，在遍歷過(guò)程中對(duì)所遇結(jié)點(diǎn)判斷是否為葉子結(jié)點(diǎn)，若是則統(tǒng)計(jì)變量加1，直到遍歷完所有結(jié)點(diǎn)，葉子結(jié)點(diǎn)總數(shù)即可求得。下面給出利用中序遍歷求葉子結(jié)點(diǎn)數(shù)的遞歸算法： int countleaf(bitree bt) int num=0; if(bt!=NULL) if(bt-lchild=NULL),3.求二叉樹(shù)的高度,二叉樹(shù)的高度

49、或深度為二叉樹(shù)中結(jié)點(diǎn)層次的最大值，由處于第一層的根結(jié)點(diǎn)開(kāi)始遞推即可求得?？梢栽诙鏄?shù)的前序或后序遍歷過(guò)程中求出，下面給出的算法是在后序遍歷過(guò)程中求深度的遞歸算法。 int treedepth(bitree bt) int h,lh,rh; if(bt=NULL) h=0; else lh=treedepth(bt-lchild); /*左子樹(shù)高度賦lh*/ rh=treedepth(bt-rchild); /*右子樹(shù)高度賦rh*/ if(lh=rh) h=lh+1; else h=rh+1; return h; ,第4章 樹(shù)與二叉樹(shù),4.1 樹(shù)的基本概念 4.2 二叉樹(shù) 4.3 二叉樹(shù)的遍歷

50、4.4 線索二叉樹(shù) 4.5 樹(shù)和森林 4.6 哈夫曼樹(shù),4.4 線索二叉樹(shù),4.4.1 線索二叉樹(shù)的概念 4.4.2 線索二叉樹(shù)的構(gòu)造算法 4.4.3 線索二叉樹(shù)上的運(yùn)算實(shí)現(xiàn),線索二叉樹(shù)的概念,遍歷二叉樹(shù)是以一定規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排成一個(gè)線性序列，得到二叉樹(shù)中結(jié)點(diǎn)的某個(gè)次序序列，如前序序列、中序序列、后序序列或?qū)哟涡蛄校?這種對(duì)非線性結(jié)構(gòu)線性化的結(jié)果，使得除端點(diǎn)外的每個(gè)結(jié)點(diǎn)在這個(gè)線性序列中有且僅有一個(gè)前趨和一個(gè)后繼。 然而，用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)每個(gè)結(jié)點(diǎn)中只有指向其左右孩子的指針，從任意一個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的左右孩子，但一般不能直接找到在某一次序序列中的前趨和后繼結(jié)點(diǎn)。,線索二叉樹(shù)的

51、概念（續(xù)）,如果在結(jié)點(diǎn)中增加指向其前趨和后繼的指針，將降低存儲(chǔ)空間的使用效率（密度）。 大家知道，n個(gè)結(jié)點(diǎn)的二叉鏈表中必有n+1個(gè)空指針，因此可以利用這些空指針域存放某一遍歷次序序列之下的前趨和后繼指針信息。 把這種附加的指向其前趨和后繼的指針?lè)Q之為線索（thread），加上了線索的二叉鏈表稱(chēng)之為線索鏈表（thread linked list），相應(yīng)的二叉樹(shù)稱(chēng)之為線索二叉樹(shù)（thread binary tree）。,線索二叉樹(shù)的概念（續(xù)）,在線索鏈表中規(guī)定： 若結(jié)點(diǎn)有左子樹(shù)則lchild域指向其左孩子，否則指向其遍歷序列的前趨； 若結(jié)點(diǎn)有右子樹(shù)則rchild域指向其右孩子，否則指向其遍歷序列的

52、后繼。 為了區(qū)別結(jié)點(diǎn)的鏈域是指向其左右孩子的指針還是指向其前趨或后繼的線索，需要在每個(gè)結(jié)點(diǎn)中增加兩個(gè)線索標(biāo)志ltag和rtag，這兩個(gè)線索標(biāo)志不需要額外的存儲(chǔ)開(kāi)銷(xiāo)，只需利用指針域的第一位（即符號(hào)位）便可實(shí)現(xiàn)。,線索二叉樹(shù)的類(lèi)型定義,typedef enum0, 1ptrtag; typedef struct bithnode elemtype data; struct bithnode *lchild,*rchild; ptrtag ltag,rtag; bithrnode; typedef bithrnode *bithrtree; 其中：,線索二叉樹(shù)舉例,下圖是一棵二叉樹(shù)的中序線索二叉樹(shù)和

53、相應(yīng)的中序線索鏈表，圖中的實(shí)線為指針而虛線為線索。在線索鏈表中增加了頭結(jié)點(diǎn)，其左鏈域lchild指向二叉樹(shù)的根結(jié)點(diǎn)，右鏈域rchild指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)。,4.4 線索二叉樹(shù),4.4.1 線索二叉樹(shù)的概念 4.4.2 線索二叉樹(shù)的構(gòu)造算法 4.4.3 線索二叉樹(shù)上的運(yùn)算實(shí)現(xiàn),線索二叉樹(shù)的構(gòu)造算法,建立線索二叉樹(shù)的過(guò)程稱(chēng)作對(duì)二叉樹(shù)線索化，線索化需要在遍歷的過(guò)程中來(lái)實(shí)現(xiàn)。 在對(duì)二叉樹(shù)的某種次序遍歷過(guò)程中，一邊遍歷一邊建立線索， 若當(dāng)前訪問(wèn)結(jié)點(diǎn)的左孩子域?yàn)榭談t建立前趨線索， 若右孩子域?yàn)榭談t建立后繼線索。 為實(shí)現(xiàn)這一過(guò)程，可設(shè)指針pre指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)，指針p指向當(dāng)前結(jié)點(diǎn)，就可以方便前

54、趨和后繼線索的填入。,線索二叉樹(shù)的構(gòu)造算法（續(xù)）,下面給出的是中序線索二叉樹(shù)線索化的遞歸算法， 其中：函數(shù)inorderthr處理頭結(jié)點(diǎn)以及與頭結(jié)點(diǎn)有關(guān)的指針和線索，包括對(duì)于空二叉樹(shù)的特殊處理；并調(diào)用函數(shù)inthreading對(duì)非空二叉樹(shù)進(jìn)行中序線索化。 算法的描述如下： bithrtree inorderthr(bithrtree t) bithrtree thrt; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0; thrt-rtag=1;,線索二叉樹(shù)的構(gòu)造算法（續(xù)）,if(t=NULL) thrt-lchild=thrt; th

55、rt-rchild=thrt; else thrt-lchild=t; pre=thrt; inthreading(t); pre-rchild=thrt; pre-rtag=1; thrt-rchild=pre; return thrt; ,線索二叉樹(shù)的構(gòu)造算法（續(xù)）,void inthreading(bithrtree t) /*在中序遍歷過(guò)程中線索化二叉樹(shù)t*/ if(t!=NULL) inthreading(t-lchild); /*左子樹(shù)線索化*/ if(t-lchild=NULL) t-ltag=1; t-lchild=pre; if(pre-rchild=NULL) pre-rt

56、ag=1; pre-rchild=p; pre=p; inthreading(t-rchild); /*右子樹(shù)線索化*/ ,4.4 線索二叉樹(shù),4.4.1 線索二叉樹(shù)的概念 4.4.2 線索二叉樹(shù)的構(gòu)造算法 4.4.3 線索二叉樹(shù)上的運(yùn)算實(shí)現(xiàn),1. 遍歷中序線索二叉樹(shù),遍歷線索二叉樹(shù)，只要從頭結(jié)點(diǎn)出發(fā)反復(fù)找結(jié)點(diǎn)的后繼，直到又回到頭結(jié)點(diǎn)時(shí)止。 查找一個(gè)結(jié)點(diǎn)的后繼有兩種情況： 如果結(jié)點(diǎn)的右線索標(biāo)志rtag=1，右指針?biāo)讣礊橹行蚝罄^。 如果結(jié)點(diǎn)的右線索rtag=0，該結(jié)點(diǎn)有右孩子，由中序遍歷定義知其后繼結(jié)點(diǎn)應(yīng)是它的右子樹(shù)上的最左下結(jié)點(diǎn)；即沿著它的右孩子結(jié)點(diǎn)的左指針鏈一直往下找，當(dāng)某結(jié)點(diǎn)左線索標(biāo)志為

57、1時(shí)，該結(jié)點(diǎn)就是要找的最左下結(jié)點(diǎn)。,最左下結(jié)點(diǎn)示意圖,遍歷中序線索二叉樹(shù)算法描述,void inorderthr(bithrtree t) bithrtree p; p=t-lchild; while(p!=t) /*空樹(shù)或遍歷結(jié)束時(shí)p=t*/ while(p-ltag=0) p=p-lchild; /*找最左下結(jié)點(diǎn)*/ printf(“%dt”,p-data); while(p-rtag=1) ,2. 中序線索二叉樹(shù)的逆中序遍歷,所謂逆中序遍歷，是指先逆中序遍歷右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后逆中序遍歷左子樹(shù)。其遍歷結(jié)果序列與中序序列正好相反，即從中序序列的最后一個(gè)結(jié)點(diǎn)到第一個(gè)結(jié)點(diǎn)的次序。 實(shí)現(xiàn)

58、逆中序遍歷，只要從中序線索樹(shù)的頭結(jié)點(diǎn)出發(fā)，由rchild域找到中序的最后一個(gè)結(jié)點(diǎn)，然后反復(fù)查找結(jié)點(diǎn)的前趨結(jié)點(diǎn)，直到又回到頭結(jié)點(diǎn)時(shí)止。 確定一個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)有兩種情況： 如果結(jié)點(diǎn)的左線索標(biāo)志ltag=1，其左指針域lchild所指即為前趨。 如果ltag=0說(shuō)明結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義其前趨結(jié)點(diǎn)應(yīng)是其左子樹(shù)上的最右下結(jié)點(diǎn)；即沿其左孩子的右指針鏈一直向下查找，當(dāng)某結(jié)點(diǎn)的右線索標(biāo)志為1，即rtag=1時(shí)，這個(gè)結(jié)點(diǎn)就是所要找的最右下結(jié)點(diǎn)。,最右下結(jié)點(diǎn)示意圖,逆中序遍歷線索二叉樹(shù)算法描述,void reverseinorder(bithrtree t) bithrtree p; p=t-rch

59、ild； /*p指向中序最后一個(gè)結(jié)點(diǎn)*/ while(p!=t) printf(“%dt”, p-data)； if(p-ltag=0) /*如果左孩子存在*/ p=p-lchild； while(p-rtag=0) /*找左子樹(shù)的最右下結(jié)點(diǎn)*/ p=p-rchild； else p=p-lchild； ,第4章 樹(shù)與二叉樹(shù),4.1 樹(shù)的基本概念 4.2 二叉樹(shù) 4.3 二叉樹(shù)的遍歷 4.4 線索二叉樹(shù) 4.5 樹(shù)和森林 4.6 哈夫曼樹(shù),4.5 樹(shù)和森林,4.5.1 樹(shù)和森林的存儲(chǔ)結(jié)構(gòu) 4.5.2 樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換 4.5.3 樹(shù)和森林的遍歷 4.5.4 樹(shù)的應(yīng)用舉例判定樹(shù),樹(shù)和森

60、林的存儲(chǔ)結(jié)構(gòu),森林是由若干棵樹(shù)組成的，樹(shù)是森林中只有一棵樹(shù)時(shí)的特殊情形； 只要弄清樹(shù)的存儲(chǔ)表示，森林的存儲(chǔ)表示問(wèn)題就迎刃而解了。 這里，介紹樹(shù)的幾種常用存儲(chǔ)表示方法。 雙親表示法 孩子鏈表表示法 孩子兄弟表示法,1. 雙親表示法,在樹(shù)中，每個(gè)結(jié)點(diǎn)的雙親都是惟一的。利用樹(shù)的這一特性，可在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)為每個(gè)結(jié)點(diǎn)增加一個(gè)指向其雙親的指針parent，就可以惟一地表示任何一棵樹(shù)。 這種存儲(chǔ)結(jié)構(gòu)可形式說(shuō)明如下： typedef struct ptrnode elemtype data; struct ptrnode *parent; ptnode; typedef ptnode *ptree;,樹(shù)

61、的雙親表示法示例,在下圖中給出了一棵樹(shù)和它的雙親表示法示例。 顯然，雙親表示法便于向雙親方向查找，而不適合于查找孩子。,2. 孩子鏈表表示法,由于樹(shù)中每個(gè)結(jié)點(diǎn)可能有多棵子樹(shù)，所以可以考慮用多重鏈表表示。然而若以樹(shù)的度設(shè)置結(jié)點(diǎn)中的指針數(shù)的定長(zhǎng)結(jié)點(diǎn)會(huì)造成空間的極大浪費(fèi)，若不定長(zhǎng)地設(shè)置結(jié)點(diǎn)又會(huì)給運(yùn)算帶來(lái)不便。 為此可考慮為樹(shù)中每個(gè)結(jié)點(diǎn)的孩子建立一個(gè)單鏈表，這樣一棵樹(shù)的n個(gè)結(jié)點(diǎn)就有n個(gè)孩子鏈表，把這n個(gè)孩子鏈表的頭結(jié)點(diǎn)組織成一個(gè)順序表，頭結(jié)點(diǎn)的數(shù)據(jù)域填寫(xiě)雙親結(jié)點(diǎn)的值。這種孩子表示法也稱(chēng)作孩子鏈表表示法。 顯然，該子鏈表表示法便于查找孩子，而不適用于雙親方向的查找。 可以把雙親表示法與孩子鏈表表示法結(jié)合

62、起來(lái)形成所謂的雙親孩子表示法，做到既方便查找孩子也方便查找雙親。,樹(shù)的孩子鏈表表示法示例,3. 孩子兄弟表示法,在樹(shù)的各種存儲(chǔ)結(jié)構(gòu)中，孩子兄弟表示法是最常用的存儲(chǔ)表示方法。此法也稱(chēng)作二叉鏈表表示法或左孩子右兄弟表示法。它同二叉樹(shù)的存儲(chǔ)表示一樣，都是用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，所不同的是左指針是指向結(jié)點(diǎn)的第一個(gè)孩子而右指針指向結(jié)點(diǎn)的下一個(gè)兄弟。其結(jié)構(gòu)的形式說(shuō)明如下： typedef struct cstnode elemtype data; struct cstnode *lchild,*rsibling; csnode; typedef csnode *cstree; 值得注意的是，樹(shù)的孩子兄弟表

63、示法所表示出來(lái)的二叉鏈表可與一棵二叉樹(shù)惟一對(duì)應(yīng)，所以可借助二叉鏈表導(dǎo)出樹(shù)與二叉樹(shù)之間的確定對(duì)應(yīng)關(guān)系。,樹(shù)的孩子兄弟表示法示例,4.5 樹(shù)和森林,4.5.1 樹(shù)和森林的存儲(chǔ)結(jié)構(gòu) 4.5.2 樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換 4.5.3 樹(shù)和森林的遍歷 4.5.4 樹(shù)的應(yīng)用舉例判定樹(shù),樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換,從樹(shù)的孩子兄弟表示法我們知道，可借助二叉鏈表導(dǎo)出樹(shù)與二叉樹(shù)之間的確定對(duì)應(yīng)關(guān)系。 此外還可以由“樹(shù)的孩子兄弟表示法示例”看出，樹(shù)所對(duì)應(yīng)的二叉樹(shù)右子樹(shù)必空。 如果把構(gòu)成森林中的各棵樹(shù)的根結(jié)點(diǎn)看作兄弟，森林的存儲(chǔ)表示則可用孩子兄弟表示法實(shí)現(xiàn)，也就是說(shuō)一片森林可以借助二叉鏈表與一棵二叉樹(shù)惟一對(duì)應(yīng)。,1.

64、 森林（或樹(shù)）轉(zhuǎn)換為二叉樹(shù),由樹(shù)和森林的孩子兄弟表示法可知， 把樹(shù)或森林轉(zhuǎn)換為二叉樹(shù)： 二叉樹(shù)的根結(jié)點(diǎn)是樹(shù)或森林中第一棵樹(shù)的根結(jié)點(diǎn)； 二叉樹(shù)的左孩子為該結(jié)點(diǎn)在樹(shù)中的第一個(gè)孩子； 二叉樹(shù)的右孩子為該結(jié)點(diǎn)的下一個(gè)兄弟，按這樣的辦法一直做下去，就會(huì)得到樹(shù)或森林所對(duì)應(yīng)的一棵惟一的二叉樹(shù)。,森林（或樹(shù)）轉(zhuǎn)換為二叉樹(shù)(續(xù)),這種轉(zhuǎn)換辦法的形式化描述（遞歸定義）為： 如果F=T1,T2,Tm是森林，則按如下規(guī)則轉(zhuǎn)換為一棵二叉樹(shù)B=root,LB,RB： 若F為空（即m=0），則B為空樹(shù)； 若F非空（即m0），則B的根root為森林中第一棵樹(shù)的根root(T1)；B的左子樹(shù)LB是從T1中根結(jié)點(diǎn)的子樹(shù)森林F1=

65、T11,T12,T1n轉(zhuǎn)換而成的二叉樹(shù)；其右子樹(shù)RB是從森林F=T2,T3,Tm轉(zhuǎn)換而成的二叉樹(shù)。,森林（或樹(shù)）轉(zhuǎn)換為二叉樹(shù)(續(xù)),前面的轉(zhuǎn)換方法是遞歸定義的。下面我們?cè)俳o出一種直觀做圖轉(zhuǎn)換的方法，這種方法可用一句不太嚴(yán)密的口訣概括為“連兄弟，斷孩子，順時(shí)針旋轉(zhuǎn)45”。 口訣的解釋如下： 連兄弟，即把森林中所有的相鄰兄弟之間用一條橫線相連接； 斷孩子，即斷開(kāi)每個(gè)結(jié)點(diǎn)與第二個(gè)及以后各個(gè)孩子的連線，只保留與第一個(gè)孩子間的連線； 順時(shí)針旋轉(zhuǎn)45，即以第一棵樹(shù)的根結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45，使結(jié)構(gòu)層次分明。,一個(gè)森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程,2. 二叉樹(shù)轉(zhuǎn)換為森林（或樹(shù)）,把二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林是前述轉(zhuǎn)換的逆過(guò)程，可由二叉樹(shù)對(duì)應(yīng)的二叉鏈表依據(jù)前述孩子兄弟表示法的定義逆推還原成樹(shù)或森林。 其形式化轉(zhuǎn)換方法描述為： 如