第6章 樹和二叉樹課件

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

樹的基本概念1樹的定義

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

6.1.1

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

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

基本操作P:書P119頁第6章樹和二叉樹樹的結點：包含一個數據元素及若干指向其子樹的分支。ABCDEFGHIJKLM(b)一般的樹2

樹的基本術語第6章樹和二叉樹結點的度：結點擁有的子樹稱為結點的度。ABCDEFGHIJKLM(b)一般的樹結點A的度為3。結點B的度為2。2

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

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

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

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

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

樹的基本術語第6章樹和二叉樹祖先：從根到該結點所經分支上的所有結點。ABCDEFGHIJKLM(b)一般的樹結點K和L的祖先為：A、B和E。結點H、I和J的祖先為：A和D。2

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

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

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

樹的表示方法的多樣化說明了樹結構的重要性。第6章樹和二叉樹圖6-2

樹的表示形式(a)

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

二叉樹6.2.1二叉樹的定義1

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

二叉樹在樹結構中起著非常重要的作用。因為二叉樹結構簡單，存儲效率高，樹的操作算法相對簡單，且任何樹都很容易轉化成二叉樹結構。上節(jié)中引入的有關樹的術語也都適用于二叉樹。2

二叉樹的基本形態(tài)二叉樹有5種基本形態(tài)，如圖6-3所示。AAAA(a)(b)(c)(d)(e)(a)空二叉樹(b)單結點二叉樹(c)右子樹為空(d)左子樹為空(e)左、右子樹都不空圖6-3

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

在二叉樹的第i層上至多有2i-1個結點（i>=1）。利用數學歸納法證明：i=1時，只有一個根結點，顯然有2i-1=20=1。

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

設n1為二叉樹T中度為1的結點數。則二叉樹T的所有結點數為n=n0+n1+n2

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

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

可以對滿二叉樹進行連續(xù)編號，約定編號從根結點起，自上而下，自左至右。完全二叉樹

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

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

二叉樹的存儲結構1

順序存儲結構二叉樹的順序存儲結構的類型定義：#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;

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

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

(c)完全二叉樹的順序存儲形式圖6-6二叉樹及其順序存儲形式對于完全二叉樹上編號為i的結點元素存儲在一維數組的下標值為i-1的分量中，如圖6-6(c)所示。對于一般的二叉樹，又如何存儲呢？第6章樹和二叉樹例題1：現有如圖A所示的一般二叉樹的存儲結構，請畫出對應的二叉樹的邏輯結構對應的圖。圖A紅黃蘭大中小正負紅黃蘭大中小正負紅黃蘭大正小中負結論：對應的邏輯結構圖不唯一。01234567紅黃蘭大中小正負第6章樹和二叉樹例題2：現有如圖B所示的一般二叉樹的存儲結構，請畫出對應的二叉樹的邏輯結構對應的圖。圖B0123456789101112紅黃蘭大0中小正0000負紅黃蘭大0中小正0000負去掉實際上不存在的0結點所得圖結構為紅黃蘭大中小正負結論：所得邏輯結構對應的圖形具有唯一性。因為采用了完全二叉樹存儲的思想。第6章樹和二叉樹(b)非完全二叉樹abcdefgh???012345678910abcde?h?

?

fg(d)非完全二叉樹的順序存儲形式圖6-6二叉樹及其順序存儲形式因此，對于一般的二叉樹，將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組中，如圖6-6(d)所示。第6章樹和二叉樹評價：在最壞情況下，一個深度為K且只有K個結點的單支樹（樹中不存在度為2的結點）即需要長度為2k-1的一維數組。例如（最壞情況）：有如圖所示的5層單支二叉樹。00000000000000000000000000EDCBA欲采用順序存儲結構，需將其與5層完全二叉樹對應起來。此時的結點數為25-1=32-1=31。結論：雖然這棵二叉樹總共只有5個結點，但需長度為31的一維數組存放。為了存儲一般二叉樹，現介紹二叉樹的另一種存儲結構——鏈式存儲結構。最壞的情況下，一個深度為k且只有k個結點的單支樹需要長度為2k-1的一維數組。第6章樹和二叉樹2鏈式存儲結構（二叉鏈表）

