山大《數(shù)據(jù)結(jié)構(gòu)》講義04樹(shù)和二叉樹(shù)

1、第四章 樹(shù)和二叉樹(shù)內(nèi)容概述樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)。樹(shù)結(jié)構(gòu)經(jīng)常用于描述和處理數(shù)據(jù)元素的層次關(guān)系，尤其適用于大規(guī)模的信息處理任務(wù)，例如建立數(shù)據(jù)庫(kù)管理系統(tǒng)時(shí)所用的層次模型就是一種樹(shù)型結(jié)構(gòu)。本章主要以二叉樹(shù)為例，講述樹(shù)結(jié)構(gòu)及其應(yīng)用，主要內(nèi)容包括：（1）樹(shù)的定義、術(shù)語(yǔ)及性質(zhì)；（2）二叉樹(shù)的定義、性質(zhì)，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及二叉樹(shù)的遍歷等各種操作的算法實(shí)現(xiàn)；（3）線索二叉樹(shù)；（4）樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)化；（5）赫夫曼樹(shù)及其應(yīng)用。重點(diǎn)與難點(diǎn)重點(diǎn)包括：二叉樹(shù)的性質(zhì)及遍歷算法，線索二叉樹(shù)的運(yùn)算，樹(shù)、森林與二叉樹(shù)之間的轉(zhuǎn)換，Huffman樹(shù)的構(gòu)造算法及Huffman編碼、譯碼。難點(diǎn)包括：二叉樹(shù)的遍歷算法，尤其是非遞歸

2、遍歷算法，線索二叉樹(shù)的運(yùn)算，Huffman編碼、譯碼。思考1樹(shù)型結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)2樹(shù)和二叉樹(shù)的主要差別表現(xiàn)在哪些方面？3二叉樹(shù)具有那些重要特性？4二叉樹(shù)有哪些遍歷策略？如何利用算法實(shí)現(xiàn)？5已知某二叉樹(shù)的后序遍歷序列和中序遍歷序列，如何求解出其前序遍歷序列。6已知一棵二叉樹(shù)的中序序列為cbedahgijf，后序序列為cedbhjigfa，畫(huà)出該二叉樹(shù)的先序線索二叉樹(shù)。7有一份電文中共使用5個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、9，試畫(huà)出對(duì)應(yīng)的赫夫曼樹(shù)（請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的赫夫曼編碼。第一節(jié)樹(shù)樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，這種

3、非線性結(jié)構(gòu)有哪些特點(diǎn)？具有那些特有性質(zhì)？如何描述樹(shù)結(jié)構(gòu)？本節(jié)從樹(shù)的定義、抽象類(lèi)型定義、樹(shù)的基本概念與相關(guān)術(shù)語(yǔ)、樹(shù)的性質(zhì)、樹(shù)的表示等方面闡述上述問(wèn)題。1、樹(shù)的遞歸與非遞歸定義1.樹(shù)的遞歸定義樹(shù)(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集合T，不含有任何結(jié)點(diǎn)（元素）的樹(shù)稱(chēng)為空樹(shù)，否則它滿(mǎn)足如下兩個(gè)條件：有且僅有一個(gè)稱(chēng)為根(Root)的結(jié)點(diǎn)；其余所有結(jié)點(diǎn)被分成m(m0)個(gè)互不相交的集合T1,T2,T3,Tm，其中每個(gè)集合又構(gòu)成一棵樹(shù)，稱(chēng)其為根結(jié)點(diǎn)的子樹(shù)(SubTree)。樹(shù)的根結(jié)點(diǎn)Root是每棵子樹(shù)根結(jié)點(diǎn)的前驅(qū)，每棵子樹(shù)的根結(jié)點(diǎn)是根結(jié)點(diǎn)Root的后繼。例如，在圖4.1中，(a)表示只有一個(gè)根結(jié)點(diǎn)的樹(shù)；(b

4、)表示有8個(gè)結(jié)點(diǎn)的樹(shù)，其中A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成3個(gè)互不相交的子集：T1=B,E,F,G,T2=C,T3=D,H。T1、T2和T3都是根結(jié)點(diǎn)A的子樹(shù)，且本身也是一棵樹(shù)。如T1的根結(jié)點(diǎn)為B，其余結(jié)點(diǎn)分為3個(gè)互不相交的子集：T11=E,T12=F,T13=G。T11、T12和T13都是T1的根結(jié)點(diǎn)B的子樹(shù)。2.樹(shù)的非遞歸定義樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集合T，不含有任何結(jié)點(diǎn)（元素）的樹(shù)稱(chēng)為空樹(shù)，而在任一非空樹(shù)中定義了一個(gè)關(guān)系，它滿(mǎn)足：（1）T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒(méi)有前驅(qū)，稱(chēng)為樹(shù)的根；（2）除根結(jié)點(diǎn)外，T中每一個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)；（3）除根結(jié)點(diǎn)外，T中每一個(gè)結(jié)點(diǎn)a，都存在一個(gè)從根結(jié)點(diǎn)到

5、a的結(jié)點(diǎn)序列a1ak,使得a1為根結(jié)點(diǎn)，ak=a，而結(jié)點(diǎn)ai+1是ai的后繼（1ik-1），這個(gè)結(jié)點(diǎn)序列稱(chēng)為從根結(jié)點(diǎn)到結(jié)點(diǎn)a的路徑。例如，在圖4.1(b)中，A為樹(shù)的根結(jié)點(diǎn)。對(duì)于結(jié)點(diǎn)G，存在一個(gè)結(jié)點(diǎn)序列ABG，使得A為根結(jié)點(diǎn)，B為A的后繼，G為B的后繼，這個(gè)序列就是從根結(jié)點(diǎn)A到結(jié)點(diǎn)G的路徑。2、樹(shù)的抽象數(shù)據(jù)類(lèi)型2、樹(shù)的抽象數(shù)據(jù)類(lèi)型樹(shù)的抽象數(shù)據(jù)類(lèi)型定義如下：ADTTree數(shù)據(jù)對(duì)象D：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系R：若D為空集，則稱(chēng)為空樹(shù)。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則RH，H滿(mǎn)足關(guān)系：(1)T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒(méi)有前驅(qū)，稱(chēng)為樹(shù)的根，用root表示，在集

6、合D中用a1表示；(2)若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素ajD且j2，存在唯一的數(shù)據(jù)元素aiD，有H；(3)若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素ajD，存在k個(gè)(k0)數(shù)據(jù)元素aiD且ij，有H；(4)對(duì)于任意的數(shù)據(jù)元素ajD且j2，存在DjD，Dj=|ElemSet,k=1,2,m,m0，有唯一的Pj=,，這個(gè)集合Pj表示從根結(jié)點(diǎn)到結(jié)點(diǎn)aj的一條路徑?；静僮鱌：InitTree(&T);操作結(jié)果：構(gòu)造空樹(shù)T。CreateTree(&T,tree);初始條件：tree給出T的表示形式。操作結(jié)果：按tree構(gòu)造T。TreeEmpty(T);初始條件：樹(shù)T存在。操作結(jié)果：若T為空樹(shù)，

7、則返回TRUE，否則返回FALSE。TreeDepth(T);初始條件：樹(shù)T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：樹(shù)T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE。Assign(T,e,value);初始條件：樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則結(jié)點(diǎn)e賦值為value，函數(shù)返回TRUE，否則返回FALSE。Parent(T,e,&P);初始條件：樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALS

