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

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

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

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

4、)表示有8個(gè)結(jié)點(diǎn)的樹，其中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的子樹，且本身也是一棵樹。如T1的根結(jié)點(diǎn)為B，其余結(jié)點(diǎn)分為3個(gè)互不相交的子集：T11=E,T12=F,T13=G。T11、T12和T13都是T1的根結(jié)點(diǎn)B的子樹。2.樹的非遞歸定義樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合T，不含有任何結(jié)點(diǎn)（元素）的樹稱為空樹，而在任一非空樹中定義了一個(gè)關(guān)系，它滿足：（1）T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒有前驅(qū)，稱為樹的根；（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)序列稱為從根結(jié)點(diǎn)到結(jié)點(diǎn)a的路徑。例如，在圖4.1(b)中，A為樹的根結(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ù)據(jù)類型2、樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型定義如下：ADTTree數(shù)據(jù)對(duì)象D：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則RH，H滿足關(guān)系：(1)T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒有前驅(qū)，稱為樹的根，用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的一條路徑。基本操作P：InitTree(&T);操作結(jié)果：構(gòu)造空樹T。CreateTree(&T,tree);初始條件：tree給出T的表示形式。操作結(jié)果：按tree構(gòu)造T。TreeEmpty(T);初始條件：樹T存在。操作結(jié)果：若T為空樹，

7、則返回TRUE，否則返回FALSE。TreeDepth(T);初始條件：樹T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：樹T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：樹T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE。Assign(T,e,value);初始條件：樹T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則結(jié)點(diǎn)e賦值為value，函數(shù)返回TRUE，否則返回FALSE。Parent(T,e,&P);初始條件：樹T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若樹中存在值為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);初始條件：樹T存在，P指向該二叉樹中的一個(gè)結(jié)點(diǎn)。操作結(jié)果：刪除P所指向的結(jié)點(diǎn)及其子樹。TraverseTree(T,visit();初始條件：樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。ClearTree(&T);初始條件：樹T存在。操作結(jié)果：將樹T清空。DestroyTree(&T);初始條件：樹T存在。操作結(jié)果：將樹T銷毀。ADTTree該抽象數(shù)據(jù)類型中，定義了樹的若干基本操作，

9、另外，對(duì)樹的操作還可有插入結(jié)點(diǎn)操作、插入子樹操作、旋轉(zhuǎn)樹操作等3、樹的基本術(shù)語3、樹的基本術(shù)語（樹結(jié)點(diǎn)、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、度、深度）樹的結(jié)點(diǎn)樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)的度和樹的度樹中每個(gè)結(jié)點(diǎn)所擁有的非空子樹數(shù)稱為結(jié)點(diǎn)的度（Degree）。樹的度是樹中所有結(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，故樹的度為3。葉子結(jié)點(diǎn)和分支結(jié)點(diǎn)樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)以外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。在分支結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)

10、的度數(shù)。度為1的結(jié)點(diǎn)，其分支數(shù)為1，稱為單分支結(jié)點(diǎn)；度為2的結(jié)點(diǎn)，其分支數(shù)為2，稱為雙分支結(jié)點(diǎn)，其余類推。如在圖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)樹中每個(gè)結(jié)點(diǎn)的子樹的根（即每個(gè)結(jié)點(diǎn)的后繼）稱為該結(jié)點(diǎn)的孩子、兒子或子女（Child），相應(yīng)地，該結(jié)點(diǎn)稱為子結(jié)點(diǎn)的雙親（Parent）。具有同一個(gè)雙親的孩子之間互稱兄弟（Brothers）。雙親在同一層上的結(jié)點(diǎn)互稱為堂兄弟。以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫，相應(yīng)地，結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)的路徑上經(jīng)過的所有分支結(jié)點(diǎn)。在一棵樹中，根結(jié)