設計不同的結點結構可構成不同的鏈式存儲結構。(1)結點的類型及其定義①二叉鏈表結點。有三個域：一個數據域，兩個分別指向左右子結點的指針域，如圖6-7(a)所示。typedefstruct{//結點結構

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

}BiTNode,*BiTree;LchilddataRchild(a)二叉鏈表結點圖6-7鏈表結點結構形式第6章樹和二叉樹②三叉鏈表結點。除二叉鏈表的三個域外，再增加一個指針域，用來指向結點的父結點，如圖6-7(b)所示。typedefstruct{//結點結構

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

}TriTNode,*TriTree;LchilddataparentRchild(b)三叉鏈表結點圖6-7鏈表結點結構形式第6章樹和二叉樹(2)二叉樹的鏈式存儲形式例如有一棵一般的二叉樹，如圖6-8(a)所示。以二叉鏈表和三叉鏈表方式存儲的結構圖分別如圖6-8(b)、6-8(c)所示。圖6-8二叉樹及其鏈式存儲結構(a)二叉樹afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T第6章樹和二叉樹6.3

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

遍歷二叉樹1

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

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

}BiTNode,*BiTree;StatusPreOrdefTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。//先序遍歷二叉樹T的遞歸算法，對每個數據元素調函數Visit。//最簡單的Visit函數是：

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

printf(e);//實際應用時，加上格式串

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

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

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

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

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

}}

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

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

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

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

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

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

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

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

0A0

0B1

0C0?

1D1

0E1

0F0

1G1

1H1

1F1?(e)中序線索樹的鏈表結構圖6-11線索二叉樹及其存儲結構說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅或直接后繼。在線索樹上進行遍歷，只要先找到序列中的第一個結點，然后就可以依次找結點的直接后繼結點直到后繼為空為止。第6章樹和二叉樹如何在線索樹中找結點的直接后繼?以圖6-11(c)所示的中序線索樹為例：◆樹中所有葉子結點的右鏈都是線索。右鏈直接指示了結點的直接后繼，如結點G的直接后繼是結點E?！魳渲幸徊糠址侨~子結點的右鏈都是指針，無法得到后繼信息。根據中序遍歷的規(guī)律，這些結點的直接后繼是遍歷其右子樹時訪問的第一個結點，即右子樹中最左下的(葉子)結點。如結點C的直接后繼：沿右指針找到右子樹的根結點F，然后沿左鏈往下直到Ltag=1的結點即為C的直接后繼結點H。AFHIEGBDC(a)二叉樹

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

樹與森林

本節(jié)將討論樹的存儲結構、樹及森林與二叉樹之間的相互轉換、樹的遍歷等。第6章樹和二叉樹6.4.1樹的存儲結構樹的存儲結構根據應用的不同而不同。

在大量的應用中，人們曾使用多種形式的存儲結構來表示樹。這里，我們介紹三種常用的鏈表結構。1

雙親表示法(順序存儲結構)

用一組連續(xù)的存儲空間來存儲樹的結點，同時在每個結點中附加一個指示器(整數域)

，用以指示雙親結點的位置(下標值)。數組元素及數組的類型定義如下：第6章樹和二叉樹//-----------------樹的雙親表存儲結構----#defineMAX_TREE_SIZE100typedefstructPTNode{//結點結構