8、E；若存在該結(jié)點(diǎn)，用P返回雙親結(jié)點(diǎn)的位置，若結(jié)點(diǎn)為根結(jié)點(diǎn)，則P返回空。DelTreeNode(&T,P);初始條件：樹(shù)T存在，P指向該二叉樹(shù)中的一個(gè)結(jié)點(diǎn)。操作結(jié)果：刪除P所指向的結(jié)點(diǎn)及其子樹(shù)。TraverseTree(T,visit();初始條件：樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。ClearTree(&T);初始條件：樹(shù)T存在。操作結(jié)果：將樹(shù)T清空。DestroyTree(&T);初始條件：樹(shù)T存在。操作結(jié)果：將樹(shù)T銷(xiāo)毀。ADTTree該抽象數(shù)據(jù)類(lèi)型中，定義了樹(shù)的若干基本操作，

9、另外，對(duì)樹(shù)的操作還可有插入結(jié)點(diǎn)操作、插入子樹(shù)操作、旋轉(zhuǎn)樹(shù)操作等3、樹(shù)的基本術(shù)語(yǔ)3、樹(shù)的基本術(shù)語(yǔ)（樹(shù)結(jié)點(diǎn)、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、度、深度）樹(shù)的結(jié)點(diǎn)樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度和樹(shù)的度樹(shù)中每個(gè)結(jié)點(diǎn)所擁有的非空子樹(shù)數(shù)稱(chēng)為結(jié)點(diǎn)的度（Degree）。樹(shù)的度是樹(shù)中所有結(jié)點(diǎn)的度的最大值。如在圖4.1(b)中，結(jié)點(diǎn)A、B的度均為3，結(jié)點(diǎn)D的度為1，其余結(jié)點(diǎn)的度均為0。因?yàn)樗薪Y(jié)點(diǎn)的度的最大值為3，故樹(shù)的度為3。葉子結(jié)點(diǎn)和分支結(jié)點(diǎn)樹(shù)中度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，度大于0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)以外，分支結(jié)點(diǎn)也稱(chēng)為內(nèi)部結(jié)點(diǎn)。在分支結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)

10、的度數(shù)。度為1的結(jié)點(diǎn)，其分支數(shù)為1，稱(chēng)為單分支結(jié)點(diǎn)；度為2的結(jié)點(diǎn)，其分支數(shù)為2，稱(chēng)為雙分支結(jié)點(diǎn)，其余類(lèi)推。如在圖4.1(b)中，結(jié)點(diǎn)C、E、F、G、H都是葉子結(jié)點(diǎn)，A、B、D都是分支結(jié)點(diǎn)，其中A和B是多分支結(jié)點(diǎn)，D是單分支結(jié)點(diǎn)。子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)樹(shù)中每個(gè)結(jié)點(diǎn)的子樹(shù)的根（即每個(gè)結(jié)點(diǎn)的后繼）稱(chēng)為該結(jié)點(diǎn)的孩子、兒子或子女（Child），相應(yīng)地，該結(jié)點(diǎn)稱(chēng)為子結(jié)點(diǎn)的雙親（Parent）。具有同一個(gè)雙親的孩子之間互稱(chēng)兄弟（Brothers）。雙親在同一層上的結(jié)點(diǎn)互稱(chēng)為堂兄弟。以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫，相應(yīng)地，結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)的路徑上經(jīng)過(guò)的所有分支結(jié)點(diǎn)。在一棵樹(shù)中，根結(jié)

11、點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)，其余結(jié)點(diǎn)都既有雙親結(jié)點(diǎn)也有子結(jié)點(diǎn)。如在圖4.1(b)中，結(jié)點(diǎn)B的孩子為結(jié)點(diǎn)E、F、G，雙親為結(jié)點(diǎn)A；而E、F、G互為兄弟，結(jié)點(diǎn)B的子孫為結(jié)點(diǎn)E、F、G，結(jié)點(diǎn)E的祖先為結(jié)點(diǎn)A、B。結(jié)點(diǎn)的層數(shù)和樹(shù)的深度樹(shù)既是一種遞歸結(jié)構(gòu)，也是一種層次結(jié)構(gòu)。結(jié)點(diǎn)的層數(shù)（Level）從根開(kāi)始定義起，根結(jié)點(diǎn)為第一層，它的子結(jié)點(diǎn)為第二層，以此類(lèi)推。如果某個(gè)結(jié)點(diǎn)在第k層，則其子樹(shù)的根位于第k+1層。樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的深度（Depth）或高度。如在圖4.1(b)中，結(jié)點(diǎn)A為第一層，B、C、D為第二層，E、F、G、H為第三層，樹(shù)中結(jié)點(diǎn)的最大層數(shù)是3，故樹(shù)的深度為3。有序樹(shù)和無(wú)序樹(shù)如果

12、樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照一定的次序從左向右安排的，則稱(chēng)該樹(shù)為有序樹(shù)，否則稱(chēng)之為無(wú)序樹(shù)。在有序樹(shù)中，最左邊的子樹(shù)的根稱(chēng)為第一個(gè)孩子，最右邊的子樹(shù)的根稱(chēng)之為最后一個(gè)孩子。任何無(wú)序樹(shù)都可以當(dāng)作是任一次序的有序樹(shù)來(lái)處理，如一個(gè)單位的機(jī)構(gòu)設(shè)置可用樹(shù)來(lái)表示，若各層機(jī)構(gòu)是按照一定的次序排列的，則為一棵有序樹(shù)，否則為無(wú)序樹(shù)。森林（Forest）是m（m0）棵互不相交的樹(shù)的集合。對(duì)于樹(shù)中每個(gè)分支結(jié)點(diǎn)來(lái)說(shuō)，其子樹(shù)的集合就是森林。如在圖4.1(b)中，由結(jié)點(diǎn)A的子樹(shù)所構(gòu)成的森林為T(mén)1,T2,T3，由結(jié)點(diǎn)B的子樹(shù)所構(gòu)成的森林為T(mén)11,T12,T13。4、樹(shù)的性質(zhì)4、樹(shù)的性質(zhì)性質(zhì)1：樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。根

13、據(jù)樹(shù)的定義，在一個(gè)樹(shù)中，除了根結(jié)點(diǎn)以外，其他每個(gè)結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，即每個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng)，所以除了根結(jié)點(diǎn)以外的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)（即度數(shù)），因此可得出樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。性質(zhì)2：度為k的樹(shù)中第i層上至多有ki-1個(gè)結(jié)點(diǎn)（i1）。利用數(shù)學(xué)歸納法可以證明此性質(zhì)。對(duì)于第一層顯然是成立的。因?yàn)闃?shù)中的第一層上只有根結(jié)點(diǎn)，而i=1時(shí)，ki-1=k0=1，同樣也得到只有一個(gè)結(jié)點(diǎn)。假設(shè)對(duì)于第i-1層（i1）命題成立，即度為k的樹(shù)中第i-1層上至多有k(i-1)-1=ki-2個(gè)結(jié)點(diǎn)，則根據(jù)樹(shù)的度的定義，度為k的樹(shù)中每個(gè)結(jié)點(diǎn)至多有k個(gè)孩子，所以第i層上的最大結(jié)點(diǎn)數(shù)為