11、點(diǎn)沒有雙親結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有子結(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ù)和樹的深度樹既是一種遞歸結(jié)構(gòu)，也是一種層次結(jié)構(gòu)。結(jié)點(diǎn)的層數(shù)（Level）從根開始定義起，根結(jié)點(diǎn)為第一層，它的子結(jié)點(diǎn)為第二層，以此類推。如果某個(gè)結(jié)點(diǎn)在第k層，則其子樹的根位于第k+1層。樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度（Depth）或高度。如在圖4.1(b)中，結(jié)點(diǎn)A為第一層，B、C、D為第二層，E、F、G、H為第三層，樹中結(jié)點(diǎn)的最大層數(shù)是3，故樹的深度為3。有序樹和無序樹如果

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

13、據(jù)樹的定義，在一個(gè)樹中，除了根結(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ù)），因此可得出樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。性質(zhì)2：度為k的樹中第i層上至多有ki-1個(gè)結(jié)點(diǎn)（i1）。利用數(shù)學(xué)歸納法可以證明此性質(zhì)。對(duì)于第一層顯然是成立的。因?yàn)闃渲械牡谝粚由现挥懈Y(jié)點(diǎn)，而i=1時(shí)，ki-1=k0=1，同樣也得到只有一個(gè)結(jié)點(diǎn)。假設(shè)對(duì)于第i-1層（i1）命題成立，即度為k的樹中第i-1層上至多有k(i-1)-1=ki-2個(gè)結(jié)點(diǎn)，則根據(jù)樹的度的定義，度為k的樹中每個(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叉樹至多有（kh-1）/（k-1）個(gè)結(jié)點(diǎn)。由性質(zhì)2可知，當(dāng)深度為h的k叉樹（即度為k的樹）上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí)，所有結(jié)點(diǎn)的總和為：，故深度為h的k叉樹至多有個(gè)結(jié)點(diǎn)。當(dāng)一棵k叉樹上的結(jié)點(diǎn)數(shù)等于時(shí)，即k叉樹的結(jié)點(diǎn)數(shù)達(dá)到了最大值時(shí)，則稱該樹為滿k叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的k叉樹的最小深度為。（其中符號(hào)表示對(duì)x進(jìn)行向上取整，如。）假設(shè)具有n個(gè)結(jié)點(diǎn)的k叉樹的深度為h，若在該樹中前h-1層都是滿的，即第i層的結(jié)點(diǎn)數(shù)等于ki-1個(gè)（1ih-1），最后一層即第h層的結(jié)

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

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

17、D為空集，則稱為空二叉樹。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則RH，H滿足關(guān)系：(1)T中存在唯一的一個(gè)結(jié)點(diǎn)，它沒有前驅(qū)，稱為樹的根，用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，則稱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)造空二叉樹T。CreateBiTree(&T,tree);初始條件：tree給出二叉樹T的表示形式。操作結(jié)果：按tree構(gòu)造二叉樹T。BiTreeEmpty(T);初始條件：二叉樹T存在。操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。BiTreeDepth(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：二叉樹T存在，e是需尋找的結(jié)點(diǎn)的值。操作結(jié)果：若找到該結(jié)點(diǎn)，則函數(shù)返回TRUE，否則返回FALSE。Assign(T,e,va

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

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

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

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

23、；如果n為偶數(shù)，則編號(hào)最大的分支結(jié)點(diǎn)即n/2只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。（2）如果i1，則結(jié)點(diǎn)i無雙親，是二叉樹的根；如果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)，無左孩子；否則，其左孩子是結(jié)點(diǎn)2i。（4）如果2i1n，則結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn)2i1。3、滿二叉樹、完全二叉樹3、滿二叉樹、完全二叉樹下面介紹兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。在一棵二叉樹中，當(dāng)?shù)趇

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

