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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、無左孩子或右孩子結點。整個數(shù)組下標為零的元素被看成是空閑鏈表的頭結點，該結點的left指向樹的根結點（一般設定樹的根結點存放在下標為1的數(shù)組元素中，即根指針為1；當然，樹為空時可設置根指針為0），該結點的right指向空閑鏈表的頭結點；在空閑鏈表中，結點的right指針指向下一個空閑結點。上述方式下存儲結構的數(shù)據(jù)類型描述如下：typedefstructSBiTreeNodeElemTypedata;intleft,right;SBiTreeNode;下面我們用一個例子來具體描述其存儲結構，如圖4.7所示。該存儲結構的優(yōu)點是：建立好后可以把整個數(shù)組寫入到文件中保存起來，當需要時再從文件整體讀入到

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

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

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

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

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

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

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

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

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

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

46、理新結點break;case):break;/對于右括號不作任何處理，退出一層遞歸case,:break;/對于逗號，退出一層遞歸后處理結點右子樹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、。設depthL為左子樹的深度，depthR為右子樹的深度，則二叉樹的深度為：max(depthL,depthR)+1其中max函數(shù)表示取參數(shù)中的較大者。該算法具體描述如下：IntBiTreeDepth(BiTreePtrT)if(T=NULL)return0;/對于空樹，返回0并結束遞歸elseintdepthL=BiTreeDepth(T-left);/計算左子樹的深度intdepthR=BiTreeDepth(T-right);/計算右子樹的深度return(depthLdepthR)?depthL+1:depthR+1;/返回樹的深度算法4-8二叉樹的深度求解算法刪除二叉樹中指定結點要

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

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

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

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

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

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

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

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

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

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

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

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

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