14、第i-1層上的最大結(jié)點(diǎn)數(shù)的k倍，即ki-2k=ki-1個(gè)，故結(jié)論成立。性質(zhì)3：深度為h的k叉樹(shù)至多有（kh-1）/（k-1）個(gè)結(jié)點(diǎn)。由性質(zhì)2可知，當(dāng)深度為h的k叉樹(shù)（即度為k的樹(shù)）上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí)，所有結(jié)點(diǎn)的總和為：，故深度為h的k叉樹(shù)至多有個(gè)結(jié)點(diǎn)。當(dāng)一棵k叉樹(shù)上的結(jié)點(diǎn)數(shù)等于時(shí)，即k叉樹(shù)的結(jié)點(diǎn)數(shù)達(dá)到了最大值時(shí)，則稱(chēng)該樹(shù)為滿(mǎn)k叉樹(shù)。這種樹(shù)的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的k叉樹(shù)的最小深度為。（其中符號(hào)表示對(duì)x進(jìn)行向上取整，如。）假設(shè)具有n個(gè)結(jié)點(diǎn)的k叉樹(shù)的深度為h，若在該樹(shù)中前h-1層都是滿(mǎn)的，即第i層的結(jié)點(diǎn)數(shù)等于ki-1個(gè)（1ih-1），最后一層即第h層的結(jié)

15、點(diǎn)數(shù)可能滿(mǎn)也可能不滿(mǎn)，則該樹(shù)具有最小的深度。根據(jù)性質(zhì)3有：，即。以k為底取對(duì)數(shù)后得。所以，。因此得到具有n個(gè)結(jié)點(diǎn)的一般k叉樹(shù)的最小深度是。第二節(jié)二叉樹(shù)二叉樹(shù)是使用最廣泛的樹(shù)型結(jié)構(gòu)，這是因?yàn)橐环矫鎽?yīng)用中有許多問(wèn)題都可以通過(guò)二叉樹(shù)來(lái)解決，另一方面一般樹(shù)的問(wèn)題也可轉(zhuǎn)化為二叉樹(shù)的問(wèn)題來(lái)簡(jiǎn)便處理。那么，二叉樹(shù)具有那些性質(zhì)？如何存儲(chǔ)表示和實(shí)現(xiàn)二叉樹(shù)？1、二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義1、二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義所謂二叉樹(shù)，是指結(jié)點(diǎn)的一個(gè)有限集合，它或?yàn)榭占?，或?yàn)闈M(mǎn)足下列性質(zhì)的非空集合：有且只有一個(gè)根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成左右兩個(gè)互不相交的集合TL、TR，且TL、TR均為二叉樹(shù)。直觀上，二叉樹(shù)就是一個(gè)最多有兩個(gè)分支的

16、樹(shù)。在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)被稱(chēng)為該結(jié)點(diǎn)的左孩子（LeftChild），右子樹(shù)的根結(jié)點(diǎn)被稱(chēng)為該結(jié)點(diǎn)的右孩子（RightChild）。二叉樹(shù)的左右子樹(shù)次序不能任意顛倒。二叉樹(shù)與一般樹(shù)的區(qū)別在于二叉樹(shù)的子樹(shù)有左右之分，以及二叉樹(shù)定義中對(duì)樹(shù)的度數(shù)的限制（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)）。下面我們將重點(diǎn)介紹二叉樹(shù)，這是因?yàn)橐环矫鎽?yīng)用中有許多問(wèn)題都可以通過(guò)二叉樹(shù)來(lái)解決，另一方面一般樹(shù)的問(wèn)題也可轉(zhuǎn)化為二叉樹(shù)的問(wèn)題來(lái)簡(jiǎn)便處理。前面引入的有關(guān)樹(shù)的術(shù)語(yǔ)也都適用于二叉樹(shù)。二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義如下：ADTBinaryTree數(shù)據(jù)對(duì)象D：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系R：若

17、D為空集，則稱(chēng)為空二叉樹(shù)。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則RH，H滿(mǎn)足關(guān)系：(1)T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒(méi)有前驅(qū)，稱(chēng)為樹(shù)的根，用root表示，在集合D中用a1表示；(2)若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素ajD且j2，存在唯一的數(shù)據(jù)元素aiD，有H；(3)若D中元素個(gè)數(shù)大于1，對(duì)于任意的數(shù)據(jù)元素aiD，僅存在不多于2個(gè)數(shù)據(jù)元素aj,akD且j,ki，有,H，其中，若jK，則稱(chēng)aj為ai的左孩子節(jié)點(diǎn)，ak為ai的右孩子節(jié)點(diǎn)。(4)對(duì)于任意的數(shù)據(jù)元素ajD且j2，存在DjD，Dj=|ElemSet,k=1,2,m,m0，有唯一的Pj=,，這個(gè)集合Pj表示從根結(jié)點(diǎn)到結(jié)點(diǎn)aj的一條路徑

18、?；静僮鱌：InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹(shù)T。CreateBiTree(&T,tree);初始條件：tree給出二叉樹(shù)T的表示形式。操作結(jié)果：按tree構(gòu)造二叉樹(shù)T。BiTreeEmpty(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：若T為空樹(shù)，則返回TRUE，否則返回FALSE。BiTreeDepth(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE。Assign(T,e,va

19、lue);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，結(jié)點(diǎn)e賦值為value，則函數(shù)返回TRUE，否則返回FALSE。Parent(T,e,P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回雙親結(jié)點(diǎn)的位置，若結(jié)點(diǎn)為根結(jié)點(diǎn)，則P返回空。LeftChild(T,e,P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回左孩子結(jié)點(diǎn)的位置，若結(jié)點(diǎn)無(wú)左孩子結(jié)點(diǎn)，則P返回空。RightChi

20、ld(T,e,P);初始條件：二叉樹(shù)T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹(shù)中存在值為e的結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點(diǎn)，用P返回右孩子結(jié)點(diǎn)的位置，若結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，則P返回空。DelBiTreeNode(&T，P);初始條件：二叉樹(shù)T存在，P指向該二叉樹(shù)中的一個(gè)結(jié)點(diǎn)。操作結(jié)果：刪除P所指向的結(jié)點(diǎn)及其子樹(shù)。TraverseBiTree(T,visit();初始條件：二叉樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。ClearBiTree(&T);初始條件：

21、二叉樹(shù)T存在。操作結(jié)果：將二叉樹(shù)T清空。ADTBinaryTree2、二叉樹(shù)的性質(zhì)2、二叉樹(shù)的性質(zhì)性質(zhì)1：二叉樹(shù)的終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。假設(shè)二叉樹(shù)中終端結(jié)點(diǎn)數(shù)為n0，單分支結(jié)點(diǎn)數(shù)為n1，雙分支結(jié)點(diǎn)數(shù)為n2，二叉樹(shù)中總結(jié)點(diǎn)數(shù)為n，因?yàn)槎鏄?shù)中所有結(jié)點(diǎn)度數(shù)均小于或等于2，所以有：nn0n1n2；另一方面，二叉樹(shù)中所有結(jié)點(diǎn)的分支數(shù)（即度數(shù)）應(yīng)等于單分支結(jié)點(diǎn)數(shù)加上兩倍的雙分支結(jié)點(diǎn)數(shù)，即n12n2。由樹(shù)的性質(zhì)1，有：nn12n21。根據(jù)以上兩個(gè)式子，我們可以得出下面這個(gè)等式成立：n0n1n2=n12n21，所以n0n21。性質(zhì)2：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。由樹(shù)

22、的性質(zhì)2可知，度為k的樹(shù)中第i層上至多有ki-1個(gè)結(jié)點(diǎn)。對(duì)于二叉樹(shù)，樹(shù)的度為2，將k=2代入ki-1即可得此性質(zhì)。性質(zhì)3：深度為h的二叉樹(shù)至多有2h1個(gè)結(jié)點(diǎn)（h1)。由樹(shù)的性質(zhì)3可知，深度為h的k叉樹(shù)至多有（kh-1）/（k-1）個(gè)結(jié)點(diǎn)。對(duì)于二叉樹(shù)，樹(shù)的度為2，將k=2代入（kh-1）/（k-1）即可得此性質(zhì)。性質(zhì)4：具有n個(gè)（n0）結(jié)點(diǎn)的完全二叉樹(shù)的深度為。由樹(shù)的性質(zhì)4可知，具有n個(gè)結(jié)點(diǎn)的k叉樹(shù)的最小深度為。對(duì)于二叉樹(shù)，樹(shù)的度為2，將k=2代入上式即可得此性質(zhì)。性質(zhì)5：對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)（1in,n1)，有：（1）如果n為奇數(shù)，則樹(shù)中每個(gè)分支結(jié)點(diǎn)都既有左孩子，又有右孩子