25、圖4.2(b)為一棵完全二叉樹，它與等深度的滿二叉樹相比，在最后一層的右邊缺少了4個(gè)結(jié)點(diǎn)。該樹中每個(gè)結(jié)點(diǎn)的值也是用該結(jié)點(diǎn)的編號(hào)來表示的。完全二叉樹的特點(diǎn)是：除最后一層外，其余各層都是滿的，并且最后一層或者是滿的，或者是在最右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。4、二叉鏈表數(shù)據(jù)類型描述4、二叉鏈表數(shù)據(jù)類型描述二叉樹的鏈?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分別表示左指針域和右指針域，用來分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存儲(chǔ)位置，這種結(jié)構(gòu)稱為二叉鏈表。

26、有時(shí)，為了便于找到結(jié)點(diǎn)的雙親，還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域，如圖4.5(b)所示，這種結(jié)構(gòu)稱為三叉鏈表。例如圖4.6(a)所示的二叉樹，它的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種表示方法，在圖4.6(b)中，用二叉鏈表表示，結(jié)點(diǎn)不帶雙親指針，其中T1為指向根結(jié)點(diǎn)的指針，簡稱為根指針；在圖4.6(c)中，用三叉鏈表表示，結(jié)點(diǎn)帶有雙親指針，其中T2為根指針。在圖4.6(b)中，二叉樹的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)類型可定義為：