TElemTypedata;intparent;}PTNode;typedefstruct{//樹結構

PTNodenodes[MAX_TREE_SIZE]；

intr,n;//根的位置和結點數}PTree;第6章樹和二叉樹圖6-13所示是一棵樹及其雙親表示的存儲結構。這種存儲結構利用了任一結點的父結點唯一的性質?？梢苑奖愕刂苯诱业饺我唤Y點的父結點，但求結點的子結點時需要掃描整個數組。FGHKRABCDE圖6-13樹的雙親存儲結構R-10A01B02C03D14E15F36G67H68K69第6章樹和二叉樹2孩子鏈表表示法

樹中每個結點有多個指針域，每個指針指向其一棵子樹的根結點。有兩種結點結構。⑴定長結點結構

指針域的數目就是樹的度。其特點是：鏈表結構簡單，但指針域的浪費明顯。結點結構如圖6-14(a)所示。由于樹可能有很多結點的度會小于d，所以鏈表中有很多空鏈域，空間較浪費。⑵不定長結點結構

樹中每個結點的指針域數量不同，是該結點的度，如圖6-14(b)所示。沒有多余的指針域，但操作不便。第6章樹和二叉樹圖6-14孩子表示法的結點結構datachild1child2

?childn(a)定長結點結構(b)不定長結點結構datadegreechild1child2

?childk⑶復合鏈表結構

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

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

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

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

森林與二叉樹的轉換由于二叉樹和樹都可用二叉鏈表作為存儲結構，對比各自的結點結構可以看出，以二叉鏈表作為媒介可以導出樹和二叉樹之間的一個對應關系。也就是說，給定一棵樹，可以找到唯一的一棵二叉樹與之對應?！?/p>

從物理結構來看，樹和二叉樹的二叉鏈表是相同的，只是對指針的邏輯解釋不同而已。

◆

從樹的二叉鏈表表示的定義可知，任何一棵和樹對應的二叉樹，其右子樹一定為空。第6章樹和二叉樹若把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則同樣可導出森林和二叉樹的對應關系。森林轉換成二叉樹第6章樹和二叉樹轉換步驟：

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

ABCDEFGIJHK⑵后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結點。如圖6-23的樹，后序遍歷的次序是：CDBFIJGHEKAABDCKGJIFHE圖6-23樹第6章樹和二叉樹說明：◆樹的先序遍歷實質上與將樹轉換成二叉樹后對二叉樹的先序遍歷相同?！魳涞暮笮虮闅v實質上與將樹轉換成二叉樹后對二叉樹的中序遍歷相同。ABDCKGJIFHE圖6-23樹ABDCKGJIFHE圖6-24圖6-23對應的二叉樹先序遍歷的次序是：ABCDEFGIJHK后序遍歷的次序是：CDBFIJGHEKA第6章樹和二叉樹2森林的遍歷設F={T1,T2,?,Tn}是森林，對F的遍歷有二種方法。⑴先序遍歷：按先序遍歷樹的方式依次遍歷F中的每棵樹。⑵中序遍歷：按后序遍歷樹的方式依次遍歷F中的每棵樹。如書上P138頁圖6.17的森林。第6章樹和二叉樹6.6

赫夫曼樹及其應用赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權路徑長度最短的樹，有著廣泛的應用。6.6.1最優(yōu)二叉樹(Huffman樹)1

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

；樹的路徑長度：31+52+23=19

ABDCKGJIFHE圖6-23樹第6章樹和二叉樹④

結點的帶權路徑長度：從該結點到樹的根結點之間的路徑長度與結點的權(值)的乘積。權(值)：各種開銷、代價、頻度等的抽象稱呼。⑤

樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記做：

WPL=w1

l1+w2

l2+?+wn

ln=∑wi

li(i=1,2,?,n)其中：n為葉子結點的個數；wi為第i個結點的權值；

li為第i個結點的路徑長度。⑥

Huffman樹：具有n個葉子結點(每個結點的權值為wi)的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為Huffman樹(或稱最優(yōu)樹)。第6章樹和二叉樹在許多判定問題時，利用Huffman樹可以得到最佳判斷算法。如圖6-24是權值分別為2、3、6、7，具有4個葉子結點的二叉樹，它們的帶權路徑長度分別為：(a)WPL=2

2+3

2+6

2+7

2=36；(b)WPL=2

1+3

2+6

3+7

3=47；(c)WPL=7

1+6

2+2

3+3

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

圖6-25是權值集合W={8,3,4,6,5,5}構造Huffman樹的過程。所構造的Huffman樹的WPL是：

WPL=6

2+3

3+4

3+8

2+5

3+5

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

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

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