23、；如果n為偶數(shù)，則編號(hào)最大的分支結(jié)點(diǎn)即n/2只有左孩子，沒(méi)有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。（2）如果i1，則結(jié)點(diǎn)i無(wú)雙親，是二叉樹(shù)的根；如果i1，則其雙親是結(jié)點(diǎn)。當(dāng)i為偶數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為i/2，它是雙親結(jié)點(diǎn)的左孩子；當(dāng)i為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2，它是雙親結(jié)點(diǎn)的右孩子。其中一對(duì)符號(hào)表示對(duì)x進(jìn)行向下取整，如。（3）如果2in，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。（4）如果2i1n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i1。3、滿(mǎn)二叉樹(shù)、完全二叉樹(shù)3、滿(mǎn)二叉樹(shù)、完全二叉樹(shù)下面介紹兩種特殊形態(tài)的二叉樹(shù)：滿(mǎn)二叉樹(shù)和完全二叉樹(shù)。在一棵二叉樹(shù)中，當(dāng)?shù)趇

24、層的結(jié)點(diǎn)數(shù)為2i-1個(gè)時(shí)，則稱(chēng)此層的結(jié)點(diǎn)數(shù)是滿(mǎn)的。當(dāng)樹(shù)中每一層都滿(mǎn)時(shí)，則稱(chēng)此二叉樹(shù)為滿(mǎn)二叉樹(shù)。圖4.2(a)為一棵深度為4的滿(mǎn)二叉樹(shù)，其結(jié)點(diǎn)數(shù)為15。圖中每個(gè)結(jié)點(diǎn)的值是用該結(jié)點(diǎn)的編號(hào)來(lái)表示的。這種樹(shù)的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。由性質(zhì)3可以得出，深度為h的滿(mǎn)二叉樹(shù)共有2h-1個(gè)結(jié)點(diǎn)?？梢詫?duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行順序編號(hào)。其規(guī)則是：樹(shù)中根結(jié)點(diǎn)的編號(hào)是1，然后按照層數(shù)從小到大、同一層內(nèi)從左到右的順序?qū)?shù)的每一個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)。若一棵深度為h的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為h的順序編號(hào)的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)這樣的二叉樹(shù)為完全二叉樹(shù)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的特例。

25、圖4.2(b)為一棵完全二叉樹(shù)，它與等深度的滿(mǎn)二叉樹(shù)相比，在最后一層的右邊缺少了4個(gè)結(jié)點(diǎn)。該樹(shù)中每個(gè)結(jié)點(diǎn)的值也是用該結(jié)點(diǎn)的編號(hào)來(lái)表示的。完全二叉樹(shù)的特點(diǎn)是：除最后一層外，其余各層都是滿(mǎn)的，并且最后一層或者是滿(mǎn)的，或者是在最右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。4、二叉鏈表數(shù)據(jù)類(lèi)型描述4、二叉鏈表數(shù)據(jù)類(lèi)型描述二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以有多種形式，通常使用的形式為：在每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，分別為數(shù)據(jù)域、左指針域和右指針域，其結(jié)點(diǎn)的結(jié)構(gòu)如圖4.5(a)所示。其中data表示數(shù)據(jù)域，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，left和right分別表示左指針域和右指針域，用來(lái)分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存儲(chǔ)位置，這種結(jié)構(gòu)稱(chēng)為二叉鏈表。

26、有時(shí)，為了便于找到結(jié)點(diǎn)的雙親，還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域，如圖4.5(b)所示，這種結(jié)構(gòu)稱(chēng)為三叉鏈表。例如圖4.6(a)所示的二叉樹(shù)，它的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種表示方法，在圖4.6(b)中，用二叉鏈表表示，結(jié)點(diǎn)不帶雙親指針，其中T1為指向根結(jié)點(diǎn)的指針，簡(jiǎn)稱(chēng)為根指針；在圖4.6(c)中，用三叉鏈表表示，結(jié)點(diǎn)帶有雙親指針，其中T2為根指針。在圖4.6(b)中，二叉樹(shù)的6個(gè)結(jié)點(diǎn)中共有7個(gè)空鏈域，容易證得，在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。在下一節(jié)中，我們將會(huì)看到可以利用這些空鏈域存儲(chǔ)其它有用信息，從而得到另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線索鏈表。根據(jù)以上所述，二叉鏈表的結(jié)點(diǎn)類(lèi)型可定義為：

27、typedefstructBiTreeNodeElemTypedata;structBiTreeNode*left;structBiTreeNode*right;BiTreeNode,*BiTreePtr;在元素結(jié)點(diǎn)中，data用來(lái)存儲(chǔ)數(shù)據(jù)元素，left和right分別用來(lái)存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存儲(chǔ)位置。與線性表中的靜態(tài)鏈表相似，我們還可以利用一組地址連續(xù)的內(nèi)存空間來(lái)描述二叉樹(shù)，把數(shù)組元素作為存儲(chǔ)結(jié)點(diǎn)，元素類(lèi)型包含數(shù)值域data和游標(biāo)指示器left和right，游標(biāo)定義為整型，left和right分別指示該結(jié)點(diǎn)的左孩子和右孩子結(jié)點(diǎn)在數(shù)組中的相對(duì)位置，若left或right游標(biāo)值為0，則該結(jié)點(diǎn)

28、無(wú)左孩子或右孩子結(jié)點(diǎn)。整個(gè)數(shù)組下標(biāo)為零的元素被看成是空閑鏈表的頭結(jié)點(diǎn)，該結(jié)點(diǎn)的left指向樹(shù)的根結(jié)點(diǎn)（一般設(shè)定樹(shù)的根結(jié)點(diǎn)存放在下標(biāo)為1的數(shù)組元素中，即根指針為1；當(dāng)然，樹(shù)為空時(shí)可設(shè)置根指針為0），該結(jié)點(diǎn)的right指向空閑鏈表的頭結(jié)點(diǎn)；在空閑鏈表中，結(jié)點(diǎn)的right指針指向下一個(gè)空閑結(jié)點(diǎn)。上述方式下存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類(lèi)型描述如下：typedefstructSBiTreeNodeElemTypedata;intleft,right;SBiTreeNode;下面我們用一個(gè)例子來(lái)具體描述其存儲(chǔ)結(jié)構(gòu)，如圖4.7所示。該存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是：建立好后可以把整個(gè)數(shù)組寫(xiě)入到文件中保存起來(lái)，當(dāng)需要時(shí)再?gòu)奈募w讀入到