27、typedefstructBiTreeNodeElemTypedata;structBiTreeNode*left;structBiTreeNode*right;BiTreeNode,*BiTreePtr;在元素結(jié)點(diǎn)中，data用來存儲(chǔ)數(shù)據(jù)元素，left和right分別用來存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存儲(chǔ)位置。與線性表中的靜態(tài)鏈表相似，我們還可以利用一組地址連續(xù)的內(nèi)存空間來描述二叉樹，把數(shù)組元素作為存儲(chǔ)結(jié)點(diǎn)，元素類型包含數(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、無左孩子或右孩子結(jié)點(diǎn)。整個(gè)數(shù)組下標(biāo)為零的元素被看成是空閑鏈表的頭結(jié)點(diǎn)，該結(jié)點(diǎn)的left指向樹的根結(jié)點(diǎn)（一般設(shè)定樹的根結(jié)點(diǎn)存放在下標(biāo)為1的數(shù)組元素中，即根指針為1；當(dāng)然，樹為空時(shí)可設(shè)置根指針為0），該結(jié)點(diǎn)的right指向空閑鏈表的頭結(jié)點(diǎn)；在空閑鏈表中，結(jié)點(diǎn)的right指針指向下一個(gè)空閑結(jié)點(diǎn)。上述方式下存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型描述如下：typedefstructSBiTreeNodeElemTypedata;intleft,right;SBiTreeNode;下面我們用一個(gè)例子來具體描述其存儲(chǔ)結(jié)構(gòu)，如圖4.7所示。該存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是：建立好后可以把整個(gè)數(shù)組寫入到文件中保存起來，當(dāng)需要時(shí)再從文件整體讀入到

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

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

31、叉樹遍歷遞歸算法6、二叉樹遍歷遞歸算法（二叉樹的先序遍歷遞歸算法、二叉樹的中序遍歷遞歸算法、二叉樹的后序遍歷遞歸算法）(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二叉樹的先序遍歷遞歸算法(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二叉樹的中序遍歷遞歸算法(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二叉樹的后序遍

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

38、.8所示的二叉樹，則打印出的結(jié)點(diǎn)序列分別為：abdgcef和gdbefca對(duì)于上述遍歷遞歸算法執(zhí)行過程中遞歸工作棧狀態(tài)的變化，我們可以通過人工建立棧仿照上述過程。具體算法描述如下：StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍歷二叉樹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)棧后，先遍歷左子樹else/根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹Pop(S,p);if(!visit(p-

39、data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉樹的中序遍歷非遞歸算法對(duì)于二叉樹進(jìn)行遍歷操作的路徑除了上述的按先序、中序或后序外，還可以從上到下、從左到右按層次進(jìn)行。在二叉樹的遍歷算法中，訪問每個(gè)結(jié)點(diǎn)的每一個(gè)域，并且每個(gè)結(jié)點(diǎn)的每一個(gè)域僅被訪問一次，所以算法的時(shí)間復(fù)雜度為O(n)。7、二叉樹中序遍歷非遞歸算法7、二叉樹中序遍歷非遞歸算法StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍歷二叉樹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)棧后，先遍歷左子樹else/根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹Pop(S,p);if(!visit(p-data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉樹的中序遍歷非遞歸算法8、二叉樹的其他運(yùn)算8、二叉樹的其他運(yùn)算（二叉樹生成算法、二叉樹的深度求解算法、刪除二叉樹中指定結(jié)點(diǎn)的算法、清空二叉樹的算法）生成二叉樹建立二叉樹的過程中，既可以使用逐個(gè)輸入結(jié)點(diǎn)的方式，也可

41、以一次性輸入樹的所有結(jié)點(diǎn)。本算法采用后者的方式建立樹，對(duì)于這種方式，我們可使用廣義表一次性輸入所有結(jié)點(diǎn)。二叉樹廣義表表示的規(guī)定如下：1）每棵樹的根結(jié)點(diǎn)作為由子樹構(gòu)成的表的名字而放在表的前面；2）每個(gè)結(jié)點(diǎn)的左子樹和右子樹用逗號(hào)隔開，若只有右子樹，則逗號(hào)不能省略。例如，對(duì)于圖4.10所示的二叉樹，其廣義表表示為：a(b(,e(h),c(f(,i)通過二叉樹的廣義表建立二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本思路是：從保存二叉樹廣義表的字符串tree中讀取每個(gè)字符，i.若遇到空格則不進(jìn)行任何操作；ii.若遇到左括號(hào)，則表明子表開始，應(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)開始處理右孩子結(jié)點(diǎn)向其雙親結(jié)點(diǎn)的鏈接，使k=2;v.若遇到右括號(hào)，則表明該子表結(jié)束，應(yīng)退棧。按照如上所述方式處理每個(gè)字符，直到字符串讀完為止。具體算法如下：voidCreatBiTree1(BiTreePtr&T,char*tree)/通過保存二

43、叉樹廣義表的字符串tree建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)BiTreePtrp,e;/p為指向二叉樹結(jié)點(diǎn)的指針intk；/用k作為鏈接結(jié)點(diǎn)的左子樹和右子樹的標(biāo)記/k=1表示左子樹，k=2表示右子樹inti=0;/用i掃描字符串treeInitStack(S);/建立鏈棧，棧元素為二叉樹結(jié)點(diǎn)的指針T=NULL;/樹初始化為空while(treei)/每循環(huán)一次處理一個(gè)字符，直到掃描到字符串結(jié)束符為止switch(treei)case:/對(duì)空格不作任何處理break;case(:Push(S,p);k=1;break;case):if(StackEmpty(S)print(“存儲(chǔ)二叉樹廣義表的字符串有錯(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ǔ)指向二叉樹結(jié)點(diǎn)的指針，那么，我們能否不通過定義棧直接按照上述算法中的思想完成樹的建立呢？在棧的遍歷中，我們看到遞歸思想的應(yīng)用，下面給出的改寫

45、算法，也是通過遞歸的方式完成上述操作，本算法具體思想由讀者去進(jìn)一步思考。StatusCreatBiTree2(BiTreePtr&T)staticchartree100;staticintx=0;if(x=0)scanf(%s,tree);switch(treex)case:break;/讀入空格后繼續(xù)讀取case(:x+;CreatBiTree2(T-left);/開始遞歸處理該結(jié)點(diǎn)的左子樹if(treex=,)x+;CreatBiTree2(T-right);/對(duì)于逗號(hào)，退出到該層遞歸后處理結(jié)點(diǎn)右子樹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)右子樹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二叉鏈表的遞歸生成算法求二叉樹的深度該算法采用遞歸的思想：若一棵二叉樹為空，則它的深度為0，否則它的深度等于左子樹和右子樹中的最大深度加1

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

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

49、eePtr&T)/刪除T指向的結(jié)點(diǎn)及其子樹if(T!=NULL)DelBiTreeNode(T-left);/刪除左子樹DelBiTreeNode(T-right);/刪除右子樹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刪除二叉樹中指定結(jié)點(diǎn)的算法清空二叉樹該算法與刪除指定結(jié)點(diǎn)的算法類似，即為刪除根結(jié)點(diǎn)。算法描述如下：StatusClearBiTree(BiTreePtr&T)if(T!

50、=NULL)ClearBiTree(T-left);/刪除左子樹ClearBiTree(T-right);/刪除左子樹free(T);/釋放根結(jié)點(diǎn)T=NULL;/根指針置空算法4-11清空二叉樹的算法第三節(jié)線索二叉樹遍歷二叉樹實(shí)現(xiàn)了樹型非線性結(jié)構(gòu)的線性化，形成了二叉樹結(jié)點(diǎn)的線性序列。為了便于查找某個(gè)結(jié)點(diǎn)在線性序列中的前驅(qū)和后繼信息，需要將二叉樹線索化。1、線索鏈表的數(shù)據(jù)類型1、線索鏈表的數(shù)據(jù)類型作為二叉樹基本的操作，遍歷二叉樹是以一定規(guī)則將二叉樹中的結(jié)點(diǎn)排成一個(gè)線性序列，這可看成是對(duì)樹這種非線性結(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)過程中才能得到。為了能方便獲得和利用某種遍歷過程中的前驅(qū)與后繼結(jié)點(diǎn)的信息，可以在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針分別保存它們，但我們注意到在二叉鏈表中有大量的空指針（n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域），我們可以充分利用這些空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼的信息。具體來說，每個(gè)結(jié)點(diǎn)有左（右）子結(jié)點(diǎn)時(shí)，其左（右）指針指向該子結(jié)點(diǎn)，或無左（右）子結(jié)點(diǎn)，則其左（右）指針指向其前驅(qū)（后繼）結(jié)點(diǎn)。當(dāng)然為了區(qū)分這些指針是指向其子結(jié)點(diǎn)還是指向其前驅(qū)或后繼結(jié)點(diǎn)，需要在結(jié)點(diǎn)的數(shù)

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

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

54、reading(T-left);/左子樹線索化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);/右子樹線索化returnOK;/InOrderThreading算法4-13二叉樹的中序線索化算法3、中序線索二叉樹的遍歷算法3、中序線索二叉樹的遍歷算法在線索二叉樹上進(jìn)行遍歷，只需要從序列的第一個(gè)結(jié)點(diǎn)開始訪問，然后通過依次尋找結(jié)點(diǎn)的后繼進(jìn)行

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

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

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

58、樹的規(guī)則為：（1）一般樹的根對(duì)應(yīng)二叉樹的根；（2）對(duì)樹中任意結(jié)點(diǎn)，轉(zhuǎn)化為二叉樹的結(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)，并依此類推。例如，設(shè)它的孩子結(jié)點(diǎn)依次為Ts1,Ts2,，兄弟結(jié)點(diǎn)依次為TB1,TB2,，則對(duì)應(yīng)二叉樹時(shí)，該結(jié)點(diǎn)的左孩子為Ts1，右孩子為TB1，Ts1的右孩子結(jié)點(diǎn)為Ts2，TB1的右孩子結(jié)點(diǎn)為TB2。這樣樹中任一結(jié)點(diǎn)的子結(jié)點(diǎn)對(duì)應(yīng)二叉樹中結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)及沿著該子結(jié)點(diǎn)的右分支路徑至末端的各結(jié)點(diǎn)，顯然這樣轉(zhuǎn)化的二叉樹根結(jié)點(diǎn)無右子樹，這是根結(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)的必然結(jié)果。圖4.16給出了一個(gè)具體的樹轉(zhuǎn)化成二叉

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

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