29、數(shù)組進(jìn)行處理，但也有一些缺點(diǎn)，例如要預(yù)先分配一個(gè)較大的空間。5、二叉樹(shù)遍歷策略5、二叉樹(shù)遍歷策略二叉樹(shù)的遍歷二叉樹(shù)的遍歷是二叉樹(shù)中最重要的運(yùn)算，也是各種操作的基礎(chǔ)。二叉樹(shù)的遍歷是指按照某個(gè)搜索路徑尋訪樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。在遍歷的過(guò)程中，可以對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如：對(duì)于一棵已知樹(shù)可求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子結(jié)點(diǎn)，判定結(jié)點(diǎn)所在的層次等。根據(jù)二叉樹(shù)的遞歸定義，一棵非空二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成，因此，遍歷一棵二叉樹(shù)可以分解為三個(gè)問(wèn)題：訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)。若分別用D、L、R表示上述三個(gè)子問(wèn)題，則可能有DLR、LDR、LRD、DRL、RDL

30、、RLD幾種情況。若限定先左后右，則只有前3種情況：（1）DLR，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左、右子樹(shù)之前，故稱(chēng)之為先序遍歷或先根遍歷；（2）LDR，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左子樹(shù)之后、右子樹(shù)之前，故稱(chēng)之為中序遍歷或中根遍歷；（3）LRD，此時(shí)訪問(wèn)根結(jié)點(diǎn)的操作在遍歷左、右子樹(shù)之后，故稱(chēng)之為后序遍歷或后根遍歷。顯然，遍歷左、右子樹(shù)的問(wèn)題仍然是遍歷二叉樹(shù)的問(wèn)題，當(dāng)二叉樹(shù)為空時(shí)遞歸結(jié)束，所以，很容易給出這三種遍歷的遞歸算法。而上述的后三種情況與前三種情況的不同僅為前三種都是先遍歷左子樹(shù)，后遍歷右子樹(shù)，而后三種則相反。由于二者對(duì)稱(chēng)故我們只討論前三種遍歷方案，熟悉了前三種，后三種也就不成問(wèn)題了。6、二

31、叉樹(shù)遍歷遞歸算法6、二叉樹(shù)遍歷遞歸算法（二叉樹(shù)的先序遍歷遞歸算法、二叉樹(shù)的中序遍歷遞歸算法、二叉樹(shù)的后序遍歷遞歸算法）(1)先序遍歷算法StatusPreOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/該算法采用遞歸的方式，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visitif(T)if(visit(T-data,visit)if(PreOrderTraverse(T-left)if(PreOrderTraverse(T-right,visit)returnOK;returnERROR;elsere

32、turnOK;/PreOrderTraverse算法4-1二叉樹(shù)的先序遍歷遞歸算法(2)中序遍歷算法StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/該算法采用遞歸的方式，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visitif(T)if(InOrderTraverse(T-left,visit)if(visit(T-data)if(InOrderTraverse(T-right,visit)returnOK;returnERROR;elsereturnOK;/InOrderTraver

33、se算法4-2二叉樹(shù)的中序遍歷遞歸算法(3)后序遍歷算法StatusPostOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/該算法采用遞歸的方式，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visitif(T)if(PostOrderTraverse(T-left,visit)if(PostOrderTraverse(T-right,visit)if(visit(T-data)returnOK;returnERROR;elsereturnOK;/PostOrderTraverse算法4-3二叉樹(shù)的后序遍

34、歷遞歸算法以上的三種算法均為遞歸算法，在運(yùn)行過(guò)程中，函數(shù)需要使用系統(tǒng)設(shè)立的“遞歸工作?！贝鎯?chǔ)調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接及信息的交換。下面我們以中序算法為例，結(jié)合圖4.8(a)的二叉樹(shù)，分析它的執(zhí)行過(guò)程。當(dāng)開(kāi)始調(diào)用中序遍歷算法時(shí)（此次稱(chēng)為第0次遞歸調(diào)用），需要以指向根結(jié)點(diǎn)a的指針Ta作為實(shí)參，把它傳遞給形參T，遞歸棧中應(yīng)包括形參T的值和返回地址。現(xiàn)假定指向每個(gè)結(jié)點(diǎn)的指針用該結(jié)點(diǎn)的值作為T(mén)的后綴，如指向結(jié)點(diǎn)d的指針就用Td表示，并且假定進(jìn)行第0次遞歸調(diào)用后的返回地址為0，以及假設(shè)訪問(wèn)函數(shù)為打印輸出結(jié)點(diǎn)的值，則函數(shù)遞歸調(diào)用的過(guò)程中，遞歸工作棧的狀態(tài)如圖4.9所示。StatusInOrderTra

35、verse(BiTreePtrT,Status(*visit)(ElemTypee)if(T)if(InOrderTraverse(T-left,visit)if(visit(T-data)if(InOrderTraverse(T-right,visit)returnOK;returnERROR;elsereturnOK;s遞歸層次、語(yǔ)句行號(hào)及執(zhí)行結(jié)果遞歸工作棧狀態(tài)（返址，指針值）(1)一層1,2,30,Ta(2)二層1,2,34,Tb0,Ta(3)三層1,2,34,Td4,Tb0,Ta(4)四層1,2,94,Td4,Tb0,Ta4,(5)三層4,5輸出d4,Td4,Tb0,Ta(6)四層1,

36、2,34,Td4,Tb0,Ta6,Tg(7)五層1,2,94,Td4,Tb0,Ta6,Tg4,(8)四層4,5輸出g4,Td4,Tb0,Ta6,Tg(9)五層1,2,94,Td4,Tb0,Ta6,Tg6,(10)四層64,Td4,Tb0,Ta6,Tg(11)三層64,Td4,Tb0,Ta(12)二層4,5輸出b4,Tb0,Ta(13)三層1,2,96,4,Tb0,Ta(14)二層64,Tb0,Ta(15)一層4,5輸出a0,Ta(16)二層1,2,36,Tc0,Ta(17)三層1,2,34,Te6,Tc0,Ta(18)四層1,2,94,Te6,Tc0,Ta4,(19)三層4,5輸出e4,Te6

37、,Tc0,Ta(20)四層1,2,94,Te6,Tc0,Ta6,(21)三層64,Te6,Tc0,Ta(22)二層4,5輸出c6,Tc0,Ta(23)三層1,2,36,Tf6,Tc0,Ta(24)四層1,2,96,Tf6,Tc0,Ta4,(25)三層4,5輸出f6,Tf6,Tc0,Ta(26)四層1,2,96,Tf6,Tc0,Ta6,(27)三層66,Tf6,Tc0,Ta(28)二層66,Tc0,Ta(29)一層60,Ta(30)0層0?？?qǐng)D4.9二叉樹(shù)中序遍歷調(diào)用的過(guò)程中，遞歸工作棧的狀態(tài)上述分析的中序遍歷的算法，最終打印出的結(jié)點(diǎn)序列為：dgbaecf若按照前序遍歷算法和后序遍歷算法遍歷圖4

38、.8所示的二叉樹(shù)，則打印出的結(jié)點(diǎn)序列分別為：abdgcef和gdbefca對(duì)于上述遍歷遞歸算法執(zhí)行過(guò)程中遞歸工作棧狀態(tài)的變化，我們可以通過(guò)人工建立棧仿照上述過(guò)程。具體算法描述如下：StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-left;/根指針進(jìn)棧后，先遍歷左子樹(shù)else/根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)Pop(S,p);if(!visit(p-

39、data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉樹(shù)的中序遍歷非遞歸算法對(duì)于二叉樹(shù)進(jìn)行遍歷操作的路徑除了上述的按先序、中序或后序外，還可以從上到下、從左到右按層次進(jìn)行。在二叉樹(shù)的遍歷算法中，訪問(wèn)每個(gè)結(jié)點(diǎn)的每一個(gè)域，并且每個(gè)結(jié)點(diǎn)的每一個(gè)域僅被訪問(wèn)一次，所以算法的時(shí)間復(fù)雜度為O(n)。7、二叉樹(shù)中序遍歷非遞歸算法7、二叉樹(shù)中序遍歷非遞歸算法StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi

40、sit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-left;/根指針進(jìn)棧后，先遍歷左子樹(shù)else/根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)Pop(S,p);if(!visit(p-data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉樹(shù)的中序遍歷非遞歸算法8、二叉樹(shù)的其他運(yùn)算8、二叉樹(shù)的其他運(yùn)算（二叉樹(shù)生成算法、二叉樹(shù)的深度求解算法、刪除二叉樹(shù)中指定結(jié)點(diǎn)的算法、清空二叉樹(shù)的算法）生成二叉樹(shù)建立二叉樹(shù)的過(guò)程中，既可以使用逐個(gè)輸入結(jié)點(diǎn)的方式，也可

41、以一次性輸入樹(shù)的所有結(jié)點(diǎn)。本算法采用后者的方式建立樹(shù)，對(duì)于這種方式，我們可使用廣義表一次性輸入所有結(jié)點(diǎn)。二叉樹(shù)廣義表表示的規(guī)定如下：1）每棵樹(shù)的根結(jié)點(diǎn)作為由子樹(shù)構(gòu)成的表的名字而放在表的前面；2）每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)用逗號(hào)隔開(kāi)，若只有右子樹(shù)，則逗號(hào)不能省略。例如，對(duì)于圖4.10所示的二叉樹(shù)，其廣義表表示為：a(b(,e(h),c(f(,i)通過(guò)二叉樹(shù)的廣義表建立二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本思路是：從保存二叉樹(shù)廣義表的字符串tree中讀取每個(gè)字符，i.若遇到空格則不進(jìn)行任何操作；ii.若遇到左括號(hào)，則表明子表開(kāi)始，應(yīng)首先用棧存儲(chǔ)指向它前面的字母所在結(jié)點(diǎn)的指針，以便括號(hào)內(nèi)的孩子結(jié)點(diǎn)向雙親結(jié)點(diǎn)鏈接，

42、然后由于左括號(hào)后面緊跟的字母（若存在）必為剛進(jìn)棧結(jié)點(diǎn)的左孩子，設(shè)定變量k=1，表示將進(jìn)行左孩子結(jié)點(diǎn)鏈接（k=2表示將進(jìn)行右孩子結(jié)點(diǎn)鏈接）；iii.若遇到的是字母（假設(shè)以字母作為結(jié)點(diǎn)的值），應(yīng)為它建立一個(gè)新結(jié)點(diǎn)，并把該結(jié)點(diǎn)（若它不是根結(jié)點(diǎn)）作為左孩子（若k=1）或右孩子（若k=2）鏈接到其雙親結(jié)點(diǎn)上，即當(dāng)前棧頂元素所指向的結(jié)點(diǎn)；iv.若遇到逗號(hào)，則表明應(yīng)開(kāi)始處理右孩子結(jié)點(diǎn)向其雙親結(jié)點(diǎn)的鏈接，使k=2;v.若遇到右括號(hào)，則表明該子表結(jié)束，應(yīng)退棧。按照如上所述方式處理每個(gè)字符，直到字符串讀完為止。具體算法如下：voidCreatBiTree1(BiTreePtr&T,char*tree)/通過(guò)保存二

43、叉樹(shù)廣義表的字符串tree建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)BiTreePtrp,e;/p為指向二叉樹(shù)結(jié)點(diǎn)的指針intk；/用k作為鏈接結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的標(biāo)記/k=1表示左子樹(shù)，k=2表示右子樹(shù)inti=0;/用i掃描字符串treeInitStack(S);/建立鏈棧，棧元素為二叉樹(shù)結(jié)點(diǎn)的指針T=NULL;/樹(shù)初始化為空while(treei)/每循環(huán)一次處理一個(gè)字符，直到掃描到字符串結(jié)束符為止switch(treei)case:/對(duì)空格不作任何處理break;case(:Push(S,p);k=1;break;case):if(StackEmpty(S)print(“存儲(chǔ)二叉樹(shù)廣義表的字符串有錯(cuò)誤”);e

44、xit(1);Pop(S,e);break;case,:k=2;break;default:p=(BiTreePtr)malloc(sizeof(BiTreeNode);p-data=treei;p-left=p-right=NULL;if(T=NULL)T=p;elseGetTop(S,e);if(k=1)e-left=p;elsee-right=p;/switchi+;/掃描下一個(gè)字符/while算法4-6二叉鏈表的生成算法在上述算法中，我們使用棧存儲(chǔ)指向二叉樹(shù)結(jié)點(diǎn)的指針，那么，我們能否不通過(guò)定義棧直接按照上述算法中的思想完成樹(shù)的建立呢？在棧的遍歷中，我們看到遞歸思想的應(yīng)用，下面給出的改寫(xiě)

45、算法，也是通過(guò)遞歸的方式完成上述操作，本算法具體思想由讀者去進(jìn)一步思考。StatusCreatBiTree2(BiTreePtr&T)staticchartree100;staticintx=0;if(x=0)scanf(%s,tree);switch(treex)case:break;/讀入空格后繼續(xù)讀取case(:x+;CreatBiTree2(T-left);/開(kāi)始遞歸處理該結(jié)點(diǎn)的左子樹(shù)if(treex=,)x+;CreatBiTree2(T-right);/對(duì)于逗號(hào)，退出到該層遞歸后處理結(jié)點(diǎn)右子樹(shù)if(treex=)x+;CreatBiTree2(T);/對(duì)于右括號(hào)，退出到該層遞歸后處

46、理新結(jié)點(diǎn)break;case):break;/對(duì)于右括號(hào)不作任何處理，退出一層遞歸case,:break;/對(duì)于逗號(hào)，退出一層遞歸后處理結(jié)點(diǎn)右子樹(shù)caseNULL:break;/數(shù)組tree尾部default:if(!(T=(BiTreeNode*)malloc(sizeof(BiTreeNode)exit(OVERFLOW);T-data=treex;T-left=T-right=NULL;x+;CreatBiTree2(T);returnOK;算法4-7二叉鏈表的遞歸生成算法求二叉樹(shù)的深度該算法采用遞歸的思想：若一棵二叉樹(shù)為空，則它的深度為0，否則它的深度等于左子樹(shù)和右子樹(shù)中的最大深度加1

47、。設(shè)depthL為左子樹(shù)的深度，depthR為右子樹(shù)的深度，則二叉樹(shù)的深度為：max(depthL,depthR)+1其中max函數(shù)表示取參數(shù)中的較大者。該算法具體描述如下：IntBiTreeDepth(BiTreePtrT)if(T=NULL)return0;/對(duì)于空樹(shù)，返回0并結(jié)束遞歸elseintdepthL=BiTreeDepth(T-left);/計(jì)算左子樹(shù)的深度intdepthR=BiTreeDepth(T-right);/計(jì)算右子樹(shù)的深度return(depthLdepthR)?depthL+1:depthR+1;/返回樹(shù)的深度算法4-8二叉樹(shù)的深度求解算法刪除二叉樹(shù)中指定結(jié)點(diǎn)要

48、刪除指定結(jié)點(diǎn)及其左右子樹(shù)，需分三種情況討論：i.被刪除結(jié)點(diǎn)無(wú)前驅(qū)，即樹(shù)的根結(jié)點(diǎn)，則先清空根結(jié)點(diǎn)的左子樹(shù)，再清空右子樹(shù)，最后刪除（即釋放）根結(jié)點(diǎn)，并把根指針置空。ii.被刪除結(jié)點(diǎn)無(wú)后繼，即葉子結(jié)點(diǎn)，則釋放該結(jié)點(diǎn)，并且將其雙親結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針置空。iii.被刪除結(jié)點(diǎn)有后繼和前驅(qū)，則清空該結(jié)點(diǎn)左右子樹(shù)，然后釋放該結(jié)點(diǎn)，且將其雙親結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針置空。以上三種情況可歸結(jié)為，判斷該結(jié)點(diǎn)是否有后繼，若有，則以遞歸的方式清空左右子樹(shù)，若無(wú)則不操作；判斷該結(jié)點(diǎn)是否有雙親結(jié)點(diǎn)，若有則將其指向該結(jié)點(diǎn)的指針置空，若無(wú)則不操作；釋放該結(jié)點(diǎn)空間。具體算法描述如下：StatusDelBiTreeNode(BiTr

49、eePtr&T)/刪除T指向的結(jié)點(diǎn)及其子樹(shù)if(T!=NULL)DelBiTreeNode(T-left);/刪除左子樹(shù)DelBiTreeNode(T-right);/刪除右子樹(shù)if(Parent(T,T-data,P)/雙親結(jié)點(diǎn)中指向該結(jié)點(diǎn)的指針置空if(p!=NULL)if(P-left=T)P-left=NULL;if(P-right=T)P-right=NULL;free(T);/釋放該結(jié)點(diǎn)returnOK;算法4-10刪除二叉樹(shù)中指定結(jié)點(diǎn)的算法清空二叉樹(shù)該算法與刪除指定結(jié)點(diǎn)的算法類(lèi)似，即為刪除根結(jié)點(diǎn)。算法描述如下：StatusClearBiTree(BiTreePtr&T)if(T!

50、=NULL)ClearBiTree(T-left);/刪除左子樹(shù)ClearBiTree(T-right);/刪除左子樹(shù)free(T);/釋放根結(jié)點(diǎn)T=NULL;/根指針置空算法4-11清空二叉樹(shù)的算法第三節(jié)線索二叉樹(shù)遍歷二叉樹(shù)實(shí)現(xiàn)了樹(shù)型非線性結(jié)構(gòu)的線性化，形成了二叉樹(shù)結(jié)點(diǎn)的線性序列。為了便于查找某個(gè)結(jié)點(diǎn)在線性序列中的前驅(qū)和后繼信息，需要將二叉樹(shù)線索化。1、線索鏈表的數(shù)據(jù)類(lèi)型1、線索鏈表的數(shù)據(jù)類(lèi)型作為二叉樹(shù)基本的操作，遍歷二叉樹(shù)是以一定規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排成一個(gè)線性序列，這可看成是對(duì)樹(shù)這種非線性結(jié)構(gòu)進(jìn)行線性化的操作，它使得每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)外）在這個(gè)線性序列中都有唯一的直接前驅(qū)和直接

51、后繼。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能較為方便地找到結(jié)點(diǎn)的左右孩子的信息，而不能直接得到在結(jié)點(diǎn)的線性序列中的前驅(qū)與后繼信息，這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。為了能方便獲得和利用某種遍歷過(guò)程中的前驅(qū)與后繼結(jié)點(diǎn)的信息，可以在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針?lè)謩e保存它們，但我們注意到在二叉鏈表中有大量的空指針（n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域），我們可以充分利用這些空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼的信息。具體來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)有左（右）子結(jié)點(diǎn)時(shí)，其左（右）指針指向該子結(jié)點(diǎn)，或無(wú)左（右）子結(jié)點(diǎn)，則其左（右）指針指向其前驅(qū)（后繼）結(jié)點(diǎn)。當(dāng)然為了區(qū)分這些指針是指向其子結(jié)點(diǎn)還是指向其前驅(qū)或后繼結(jié)點(diǎn)，需要在結(jié)點(diǎn)的數(shù)

52、據(jù)類(lèi)型中增加兩個(gè)標(biāo)志域ltag、rtag，如圖4.11所示。以這種結(jié)點(diǎn)類(lèi)型構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表，其中指向結(jié)點(diǎn)前驅(qū)或后繼的指針?lè)Q為線索，加上線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù)。其中：所以，線索二叉樹(shù)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)為：typedefenumLink,ThreadPTag;/Link=0：指針，Thread=1：線索typedefstructBiThrNodeElemTypedata;structBiThrNode*left,*right;/左右孩子指針PTagltag,rtag;/左右標(biāo)志BiThrNode,*BiThrTree;2、二叉樹(shù)的中序線索化算法2、二叉樹(shù)的中序線索化

53、算法這個(gè)過(guò)程實(shí)際上就是將已經(jīng)建立好的二叉鏈表中的空指針改為指向前驅(qū)或者后繼的線索。由于在二叉樹(shù)的遍歷過(guò)程中，我們可以得到結(jié)點(diǎn)的前驅(qū)或后繼的信息，因此，線索化的過(guò)程即為在遍歷過(guò)程中修改空指針的過(guò)程。為了能在遍歷過(guò)程中記錄訪問(wèn)結(jié)點(diǎn)的先后關(guān)系，我們附設(shè)一個(gè)全局變量指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)。若指針指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)，則pre指向它的前驅(qū)，而當(dāng)前訪問(wèn)的結(jié)點(diǎn)又是pre的后繼。pre的初值為NULL。二叉樹(shù)的中序線索化算法如下所示：StatusInOrderThreading(BiThrTree&T)/中序遍歷二叉樹(shù)T，并將其中序線索化，T指向樹(shù)或子樹(shù)的根結(jié)點(diǎn)。p=T;if(p)InOrderTh

54、reading(T-left);/左子樹(shù)線索化if(!p-left)p-ltag=Thread;p-left=pre;/前驅(qū)線索標(biāo)記if(pre&!pre-right)pre-rtag=Thread;pre-right=p;/pre為全局變量，初值為NULL；后繼線索標(biāo)記pre=p;/pre始終指向前驅(qū)InOrderThreading(T-right);/右子樹(shù)線索化returnOK;/InOrderThreading算法4-13二叉樹(shù)的中序線索化算法3、中序線索二叉樹(shù)的遍歷算法3、中序線索二叉樹(shù)的遍歷算法在線索二叉樹(shù)上進(jìn)行遍歷，只需要從序列的第一個(gè)結(jié)點(diǎn)開(kāi)始訪問(wèn)，然后通過(guò)依次尋找結(jié)點(diǎn)的后繼進(jìn)行

55、遍歷，當(dāng)后繼為空時(shí)，遍歷即可結(jié)束。當(dāng)然，線索二叉樹(shù)總是與某種遍歷次序相關(guān)的，我們下面主要以中序遍歷為主來(lái)考慮線索二叉樹(shù)。以圖4.12為例，樹(shù)中所有葉子結(jié)點(diǎn)的左、右鏈?zhǔn)蔷€索，此時(shí)，右鏈域直接指示了結(jié)點(diǎn)的后繼，如結(jié)點(diǎn)g的后繼為結(jié)點(diǎn)b。樹(shù)中所有存在右孩子結(jié)點(diǎn)的右鏈均為指針，則無(wú)法直接得到該結(jié)點(diǎn)后繼的信息。但是，根據(jù)中序遍歷的規(guī)則，該結(jié)點(diǎn)的后繼應(yīng)是遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)，即為該結(jié)點(diǎn)的右子樹(shù)中最左下的結(jié)點(diǎn)。例如，找結(jié)點(diǎn)a的后繼，首先應(yīng)沿著其右指針，找到它的右孩子結(jié)點(diǎn)c，然后，順著左指針一直往下，直到左標(biāo)志為1時(shí)，意味著該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)，即該結(jié)點(diǎn)為a的后繼，在圖中是結(jié)點(diǎn)e。根據(jù)如上所述，則遍歷中序

56、線索二叉樹(shù)的算法為：StatusInOrderTaverse_Thr(BiThrTreeT,Status(*visit)(ElemTypee)/T指向根結(jié)點(diǎn)，遍歷中序線索二叉樹(shù)p=T;/p指向根結(jié)點(diǎn)while(p!=NULL)/空樹(shù)或遍歷結(jié)束時(shí)，p=NULLwhile(p-ltag=Link)p=p-left;if(!visit(p-data)returnERROR;/訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn)while(p-rtag=Thread&p-right!=NULL)p=p-right;visit(p-data);/訪問(wèn)后繼結(jié)點(diǎn)p=p-right;returnOK;/InOrderTraverse_Th

57、r算法4-12中序線索二叉樹(shù)的遍歷算法由此算法可以看出，對(duì)于中序線索二叉樹(shù)的遍歷，雖然時(shí)間復(fù)雜度為O(n)，但是算法的實(shí)際頻數(shù)要比二叉鏈表的遞歸遍歷算法低，而且不需要設(shè)棧。因此，若在某程序中所使用的二叉樹(shù)經(jīng)常需要遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼，則應(yīng)采用線索鏈表作為存儲(chǔ)結(jié)構(gòu)。第四節(jié)樹(shù)和森林為了便于樹(shù)的操作，通常將樹(shù)轉(zhuǎn)化為二叉樹(shù)。本節(jié)討論樹(shù)的表示及基本的遍歷操作，并說(shuō)明樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)化關(guān)系。1、一般樹(shù)轉(zhuǎn)化成二叉樹(shù)的規(guī)則2、森林轉(zhuǎn)化成二叉樹(shù)的規(guī)則2、森林轉(zhuǎn)化成二叉樹(shù)的規(guī)則任何一棵樹(shù)都能按照一定的方式表示成二叉樹(shù)，這樣對(duì)樹(shù)的計(jì)算機(jī)表示和操作等，只要利用二叉樹(shù)即可。一般樹(shù)轉(zhuǎn)化為二叉

58、樹(shù)的規(guī)則為：（1）一般樹(shù)的根對(duì)應(yīng)二叉樹(shù)的根；（2）對(duì)樹(shù)中任意結(jié)點(diǎn)，轉(zhuǎn)化為二叉樹(shù)的結(jié)點(diǎn)后，該結(jié)點(diǎn)原最左邊的孩子結(jié)點(diǎn)作為轉(zhuǎn)化后它的左孩子結(jié)點(diǎn)，該結(jié)點(diǎn)原右邊相鄰的第一個(gè)兄弟結(jié)點(diǎn)作為轉(zhuǎn)化后它的右孩子結(jié)點(diǎn)，并依此類(lèi)推。例如，設(shè)它的孩子結(jié)點(diǎn)依次為T(mén)s1,Ts2,，兄弟結(jié)點(diǎn)依次為T(mén)B1,TB2,，則對(duì)應(yīng)二叉樹(shù)時(shí)，該結(jié)點(diǎn)的左孩子為T(mén)s1，右孩子為T(mén)B1，Ts1的右孩子結(jié)點(diǎn)為T(mén)s2，TB1的右孩子結(jié)點(diǎn)為T(mén)B2。這樣樹(shù)中任一結(jié)點(diǎn)的子結(jié)點(diǎn)對(duì)應(yīng)二叉樹(shù)中結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)及沿著該子結(jié)點(diǎn)的右分支路徑至末端的各結(jié)點(diǎn)，顯然這樣轉(zhuǎn)化的二叉樹(shù)根結(jié)點(diǎn)無(wú)右子樹(shù)，這是根結(jié)點(diǎn)沒(méi)有兄弟結(jié)點(diǎn)的必然結(jié)果。圖4.16給出了一個(gè)具體的樹(shù)轉(zhuǎn)化成二叉

59、樹(shù)的例子。如果把森林中第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則同樣可推導(dǎo)出森林和二叉樹(shù)的轉(zhuǎn)化。森林轉(zhuǎn)化成二叉樹(shù)的規(guī)則是：（1）若森林為空，則對(duì)應(yīng)的二叉樹(shù)為空；（2）若森林非空，將森林中所有的樹(shù)按照規(guī)則轉(zhuǎn)化為二叉樹(shù)；（3）設(shè)置一個(gè)虛擬根結(jié)點(diǎn)，該結(jié)點(diǎn)的子樹(shù)從左到右依次為森林中從左到右的樹(shù)，即將所有的二叉樹(shù)連接到虛擬根結(jié)點(diǎn)上；（4）將這棵樹(shù)按照規(guī)則轉(zhuǎn)化為二叉樹(shù)（實(shí)際僅需一層操作，即原各棵樹(shù)的根結(jié)點(diǎn)按照兄弟結(jié)點(diǎn)的規(guī)則進(jìn)行轉(zhuǎn)化，在此過(guò)程中各根結(jié)點(diǎn)帶上原子樹(shù)一起移動(dòng)）；（5）去掉虛擬根結(jié)點(diǎn)，則二叉樹(shù)的根結(jié)點(diǎn)為原第一棵樹(shù)的根結(jié)點(diǎn)。二叉樹(shù)轉(zhuǎn)化成森林的規(guī)則是：（1）若二叉樹(shù)為空，則對(duì)應(yīng)的森林為空；（

60、2）若二叉樹(shù)非空，則對(duì)應(yīng)的森林中第一棵樹(shù)的根結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn)，根結(jié)點(diǎn)的子樹(shù)森林是由二叉樹(shù)的左子樹(shù)轉(zhuǎn)化而成的森林；森林中除第一棵樹(shù)之外其余樹(shù)組成的森林是由二叉樹(shù)的右子樹(shù)轉(zhuǎn)化而成的森林。3、森林的遍歷策略3、森林的遍歷策略有兩種次序遍歷樹(shù)的方法：一種是先根(次序)遍歷樹(shù)，另一種是后根(次序)遍歷樹(shù)。前者先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根結(jié)點(diǎn)的每棵子樹(shù)；后者則是先依次后根遍歷每棵子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)。按照森林和樹(shù)相互遞歸的定義，可以得到森林的兩種遍歷方法：1.先序遍歷森林若森林非空，則可按下述規(guī)則對(duì)其進(jìn)行遍歷：（1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；（2）先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；（3）