數(shù)據(jù)結(jié)構(gòu) 課件 第7章 樹

第7章樹總體要求：熟悉樹的的定義和二叉樹的定義熟悉二叉樹的抽象數(shù)據(jù)類型描述中各種操作的含義掌握樹的存儲結(jié)構(gòu)熟練掌握二叉樹的各種存儲接結(jié)構(gòu)熟練掌握二叉樹各種存儲接結(jié)構(gòu)下的建立、遍歷算法熟練掌握線索二叉樹的定義和線索化、遍歷算法熟練掌握哈夫曼樹的定義和建立算法及用途核心技能點：具有二叉樹應(yīng)用于實際問題的能力具有熟練掌握二叉樹各種存儲結(jié)構(gòu)下的建立、遍歷算法實現(xiàn)的能力具有熟練掌握線索二叉樹的線索化、遍歷算法的能力具有熟練掌握哈夫曼樹應(yīng)用于實際問題的能力1第7章樹擴展技能點：C語言環(huán)境下二叉樹各種算法的實現(xiàn)相關(guān)知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言指針的知識C語言函數(shù)的知識2第7章樹學習重點：熟悉樹的的定義和二叉樹的定義熟練掌握二叉樹的各種存儲接結(jié)構(gòu)熟練掌握各種存儲接結(jié)構(gòu)下的建立、遍歷算法熟練掌握線索二叉樹的定義和線索化、遍歷算法熟練掌握哈夫曼樹的定義和建立算法及用途3第7章樹

樹的實例和基本概念7.1.1樹的實例7.1.2樹的基本概念7.1.3樹的常用術(shù)語7.1.4樹的表示方法7.2二叉樹7.2.1二叉樹的定義7.2.2二叉樹的重要性質(zhì)7.2.3二叉樹的存儲結(jié)構(gòu)7.2.4二叉樹二叉鏈表生成算法4第7章樹7.3二叉樹的遍歷7.3.1二叉樹遍歷的定義7.3.2遍歷的遞歸方法7.3.3二叉樹遍歷的非遞歸實現(xiàn)7.4二叉樹其它運算的實現(xiàn)7.5線索二叉樹7.5.1線索二叉樹的基本概念7.5.2線索二叉樹的邏輯表示圖7.5.3中序次序線索化算法7.5.4在中序線索樹上檢索某結(jié)點的前驅(qū)或后繼7.5.5在中序線索樹上遍歷二叉樹5第7章樹7.6樹與森林7.6.1樹的存儲結(jié)構(gòu)7.6.2樹、森林和二叉樹的轉(zhuǎn)換7.6.3一般樹或森林的遍歷7.7哈夫曼樹及其應(yīng)用7.7.1哈夫曼樹的基本概念7.7.2哈夫曼樹的構(gòu)造及其算法7.7.3哈夫曼樹的應(yīng)用7.8二叉樹的ADT定義7.9上機實驗本章小結(jié)習題6第7章樹7.1樹的實例和基本概念

前幾章主要討論了線性表以及它的一些實例，這些數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間是前后次序關(guān)系。本章將介紹一種重要的非線性結(jié)構(gòu)，即樹型結(jié)構(gòu)，直觀看來它是以分支關(guān)系定義的層次結(jié)構(gòu)，其數(shù)據(jù)元素之間是上下層次關(guān)系。7第7章樹7.1.1樹的實例下面我們舉兩個樹型結(jié)構(gòu)最常見的實例。例1：如圖7.1學院的行政機構(gòu)，可以把一所高校名稱看成樹根，把下設(shè)的若干個系名看成它的樹枝中間結(jié)點，把每個系分出的若干專業(yè)方向看成樹葉，這樣也形成一個樹形結(jié)構(gòu)。8圖7.1學院的行政機構(gòu)第7章樹

例2：如圖7.2是WINDOWS2000系統(tǒng)的注冊表，第一層是“我的電腦”，第二層分別是HKEY_CLASSES_ROOT、HKEY_CURRENT_USER、HKEY_LOCAL_MACHINE、HKEY_USERS和HKEY_CURRENT_CONFIG。第三層是“HKEY_LOCAL_MACHINE”下的HARDWARE、SAM、SECURITY、SOFTWARE及SYSTEM。從以上兩個實例可以看出，樹型結(jié)構(gòu)是一種層次結(jié)構(gòu)，就像一棵倒掛的樹。9圖7.2WINDOWS2000系統(tǒng)的注冊表第7章樹7.1.2樹的基本概念樹（Ttree）是由n(n≥0)個結(jié)點構(gòu)成的有限集合T，n=0的樹稱為空樹；當n≠0時，樹中的結(jié)點應(yīng)該滿足以下兩個條件：⑴有且僅有一個特定的結(jié)點稱之為根(root)；⑵)其余結(jié)點分成m(m≥0)個互不相交的有限集合T1，T2，…Tm，其中每一個集合又都是一棵樹，稱T1，T2，…Tm為根結(jié)點的子樹(Subtree)。10第7章樹

這是一個遞歸定義，它反映了樹的固有特性，因為一棵樹是由根和它的子樹構(gòu)成，而子樹又由子樹的根和更小的子樹構(gòu)成。圖7.3所表示的樹T中，A是根結(jié)點，其余結(jié)點分成三個互不相交的子集：T1={B，E，F(xiàn)},T2={C}，T3={D，G，H，I，J，K}，這三個集合分別構(gòu)成了A的三棵子樹；在T3構(gòu)成的子樹中，D是根結(jié)點，D又具有三棵子樹，這三棵子樹的根結(jié)點分別是G，H和I；對于結(jié)點G和I，它們的子樹均為空。圖7.3中樹的表示類似于自然界中一棵倒長的樹，“樹型結(jié)構(gòu)”由此得名。11圖7.3一棵樹第7章樹7.1.3樹的常用術(shù)語1.結(jié)點的度和樹的度樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹數(shù)稱為結(jié)點的度(Degree)。而樹的度是指樹中結(jié)點的度的最大值。如圖7

3所示，B結(jié)點有2個子樹，則它的度為2。在樹T中，A和D結(jié)點的度最大，值為3，也就是說，樹T的度為3。2.分支結(jié)點和葉子結(jié)點稱度不為0的結(jié)點為分支結(jié)點，也叫非終端結(jié)點。稱度為0的結(jié)點為葉子(Leaf)或終端結(jié)點。如圖7.3中，分支結(jié)點分別為A、B、D、H，而葉子結(jié)點分別為C、E、F、G、I、J、K。12第7章樹3.孩子、雙親、兄弟、子孫、祖先結(jié)點的子樹的根稱為該結(jié)點的孩子(Child)，相應(yīng)地，該結(jié)點稱為孩子的雙親(Parent)。同一個雙親的孩子之間互稱兄弟(Sibling)。如圖7.3中，B、C、D分別是根結(jié)點A的子樹的根，三個都是A的孩子，相應(yīng)地，A是它們的雙親，其中，B、C、D三者是兄弟。一棵樹上除根結(jié)點以外的其它結(jié)點稱為根結(jié)點的子孫。對于樹中某結(jié)點，從根結(jié)點開始到該結(jié)點的雙親是該結(jié)點的祖先。13第7章樹4.結(jié)點的層次和樹的高度結(jié)點的層次(Level)從根結(jié)點開始定義，根為第一層，根結(jié)點的孩子為第二層，依此類推，其余結(jié)點的層次值為雙親結(jié)點層次值加1。樹中結(jié)點的最大層次值稱為樹的高度或深度(Depth)。如圖7.3所示的樹T高度為4。14第7章樹5.無序樹、有序樹、森林若樹中結(jié)點的各子樹看成從左至右是有次序的(即不能互換)，則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子。森林(Forest)是m(m≥0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。15第7章樹7.1.4樹的表示方法樹的表示形式有多種，常見的三種方法是：1.倒懸樹法樹的表示類似于自然界中一棵倒長的樹，樹的每個結(jié)點都用一個圓圈表示，圓圈內(nèi)的符號代表該結(jié)中的數(shù)據(jù)，結(jié)點之間的關(guān)系通過連線表示。連線上方的結(jié)點為連線下方的結(jié)點的父結(jié)點，而連線下方的結(jié)點則為連線上方結(jié)點的子女結(jié)點。這種表示方法形象、直觀，大多數(shù)書中都采用這種方法，如圖7.3所示。16第7章樹2.嵌套集合表示法樹的嵌套集合圖表示法，其中每一個圓形對應(yīng)著一棵樹，圓內(nèi)包含根結(jié)點和子樹，如圖7.4所示。3.凹入表示法樹的凹入表示法中的每個條形對應(yīng)著一個樹根，子樹的樹根對應(yīng)的條形較短，并在其直接前驅(qū)對應(yīng)的條形之下，如圖7.5所示。17第7章樹18圖7.4樹的嵌套集合圖表示圖7.5樹的凹入表示法第7章樹7.2二叉樹7.2.1二叉樹的定義二叉樹（BinaryTree）是n（n≥0）個結(jié)點的有限集合。它或為空樹（n=0），或為非空樹；對于非空樹有：⑴有一個特定的稱之為根的結(jié)點；⑵根結(jié)點以外的其余結(jié)點分別由兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。19第7章樹

這個遞歸定義表明二叉樹或為空，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的互不相交的二叉樹組成。由于左、右子樹也是二叉樹，則由二叉樹的定義，它們也可以為空。由此，二叉樹可以有五種基本形態(tài)，如圖7.6所示。20第7章樹21圖7.6二叉樹的五種基本形態(tài)(a)空二叉樹(b)只有一個根結(jié)點(c)有根結(jié)點和左子樹(d)有根結(jié)點和右子樹(e)有根結(jié)點和左，右子樹第7章樹

從以上分析得知二叉樹與普通樹比較，有以下特點：⑴二叉樹可以為空樹。⑵二叉樹的度不大于2(即每個結(jié)點至多只有二棵子樹)。⑶二叉樹是有序樹，其左子樹和右子樹是嚴格區(qū)分且不能隨意顛倒的。如圖7.6(c)和圖7.6(d)就是二棵不同的二叉樹。22第7章樹7.2.2二叉樹的重要性質(zhì)性質(zhì)1

二叉樹第i（i≥1）層上至多有2i-1個結(jié)點。根據(jù)二叉樹和結(jié)點層次的定義可知，根結(jié)點在第一層上，這層結(jié)點數(shù)至多為1個，即20個；顯然第二層上至多有2個結(jié)點，即21個；…假設(shè)第i-1層的結(jié)點至多有2i-2個，且每個結(jié)點最多有兩個孩子，那么第i層上結(jié)點至多有2×2i-2=2i-1個。性質(zhì)2

深度為k（k≥1）的二叉樹至多有2k-1個結(jié)點。由性質(zhì)1可知各層結(jié)點最多數(shù)目之和為20+21+22+…+2k-1；由二進制換算關(guān)系可知：20+21+22+…+2k-1=2k-1，因此二叉樹中結(jié)點的最大數(shù)目為2k-1。23第7章樹性質(zhì)3

在任意二叉樹中，若葉子結(jié)點（即度為零的結(jié)點）個數(shù)為n0，度為1的結(jié)點個數(shù)為n1，度為2的結(jié)點個數(shù)為n2，那么n0=n2+1。證明：設(shè)n代表二叉樹結(jié)點總數(shù)，那么n=n0+n1+n2(1)由于有n個結(jié)點的二叉樹總分支數(shù)為n-1條，于是得n-1=0×n0+1×n1+2×n2(2)將式(1)代入式(2)得n0=n2+1有兩種特殊形態(tài)的二叉樹，它們是滿二叉樹和完全二叉樹。24第7章樹

滿二叉樹：深度為k且含有2k-1個結(jié)點的二叉樹為滿二叉樹，這種樹的特點是每層上的結(jié)點數(shù)都是最大結(jié)點數(shù)，如圖7.7(a)所示。對滿二叉樹的結(jié)點可以從根結(jié)點開始自上向下，自左至右順序編號，圖7.7(a)中每個結(jié)點斜上角的數(shù)字即是該結(jié)點的編號。完全二叉樹：深度為k，含有n個結(jié)點的二叉樹，當且僅當每個結(jié)點的編號與相應(yīng)滿二叉樹結(jié)點順序號從0到n-1對應(yīng)時，則稱此二叉樹為完全二叉樹，如圖7.7(b)所示。而圖7.7(c)則不是完全二叉樹。25第7章樹26圖7.7滿二叉樹、完全二叉樹和非完全二叉樹（a）滿二叉樹；（b）完全二叉樹；（c）非完全二叉樹第7章樹性質(zhì)4具有n個結(jié)點的完全二叉樹深度為

lbn

+1（其中

x

表示不大于X的最大整數(shù)）。性質(zhì)5若對有n個結(jié)點的完全二叉樹進行順序編號（0≤i≤n-1，那么，對于編號為i(i≥0)的結(jié)點：當i=0時，該結(jié)點為根，它無雙親結(jié)點；當i＞0時，該結(jié)點的雙親結(jié)點編號為

(i-1)/2

；若2i+1≤n-1,則有編號為2i+1的左孩子，否則沒有左孩子；若2i+2≤n-1，則有編號為2i+2的右孩子，否則沒有右孩子。對照圖7.7(a)或圖7.7(b)，讀者可看到由性質(zhì)5所描述的結(jié)點與編號的對應(yīng)關(guān)系27第7章樹7.2.3二叉樹的存儲結(jié)構(gòu)二叉樹常用的存儲結(jié)構(gòu)有兩種，順序存儲結(jié)構(gòu)（向量）和鏈表存儲結(jié)構(gòu)。⑴順序存儲結(jié)構(gòu)（向量）可以作為二叉樹的存儲結(jié)構(gòu)。這種存儲結(jié)構(gòu)適用于完全二叉樹和滿二叉樹。假設(shè)用一維數(shù)組a存放圖7.7(a)的滿二叉樹?？梢园l(fā)現(xiàn)圖7.7(a)中結(jié)點的編號恰好與數(shù)組元素的下標相對應(yīng)，見圖7.8。28第7章樹

根據(jù)二叉樹性質(zhì)5，在a數(shù)組中可以方便地由某結(jié)點a[i]的下標i找到它們的雙親結(jié)點a[(i-1)/2]或左、右孩子結(jié)點a[2i+1]、a[2i+2]。在哈夫曼樹構(gòu)造算法中也用到順序存儲結(jié)構(gòu)。一般二叉樹較少采用順序存儲結(jié)構(gòu)。29圖7.8二叉樹的順序存儲結(jié)構(gòu)第7章樹⑵鏈表存儲結(jié)構(gòu)通常用于二叉樹存儲。常見的有二叉鏈表和三叉鏈表。二叉鏈表的每個結(jié)點都有一個數(shù)據(jù)域和兩個指針域，一個指針指向左孩子，另一個指針指向右孩子。結(jié)點結(jié)構(gòu)如圖7.9(a)所示，可以描述為：

typedefcharDataType;/*結(jié)點屬性值的類型*/typedefstructNode{DataTypedata;/*數(shù)據(jù)域*/structNode*leftChild;/*左子樹指針*/structNode*rightChild;/*右子樹指針*/}BiTreeNode;30第7章樹(a)二叉鏈表中的結(jié)點結(jié)構(gòu)；(b)三叉鏈表中的結(jié)點結(jié)構(gòu)三叉鏈表的結(jié)點比二叉鏈表多了一個指向雙親的指針域。結(jié)點結(jié)構(gòu)如圖7.9(b)所示，可以描述為：typedefstructNode3{DataTypedata;/*數(shù)據(jù)域*/structNode3*leftChild;/*左子樹指針*/structNode3*rightChild;/*右子樹指針*/structNode3*parent;/*雙親的指針*/}BiTreeNode3;31圖7.9二叉樹鏈表存儲結(jié)構(gòu)中的結(jié)點結(jié)構(gòu)第7章樹

對于圖7.10(a)中二叉樹T，它的二叉鏈表如圖7.10（b），三叉鏈表如圖7.10（c）32圖7.10二叉樹的鏈表存儲結(jié)構(gòu)第7章樹7.2.4二叉樹二叉鏈表的一個生成算法算法思路分析：此方法主要利用二叉樹的性質(zhì)5。對任意二叉樹，先按滿二叉樹對其進行編號，如圖7.11（a）所示。由于此樹并非完全二叉樹，所以編號并不連續(xù)。算法中使用一個輔助向量s用于存放指向樹結(jié)點的指針，如s[i]中存放編號為i的結(jié)點的指針，即為該結(jié)點的地址。此例原始數(shù)據(jù)序列如圖7.11（b）所示，把它存入a數(shù)組，a數(shù)組的類型定義如下：33第7章樹typedefstruct{DataTypedata;intnumber;}DataNum;

當結(jié)點編號i=0時，所產(chǎn)生的結(jié)點為根結(jié)點，同時將指向該結(jié)點的指針存入s[0]。當結(jié)點編號i＞0時，產(chǎn)生一個新的結(jié)點之后，也要將指向該結(jié)點的指針存入s[i]。由性質(zhì)5可知：j=(i-1)/2為它的雙親結(jié)點編號。如果i為奇數(shù)，則它是雙親結(jié)點的左孩子，即讓s[j]->leftChild=s[i]；如果i為偶數(shù)，則它是雙親結(jié)點的右孩子，即讓s[j]->rightChild=s[i]。這樣就將a數(shù)組的結(jié)點逐一與其雙親結(jié)點相連，生成二叉樹。34第7章樹35圖7.11二叉樹及數(shù)據(jù)表第7章樹二叉樹生成算法如下:BiTreeNode*creat(DataNuma[],intn){BiTreeNode*t,*q;BiTreeNode*s[20];/*動態(tài)申請2*n+1個BiTreeNode類型的數(shù)組空間*/inti,j,k;for(k=0;k<n;k++){q=(BiTreeNode*)malloc(sizeof(BiTreeNode));/*產(chǎn)生一個結(jié)點*/q->data=a[k].data;q->leftChild=NULL;q->rightChild=NULL;36第7章樹i=a[k].number;s[i]=q;if(i==0)t=q;/*t為局部變量，代表樹根結(jié)點*/else{j=(i-1)/2;/*雙親結(jié)點編號*/if(i%2==1)s[j]->leftChild=q;elses[j]->rightChild=q;}}return(t);}37第7章樹7.3二叉樹的遍歷7.3.1二叉樹遍歷的定義前面已經(jīng)指出，對于二叉樹經(jīng)常采用鏈表做為它的存儲結(jié)構(gòu)，本節(jié)及以后對二叉樹的討論將主要針對鏈表存儲結(jié)構(gòu)來進行。在二叉樹的應(yīng)用中，常常需要在樹中搜索具有某種特征的結(jié)點，或是對樹中全部的結(jié)點逐一進行處理。這就涉及到一個二叉樹遍歷的問題。二叉樹遍歷是指以一定的次序訪問二叉樹中的每個結(jié)點，并且每個結(jié)點僅被訪問一次。所謂訪問結(jié)點是指對結(jié)點進行各種操作的簡稱。例如，查詢結(jié)點數(shù)據(jù)域的內(nèi)容，或輸出它的值，或找出結(jié)點位置，或是執(zhí)行對結(jié)點的其它操作。二叉樹遍歷的過程實質(zhì)是把二叉樹的結(jié)點進行線性排列的過程。對于線性結(jié)構(gòu)來說，遍歷很容易實現(xiàn)，順序掃描結(jié)構(gòu)中的每個數(shù)據(jù)元素即可。但二叉樹是非線性結(jié)構(gòu)，遍歷時是先訪問根結(jié)點還是先訪問子樹，是先訪問左子樹還是先訪問右子樹必須有所規(guī)定，這就是遍歷規(guī)則。采用不同的遍歷規(guī)則會產(chǎn)生不同的遍歷結(jié)果，因此必須人為設(shè)定遍歷規(guī)則。38第7章樹

由于一棵非空二叉樹是由根結(jié)點、左子樹和右子樹三個基本部分組成，遍歷二叉樹只要按照依次遍歷這三部分即可。假定我們以D、L、R分別表示訪問根結(jié)點，遍歷左子樹和遍歷右子樹則可以有六種遍歷形式：DLR、LDR、LRD、DRL、RDL、RLD，若依習慣規(guī)定先左后右，則上述六種形式可歸并為三種形式，即：DLR：前序遍歷LDR：中序遍歷LRD：后序遍歷下面將分別具體介紹這三種形式的遍歷規(guī)則的遞歸和非遞歸實現(xiàn)。39第7章樹7.3.2遍歷的遞歸方法1．前序遍歷前序遍歷可以遞歸的描述如下：如果根不空：⑴訪問根結(jié)點；⑵按前序次序遍歷左子樹；⑶按前序次序遍歷右子樹；否則返回。前序遍歷的遞歸算法如下：voidPreOrder(BiTreeNode*t){if(t!=NULL){visit(t->data);/*visit（）函數(shù)根據(jù)需要來定義。*/40第7章樹PreOrder(t->leftChild);PreOrder(t->rightChild);}}

如圖7.12(a)所示二叉樹的先序遍歷序列為ABC,7.12(b)所示二叉樹的先序遍歷序列為ABCDEF。41圖7.12遍歷序列示例第7章樹2．中序遍歷中序遍歷可以遞歸的描述如下：如果根不空：⑴按中序遍歷左子樹；⑵訪問根結(jié)點；⑶按中序遍歷右子樹；否則返回。中序遍歷遞歸算法如下：voidInOrder(BiTreeNode*t){if(t!=NULL){InOrder(t->leftChild);visit(t->data);/*visit（）函數(shù)根據(jù)需要來定義。*/42第7章樹InOrder(t->rightChild);}}

如圖7.12(a)所示二叉樹的中序遍歷序列為BAC,7.12(b)所示二叉樹的中序遍歷序列為BCAEDF。3.后序遍歷后序遍歷可以遞歸的描述如下：如果根不空：(1)按后序次序遍歷左子樹；(2)按后序次序遍歷右子樹；(3)訪問根結(jié)點；否則返回。43第7章樹后序遍歷遞歸算法如下：voidPostOrder(BiTreeNode*t){if(t!=NULL){PostOrder(t->leftChild);PostOrder(t->rightChild);visit(t->data);/*visit（）函數(shù)根據(jù)需要來定義。*/}}

如圖7.12(a)所示二叉樹的后序遍歷序列為BCA,7.12(b)所示二叉樹的后序遍歷序列為CBEFDA。44第7章樹7.3.3二叉樹遍歷的非遞歸實現(xiàn)二叉樹遍歷的遞歸程序思路清晰，易于理解，但執(zhí)行效率較低。為了提高程序的執(zhí)行效率，我們可以采用非遞歸方式實現(xiàn)二叉樹的遍歷算法。因此，我們首先給出一個順序棧的定義及其部分操作的實現(xiàn)，在此基礎(chǔ)上討論二叉樹遍歷的非遞歸實現(xiàn)。#definecharDataTypetypedefstructNode/*結(jié)點的結(jié)構(gòu)體定義*/{DataTypedata;/*數(shù)據(jù)域*/structNode*leftChild;/*左子樹指針*/structNode*rightChild;/*右子樹指針*/}BiTreeNode;45第7章樹typedefstruct/*棧結(jié)構(gòu)定義*/{BiTreeNode*data[MaxStackSize];inttag[MaxStackSize];/*為棧中每個元素設(shè)置的標記，用于后序遍歷*/inttop;}SeqStack;voidpush(SeqStack*s,BiTreeNode*x);/*進棧*/voidpop(SeqStack*s,BiTreeNode**x)/*出棧*/1.二叉樹前序遍歷的非遞歸實現(xiàn)二叉樹前序遍歷的非遞歸操作可表示為：voidPreOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法先序遍歷二叉樹。處理過程為：46第7章樹當t！=NULL或s.top!=-1：⑴當t！=NULL：訪問t所指結(jié)點，t壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵若s.top!=-1，彈出棧頂元素給t，t移向其右子樹，重復(fù)⑴，否則⑶。⑶當t！=NULL或s.top！=-1重復(fù)⑴。否則，結(jié)束。程序如下：voidPreOrder1(BiTreeNode*t)/*非遞歸實現(xiàn)二叉樹的前序遍歷*/{SeqStacks;s.top=-1;while((t!=NULL)||(s.top!=-1))/*當前處理的子樹不為空或棧不為空則循環(huán)*/{while(t!=NULL){printf("%c",t->data);push(&s,t);t=t->leftChild;}47第7章樹if(s.top>-1){pop(&s,&t);t=t->rightChild;}}}2.二叉樹中序遍歷的非遞歸實現(xiàn)二叉樹中序遍歷的非遞歸操作可表示為：voidInOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法中序遍歷二叉樹。48第7章樹處理過程為：當t！=NULL或s.top!=-1：⑴當t！=NULL：t壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵若s.top!=-1，彈出棧頂元素給t，訪問t所指結(jié)點，t移向其右子樹，重復(fù)⑴，否則⑶。⑶當t！=NULL或s.top！=-1重復(fù)⑴。否則，結(jié)束。程序如下：voidInOrder1(BiTreeNode*t)/*非遞歸實現(xiàn)二叉樹的前序遍歷*/{SeqStacks;s.top=-1;49第7章樹while((t!=NULL)||(s.top!=-1))/*當前處理的子樹不為空或棧不為空則循環(huán)*/{while(t!=NULL){push(&s,t);t=t->leftChild;}if(s.top>-1){pop(&s,&t);printf("%c",t->data);t=t->rightChild;}}}50第7章樹3.二叉樹后序遍歷的非遞歸實現(xiàn)二叉樹后序遍歷的非遞歸操作，比先序和中序要復(fù)雜，要區(qū)分第一次經(jīng)過（s.tag[s.top]==0）和第二次經(jīng)過（s.tag[s.top]==1）,當從棧中彈出并且s.tag[s.top]==0時，要使s.tag[s.top]=1再壓棧，訪問其右子樹。當從棧中彈出并且s.tag[s.top]==1時才可訪問。二叉樹后序遍歷的非遞歸操作可表示為：voidPostOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法后序遍歷二叉樹。51第7章樹處理過程為：當t！=NULL或s.top!=-1：⑴當t！=NULL：t壓棧，tag=0壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵當s.top!=-1而且s.tag[s.top]==1：彈出棧頂元素給t，訪問t所指結(jié)點，，重復(fù)⑵，否則⑶。⑶若s.top！=-1，彈出棧頂元素給t，s.tag[s.top]=1，t移向其右子樹，否則t=NULL。重復(fù)⑴。否則，結(jié)束。程序如下：voidPostOrder1(BiTreeNode*t)/*非遞歸實現(xiàn)二叉樹的后序遍歷*/{SeqStacks;s.top=-1;52第7章樹while((t!=NULL)||(s.top!=-1))/*當前處理的子樹不為空或棧不為空則循環(huán)*/{while(t!=NULL){s.top++;s.data[s.top]=t;s.tag[s.top]=0;;t=t->leftChild;}while((s.top>-1)&&(s.tag[s.top]==1)){t=s.data[s.top];printf("%c",t->data);s.top--;}if(s.top>-1){t=s.data[s.top];s.tag[s.top]=1;t=t->rightChild;}elset=NULL;}}53第7章樹7.4二叉樹其它運算的實現(xiàn)1．二叉樹的查找locate(t,x)

該運算實現(xiàn)返回二叉樹t中值為x的結(jié)點的位置。根據(jù)二叉樹的定義，首先應(yīng)該將x與t的根結(jié)點的值進行比較，若相等，則返回指向根結(jié)點的指針；否則，進入t的左子樹查找，若查找仍未成功，則進入t的右子樹查找；查找過程中如找到值為x的結(jié)點，則返回；否則意味著t中無x結(jié)點。在左子樹和右子樹中的查找過程與在整棵二叉樹中查找的過程完全相同，只是處理的對象范圍不同，因此可以通過遞歸方式加以實現(xiàn)。具體實現(xiàn)過程算法如下。54第7章樹BiTreeNode*locate(BiTreeNode*t,DataTypex)/*在二叉樹t中查找值為x的結(jié)點*/{BiTreeNode*p;if(t==NULL)returnNULL;elseif(t->data==x)returnt;else{p=locate(t->leftChild,x);if(p!=NULL)returnp;elsereturnlocate(t->rightChild,x);}}55第7章樹2．統(tǒng)計二叉樹中結(jié)點的個數(shù)NumOfNode(t)

該運算返回二叉樹t中所含結(jié)點的個數(shù)。顯然，若t為空，則t中所含結(jié)點的個數(shù)為0；否則，t中所含結(jié)點的個數(shù)等于左子樹中所含結(jié)點的個數(shù)加上右子樹中所含結(jié)點的個數(shù)再加1；而求左子樹中所含結(jié)點的個數(shù)和右子樹中所含結(jié)點的個數(shù)的過程與求整棵二叉樹中所含結(jié)點個數(shù)的過程完全相同，只是處理的對象范圍不同，因此可以通過遞歸調(diào)用加以實現(xiàn)。具體實現(xiàn)過程見算法如下。56第7章樹intNumOfNode(BiTreeNode*t)/*統(tǒng)計二叉樹t中的結(jié)點數(shù)*/{if(t==NULL)return0;elsereturn(NumOfNode(t->leftChild)+NumOfNode(t->rightChild)+1);}3.判斷二叉樹是否等價isEqual(t1,t2)

該運算判斷兩棵給定的二叉樹t1和t2是否等價。兩棵二叉樹等價當且僅當其根結(jié)點的值相等且其左、右子樹對應(yīng)等價。若t1與t2等價，則該運算返回值1，否則返回值0。判斷兩棵二叉樹的左子樹是否等價及判斷兩棵二叉樹的右子樹是否等價的過程與判斷兩棵二叉樹是否等價的過程完全相同，只是處理的對象范圍不同而已，因此可以使用遞歸方式加以實現(xiàn)。具體實現(xiàn)過程見算法如下。57第7章樹intisEqual(BiTreeNode*t1,BiTreeNode*t2)/*判斷二叉樹t1和t2是否等價*/{intt;t=0;if(t1==NULL&&t2==NULL)t=1;/*t1和t2均為空，則二者等價*/elseif(t1!=NULL&&t2!=NULL)/*處理t1和t2均不為空的情形*/if(t1->data==t2->data)/*如果根結(jié)點的值相等*/if(isEqual(t1->leftChild,t2->leftChild))/*如果t1和t2的左子樹等價*/t=isEqual(t1->rightChild，t2->rightChild);/*返回值取決于t1和t2的右子樹是否等價的結(jié)果*/return(t);}58第7章樹4.求二叉樹的高(深)度depth(t)

該運算返回一棵給定的二叉樹t的高（深）度。根據(jù)二叉樹的性質(zhì)及其高度的定義可知，如果t為空二叉樹，則其高度為0；否則，其高度應(yīng)為其左子樹的高度和右子樹的高度的最大值再加1；而求其左子樹和右子樹高度的過程與求整棵二叉樹高度的過程完全相同，因此可以通過遞歸調(diào)用加以實現(xiàn)。具體實現(xiàn)過程如下。intdepth(BiTreeNode*t)/*返回二叉樹的高度*/{inth,lh,rh;if(t==NULL)h=0;/*處理空二叉樹的情況*/59第7章樹else{lh=depth(t->leftChild);/*求左子樹的高度*/rh=depth(t->rightChild);/*求右子樹的高度*/if(lh>=rh)h=lh+1;/*求二叉樹t的高度*/elseh=rh+1;}returnh;}60第7章樹7.5線索二叉樹由上節(jié)可知，遍歷二叉樹可按一定的次序訪問輸出結(jié)點內(nèi)容，得到一個線性序列。這實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化的操作，使每個結(jié)點(除第一個和最后一個外)在這個線性序列中有且僅有一個直接前驅(qū)和直接后繼。換句話說，二叉樹的結(jié)點之間隱含著一個線性關(guān)系，不過這個關(guān)系要通過遍歷才能顯示出來。但是當我們以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，要找到結(jié)點的線性前驅(qū)或后繼就不方便了。能否在不增加存儲空間的前提下保留結(jié)點的線性前驅(qū)和后繼的信息呢？為此，我們引入線索二叉樹。61第7章樹7.5.1線索二叉樹的基本概念我們發(fā)現(xiàn)，具有n個結(jié)點的二叉樹中有n-1條邊指向其左、右孩子，這意味著在二叉鏈表中的2n個孩子指針域中只用到了n-1個域，還有另外n+1個指針域是空的。我們可充分利用這些空指針來存放結(jié)點的線性前驅(qū)和后繼信息。試作如下規(guī)定：若結(jié)點有左子樹，則其leftChild域指示其左孩子，否則令leftChild域指示其直接前驅(qū)；若結(jié)點有右子樹，則其rightChild域指示其右孩子，否則令rightChild域指示其直接后繼。為了嚴格區(qū)分結(jié)點的孩子指針域究竟指向孩子結(jié)點還是指向前驅(qū)或后繼結(jié)點，需在原結(jié)點結(jié)構(gòu)中增加兩個標志域。新的結(jié)點結(jié)構(gòu)為：62第7章樹leftChildleftTagdatarightTagrightChild63其中：LeftTag=0表示leftChild指示結(jié)點的左孩子leftTag=1表示leftChild指示結(jié)點的直接前驅(qū)rightTag=0表示rightChild指示結(jié)點的右孩子rightTag=1表示rightChild指示結(jié)點的直接后繼可以描述為：typedefstructBiTreeThNode{chardata;structBiTreeThNode*leftChild,*rightChild;intleftTag,rightTag;/*左、右標志域*/}BiTreeThNode;第7章樹

通常把指向前驅(qū)或后繼的指針稱做線索。對二叉樹以某種次序進行遍歷并且加上線索的過程稱做線索化。經(jīng)過線索化之后生成的二叉鏈表表示稱為線索二叉樹。對一個已建好的二叉樹的二叉鏈表進行線索化時規(guī)定（對p結(jié)點）：(1)p有左孩子時，則令左特征域p->leftTag=0;(2)p無左孩子時，令p->leftTag=1,并且p->leftChild指向p的前驅(qū)結(jié)點;(3)p有右孩子時，令p->rightTag=0;(4)p無右孩子時，令p->rightTag=1,并且讓p->rightChild指向p的后繼結(jié)點。針對圖7.13（a）的二叉樹，它的中序線索樹的鏈表表示如圖7.13（b）所示。線索用帶箭頭的虛線表示。64第7章樹65圖7.13中序次序線索樹（a）二叉樹；（b）中序線索樹第7章樹7.5.2線索二叉樹的邏輯表示圖按照不同的次序進行線索化，可得到不同的線索二叉樹。有先序線索二叉樹、中序線索二叉樹和后續(xù)線索二叉樹。對圖7.14（a）的二叉樹線索化，可得到圖7.14(b)、(c)、(d)三種線索二叉樹的邏輯表示。66第7章樹67圖7.14線索二叉樹的邏輯表示圖（a）二叉樹；(b)先序線索二叉樹；(c)中序根線索二叉樹；(d)后序根線索二叉樹第7章樹

讀者應(yīng)能熟練掌握三種不同的線索二叉樹的邏輯圖畫法。畫圖時應(yīng)注意，線索應(yīng)畫成帶箭頭的虛線，應(yīng)從結(jié)點的左下方和右下方出發(fā)，左右分明，指向準確。7.5.3中序次序線索化算法這里重點介紹中序次序線索化的算法。中序次序線索化是在已建立好的二叉鏈表之上（每個結(jié)點有5個域），按中序遍歷的方法在訪問根結(jié)點時建立線索，程序如下。/*中序線索化遞歸算法*/voidinThread(BiTreeThNode*p){if(p!=NULL){inThread(p->leftChild);printf("%6c\t",p->data);if(p->leftChild!=NULL)p->leftTag=0;else{p->leftTag=1;p->leftChild=pr;}/*建p結(jié)點的左線索，指向前驅(qū)結(jié)點pr*/68第7章樹if(pr!=NULL){if(pr->rightChild!=NULL)pr->rightTag=0;else{pr->rightTag=1;pr->rightChild=p;}/*前驅(qū)結(jié)點pr建右線索，指向結(jié)點p*/}pr=p;/*pr跟上p，以便p向后移動*/inThread(p->rightChild);}}/*inThread*/69第7章樹

此算法中pr是全局變量，在主程序中置初值為空。在inThread函數(shù)中pr始終作為當前結(jié)點p的前驅(qū)結(jié)點的指針。在線索化過程中，邊判斷二叉樹的結(jié)點有無左、右孩子，邊給相應(yīng)標志域置0或1，邊建立線索。在閱讀此算法時，將inThread（p->leftChild和inThread(p->rightChild)之間的一組語句看成一個整體，把這段語句理解為“訪問”，很明顯這里應(yīng)用了典型的中序遍歷算法思路。在遞歸調(diào)用結(jié)束時p為空，這表明pr已是最后一個結(jié)點，應(yīng)該沒有后繼結(jié)點。所以在返回主程序后還要使pr->rch=NULL，至此整個線索化結(jié)束。主函數(shù)如下：70第7章樹BiTreeThNode*pr;typedefstruct{DataTypedata;intnumber;}DataNum;main(){BiTreeThNode*t=NULL;intn;DataNumtest[]={{'a',0},{'b',1},{'c',2},{'d',3},{'e',4},{'f',5},{'g',6}};pr=NULL;n=7;t=creat(test,n);/*建立二叉樹*/inThread(t);/*中序線索化二叉樹*/pr->rightChild=NULL;/*善后處理*/}71第7章樹

初學者在這里往往易犯錯誤，常把預(yù)處理pr=NULL和善后處理pr->rightChild=NULL放在線索化子函數(shù)VoidinThread(BiTreeThNode*p)中，一個放最前邊，另一個放最后邊。這樣每遞歸調(diào)用一次，pr就置一次空，無法記下p的前驅(qū)結(jié)點。而在從深度遞歸返回時，每返回一次就讓pr->rightChild置一次空，這顯然是錯誤的。因此，在描述遞歸算法時，提倡同時寫出主函數(shù)來示意遞歸調(diào)用前的初始化處理和遞歸調(diào)用結(jié)束后的善后處理。72第7章樹7.5.4在中序線索樹上檢索某結(jié)點的前驅(qū)或后繼⑴已知q結(jié)點，找出它的前驅(qū)結(jié)點。根據(jù)線索樹的基本概念，當q->leftTag==1時，q->leftChild就指向q的前驅(qū)。當q->leftTag==0時，表明q有左孩子。由中序遍歷的規(guī)律可知，作為根q的前驅(qū)結(jié)點（或者說以根結(jié)點為后繼的結(jié)點），它應(yīng)是中序遍歷q的左子樹時訪問的最后一個結(jié)點，即左子樹的最右尾結(jié)點。請看圖7.14（c），結(jié)點B是A的左子樹的最右尾結(jié)點，它就是A的前驅(qū)結(jié)點。而B的后繼指針指向了A，A就是B的后繼結(jié)點。若用p記錄q的前驅(qū)，算法如下。73第7章樹/*已知q結(jié)點，找出它的前驅(qū)結(jié)點*/BiTreeThNode*inpre(BiTreeThNode*q){if(q->leftTag==1)p=q->leftChild;else{r=q->leftChild;while(r->rightTag!==1)r=r->rightChild;p=r;}return(p);}74第7章樹⑵已知q結(jié)點，找出它的后繼結(jié)點。當q->rightTag==1時，q->rightChild即指向q的后繼結(jié)點。若q->rightTag==0，表明q有右孩子，那么q的后繼應(yīng)是中序遍歷q的右子樹時訪問的第一個結(jié)點，即右子樹的最左尾結(jié)點。看圖7.14（c），A的后繼為F，C的后繼為H。依照找前驅(qū)結(jié)點的算法請讀者自己思考該算法的寫法，這里就不再細講。7.5.5在中序線索樹上遍歷二叉樹在中序線索樹上遍歷二叉樹，首先從根結(jié)點開始查找二叉樹的最左結(jié)點，對最左結(jié)點進行訪問。然后，利用在中序線索樹上求某結(jié)點后繼的算法，逐一找出每個結(jié)點加以訪問，直到某結(jié)點的右孩子指針域為空為止。75第7章樹7.6樹與森林7.6.1樹的存儲結(jié)構(gòu)存儲結(jié)構(gòu)的選擇不僅要考慮數(shù)據(jù)元素如何存儲，更重要的是要考慮數(shù)據(jù)元素之間的關(guān)系如何體現(xiàn)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同表示方式，常用的樹存儲結(jié)構(gòu)主要有三種：雙親表示法、孩子表示法和孩子兄弟表示法。本小節(jié)主要討論樹的這三種常用的存儲結(jié)構(gòu)。1.雙親表示法在樹中，除根結(jié)點沒有雙親外，其他每個結(jié)點的雙親是惟一確定的。因此，根據(jù)樹的這種性質(zhì)，存儲樹中結(jié)點時，應(yīng)該包含兩個信息：結(jié)點的值data和體現(xiàn)結(jié)點之間相互關(guān)系的屬性，即該結(jié)點的雙親parent。借助于每個結(jié)點的這兩個信息便可惟一地表示任何一棵樹。這種表示方法稱為雙親表示法，為了查找方便，可以將樹中所有結(jié)點存放在一個一維數(shù)組中，具體類型定義如下。76第7章樹#defineMAXSIZE100/*樹中結(jié)點個數(shù)的最大值*/typedefcharDataType;/*結(jié)點值的類型*/typedefstructnode/*結(jié)點的類型*/{DataTypedata;intparent;/*結(jié)點雙親的下標*/}node;typedefstructtree{nodetreeList[MaxSize];/*存放結(jié)點的數(shù)組*/intlength,root;/*樹中實際所含結(jié)點的個數(shù)及根結(jié)點的位置*/}Tree;/*樹的類型*/77第7章樹

其中DataType應(yīng)根據(jù)結(jié)點值的具體類型給出定義，在此假設(shè)為字符型。這里值得一提的是，根結(jié)點在樹中有著與其它結(jié)點不同的地位，樹根的位置是非常關(guān)鍵的，正如單鏈表中抓住了表頭指針，就掌握了整個鏈表一樣，樹中只要知道樹根在哪里，便可以訪問到樹中所有的結(jié)點，因此樹的存儲結(jié)構(gòu)中要特別考慮根結(jié)點的存儲。圖7.15給出了一棵樹及其雙親表示法。78圖7.15樹的雙親表示法第7章樹

其中parent的值為-1表示結(jié)點的雙親不存在。本樹中root域的值為0，表示樹的根結(jié)點存放在數(shù)組的第一個元素中。2.孩子表示法與雙親表示法不同的是，采用孩子表示法表示一棵樹時，樹中每個結(jié)點除了存儲其自身的值之外，還必須指出其所有子女的位置。為此每個結(jié)點通常包含兩個域：一個是元素的值域data，另一個為指針數(shù)組，數(shù)組中的每個元素均為一個指向該結(jié)點子女的指針；一棵m度的樹，其指針數(shù)組的大小即為m。具體數(shù)據(jù)結(jié)構(gòu)的定義如下。#defineM3/*樹的度數(shù)*/typedefcharDataType;/*結(jié)點值的類型*/typedefstructnode/*結(jié)點的類型*/{DataTypedata;structnode*child[M];/*指向子女的指針數(shù)組*/}Tree;Tree*root;79第7章樹

其中root表示指向樹根結(jié)點的指針，整棵樹中的結(jié)點是通過指向子女結(jié)點的指針數(shù)組相聯(lián)系的，稱這種孩子表示法為指針方式的孩子表示法。圖7.16為圖7.15中（a）的指針方式孩子表示法的表示。80圖7.16樹的指針方式的孩子表示法第7章樹

以上孩子表示法有個缺點：由于每個結(jié)點所含子女數(shù)不相同，因此指示結(jié)點子女的數(shù)組大小均由樹的度數(shù)m來決定。這樣如果一個結(jié)點子女個數(shù)少于m，就有空間閑置與浪費。一種改進的辦法是：把每個結(jié)點的子女排列起來形成一個單鏈表，這樣n個結(jié)點就形成n個單鏈表；而n個單鏈表的頭指針又組成一個線性表，為了查找方便，可以使用數(shù)組方式加以存儲，稱這種孩子表示法為鏈表方式的孩子表示法。其具體數(shù)據(jù)結(jié)構(gòu)定義如下。#defineMAXSIZE50typedefcharDataType;typedefstructchildNode/*孩子結(jié)點的類型*/81第7章樹{intchild;structchildNode*next;}childNode,*childPoint;typedefstruct{/*樹中每個結(jié)點的類型*/DataTypedata;childPointfirstChild;/*指向第一個子女結(jié)點的指針*/}node;typedefstruct{/*樹的類型*/nodetreeList[MaxSize];intlength,root；/*樹中實際所含結(jié)點的個數(shù)和根結(jié)點的位置*/}Tree;圖7.17給出了圖7.15中（a）的鏈表方式孩子表示法的表示。82第7章樹83圖7.17樹的鏈表方式的孩子表示法第7章樹7.6.2樹、森林和二叉樹的轉(zhuǎn)換樹和二叉樹雖然為兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們之間有一種自然的一一對應(yīng)關(guān)系。任何一棵樹（或森林）都惟一地對應(yīng)于一棵二叉樹；反之，任何一棵二叉樹也惟一地對應(yīng)于一棵樹（或森林）。以下討論它們之間的轉(zhuǎn)換方法。1.樹與二叉樹之間的轉(zhuǎn)換對于一般樹，樹中孩子的次序并不重要，只要雙親與孩子的關(guān)系正確即可。但在二叉樹中，左、右孩子的次序是嚴格區(qū)分的。所以在討論二叉樹與一般樹之間的轉(zhuǎn)換時，為了不引起混淆，就約定按樹上現(xiàn)有結(jié)點次序進行轉(zhuǎn)換。84第7章樹(1)一般樹轉(zhuǎn)化為二叉樹將一般樹轉(zhuǎn)化為二叉樹的思路，主要根據(jù)樹的孩子－兄弟存儲方式而來，步驟是：①加線：在各兄弟結(jié)點之間用虛線相連?？衫斫鉃槊總€結(jié)點的兄弟指針指向它的一個兄弟。②抹線：對每個結(jié)點僅保留它與其最左一個孩子的連線，抹去該結(jié)點與其它孩子之間的連線?？衫斫鉃槊總€結(jié)點僅有一個孩子指針，讓它指向自己的長子。③旋轉(zhuǎn)：把虛線改為實線，從水平方向向下旋轉(zhuǎn)450，成右斜下方向。原樹中實線成左斜下方向。這樣就形成一棵二叉樹。由于二叉樹中各結(jié)點的右孩子都是原一般樹中該結(jié)點的兄弟，而一般樹的根結(jié)點又沒有兄弟結(jié)點，因此所生成的二叉樹的根結(jié)點沒有右子樹。在所生成的二叉樹中某一結(jié)點的左孩子仍是原來樹中該結(jié)點的長子，并且是它的最左孩子。圖7

18是一個由一般樹轉(zhuǎn)為二叉樹的實例。

85第7章樹86圖7

18

一般樹轉(zhuǎn)換為二叉樹(a)一般樹；(b)加線；(c)抹線；(d)旋轉(zhuǎn)整理第7章樹(2)二叉樹還原為一般樹二叉樹還原為一般樹，此時的二叉樹必須是由某一樹轉(zhuǎn)換而來的沒有右子樹的二叉樹。并非隨便一棵二叉樹都能還原成一般樹。其還原過程也分為三步：①加線：若某結(jié)點i是雙親結(jié)點的左孩子，則將該結(jié)點i的右孩子以及當且僅當連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子，都分別與結(jié)點i的雙親結(jié)點用虛線連接。②抹線：把原二叉樹中所有雙親結(jié)點與其右孩子的連線抹去。這里的右孩子實質(zhì)上是原一般樹中結(jié)點的兄弟，抹去的連線是兄弟間的關(guān)系。③進行整理：把虛線該為實線，把結(jié)點按層次排列。二叉樹還原為一般樹的示例，如圖7

19所示。87第7章樹88圖7

19

二叉樹還原為一般樹（a）二叉樹；(b)還原加線；(c)還原抹線；(d)還原整理第7章樹2．森林與二叉樹的轉(zhuǎn)換森林是樹的有限集合，如圖7

20（a）所示。89圖7

20

森林轉(zhuǎn)換為二叉樹（a）一般樹的森林；（b）二叉樹的森林；（c）第二棵子樹并入第一棵子樹；（d）最終結(jié)果第7章樹（1）森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的步驟為：①將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成有若干二叉樹的森林。②按森林圖形中樹的先后次序，依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點的右子樹，這樣整個森林就生成了一棵二叉樹，實際上第一棵樹的根結(jié)點便是生成后的二叉樹的根結(jié)點。圖7

20是森林轉(zhuǎn)化為二叉樹的示例。（2）二叉樹還原為森林將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森林的步驟是：①抹線：將二叉樹的根結(jié)點與其右孩子的連線以及當且僅當連續(xù)地沿著右鏈不斷地搜索到的所有右孩子的連線全部抹去，這樣就得到包含有若干棵二叉樹的森林。90第7章樹②還原：將每棵二叉樹按二叉樹還原一般樹的方法還原為一般樹，于是得到森林。這部分的圖示，請讀者自己練習畫出。7.6.3一般樹或森林的遍歷一般樹的遍歷主要是先序和后序遍歷，一般不討論中序遍歷。樹的先序遍歷首先訪問樹的根結(jié)點，然后從左至右逐一先序遍歷每一棵子樹。樹的后序遍歷首先后序遍歷樹的最左邊的第一棵子樹，接著從左至右逐一后序遍歷每一棵子樹，最后訪問樹的根結(jié)點。一般樹轉(zhuǎn)換為二叉樹后，此二叉樹沒有右子樹，對此二叉樹的中序遍歷結(jié)果與上述一般樹的后序遍歷結(jié)果相同。91第7章樹7.7哈夫曼樹及其應(yīng)用哈夫曼樹（Huffman），又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。7.7.1哈夫曼樹的基本概念首先我們要學習一些與哈夫曼樹有關(guān)的術(shù)語。兩個結(jié)點之間的路徑：樹中一個結(jié)點到另一個結(jié)點之間的分支序列稱為這對結(jié)點之間的路徑。兩個結(jié)點之間的路徑長度：樹中一個結(jié)點到另一個結(jié)點之間的分支數(shù)目稱為這對結(jié)點之間的路徑長度。樹的路徑長度：從根結(jié)點到每個葉子結(jié)點的路徑長度之和。樹的帶權(quán)路徑長度：設(shè)一棵二叉樹有n個葉子，每個葉子結(jié)點擁有一個權(quán)值w1，w2，…，wn，從根結(jié)點到每個葉子結(jié)點的路徑長度分別為l1，l2，…，ln,那么樹的帶權(quán)路徑長度為每個葉子的路徑長度與該葉子權(quán)值乘積之和，通常記作：92第7章樹WPL=wili

為了直觀起見，在圖7.21中，把帶權(quán)的葉子結(jié)點畫成方形，其它非葉子結(jié)點仍為圓形。請看圖7.21中的三棵二叉樹以及它們的帶權(quán)路徑長度。(a)WPL=2×2+4×2+5×2+8×2=38(b)WPL=4×2+5×3+8×3+2×1=49(c)WPL=8×1+5×2+4×3+2×3=36

請注意，這三棵二叉樹葉子結(jié)點數(shù)相同，它們的權(quán)值也相同，但是它們的WPL帶權(quán)路徑長各不相同。圖7.21（c）WPL最小。它就是哈夫曼樹，最優(yōu)樹。哈夫曼樹：是在具有同一組權(quán)值的葉子結(jié)點的不同二叉樹中，帶權(quán)路徑長度最短的樹。93第7章樹94圖7.21具有不同帶權(quán)路徑長度的二叉樹（a）WPL=38；（b）WPL=49；（c）WPL=36第7章樹7.7.2哈夫曼樹的構(gòu)造及其算法1.構(gòu)造哈夫曼樹的方法對于已知的一組葉子的權(quán)值w1，w2，…，wn：(1)首先把n個葉子結(jié)點看作n棵樹（有一個結(jié)點的二叉樹），把它們看作一個森林。(2)在森林中把權(quán)值最小和次小的兩棵樹合并成一棵樹，該樹根結(jié)點的權(quán)值是兩棵子樹權(quán)值之和。這時森林中還有n-1棵樹。(3)重復(fù)第（2）步直到森林中只有一棵樹為止。此樹就是哈夫曼樹?，F(xiàn)給一組（n=4））具體的權(quán)值{2，4，5，8}，7.22是構(gòu)造哈夫曼樹的具體過程。95第7章樹96圖7.22哈夫曼樹構(gòu)造過程（a）森林中有四棵樹；（b）森林中有三棵樹；（c）森林中有兩棵樹；（d）生成一棵樹第7章樹

此時我們或許會問，n個葉子構(gòu)成的哈夫曼樹其帶權(quán)路徑長度惟一嗎？答案是確實惟一。樹形惟一嗎？答案是不惟一。因為將森林中兩棵權(quán)值最小和次小的子樹合并時，哪棵做左子樹，哪棵做右子樹并不嚴格限制。圖7

22之中的做法是把權(quán)值較小的當作左子樹，權(quán)值較大的當作右子樹。如果反過來也可以，畫出的樹形有所不同，但WPL值相同。2.哈夫曼算法實現(xiàn)討論算法實現(xiàn)需選擇合適的存儲結(jié)構(gòu)，因為哈夫曼樹中沒有度為1的結(jié)點。這里選用順序存儲結(jié)構(gòu)。由二叉樹性質(zhì)可知n0=n2+1，而現(xiàn)在總結(jié)點數(shù)為n0+n2，也即2n0-1，葉子數(shù)n0若用n表示則二叉樹結(jié)點總數(shù)為2n-1。向量的大小就定義為2n-1。假設(shè)n,<10，存儲結(jié)構(gòu)如下：97第7章樹typedefstruct/*哈夫曼樹的結(jié)點結(jié)構(gòu)*/{intweight;/*權(quán)值*/intflag;/*標記*/intparent;/*雙親結(jié)點下標*/intleftChild;/*左孩子下標*/intrightChild;/*右孩子下標*/}HaffNode;HaffNodehaffTree[];

首先需將葉子權(quán)值輸入haffTree向量，leftChild,rightChild,flag域全置零，如果用前邊的一組數(shù)值{2，4，5，8}初始化向量r，見圖7.23（a）。然后執(zhí)行算法，可得出如圖7.23（b）所示的結(jié)果。設(shè)t為指向哈夫曼樹的根結(jié)點（在此是數(shù)組元素）的指針，算法如下。98第7章樹99圖7.23哈夫曼樹向量存儲結(jié)構(gòu)示意(a)初始狀態(tài)；(b)最終狀態(tài)第7章樹voidHaffman(intweight[],intn,HaffNodehaffTree[])/*建立葉結(jié)點個數(shù)為n權(quán)值數(shù)組為weight的哈夫曼樹haffTree*/{inti,j,m1,m2,x1,x2;/*哈夫曼樹haffTree[]初始化。n個葉結(jié)點共有2n-1個結(jié)點*/for(i=0;i<2*n-1;i++){if(i<n)haffTree[i].weight=weight[i];elsehaffTree[i].weight=0;haffTree[i].parent=-1;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}100第7章樹/*構(gòu)造哈夫曼樹haffTree[]的n-1個非葉結(jié)點*/for(i=0;i<n-1;i++){m1=m2=MaxValue;x1=x2=0;for(j=0;j<n+i;j++){if(haffTree[j].weight<m1&&haffTree[j].flag==0){m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;}101第7章樹elseif(haffTree[j].weight<m2&&haffTree[j].flag==0){m2=haffTree[j].weight;x2=j;}}/*將找出的兩棵權(quán)值最小的子樹合并為一棵子樹*/haffTree[x1].parent=n+i;haffTree[x2].parent=n+i;haffTree[x1].flag=1;haffTree[x2].flag=1;haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;haffTree[n+i].leftChild=x1;haffTree[n+i].rightChild=x2;}}102第7章樹

圖7.23中僅給出了所用到的數(shù)組元素，其它略去未畫。在以上算法中主要有一個二重循環(huán)，內(nèi)循環(huán)的平均循環(huán)次數(shù)均為O(n),外循環(huán)大約n次，所以該算法的時間復(fù)雜度為O(n2)。7.7.3哈夫曼樹的應(yīng)用

1.判定樹。在考查課記分時往往把百分制轉(zhuǎn)換成優(yōu)（x≥90）、良（80≤x<90）、中（70≤x<80）、及格（60≤x<70）、不及格（x<60）5個等級。若不考慮學生考試分數(shù)的分布概率，程序判定過程很容易寫成圖7

24（a）可看出這種情況的x值要比較2至3次才能確定等級。而學生中考試不及格的人數(shù)很少，x值比較一次即可定等級。能否使出現(xiàn)次數(shù)多的在70～80分之間的x值比較次數(shù)減少些，而使很少出現(xiàn)的低于60分的x值比較次數(shù)多一些，以便提高程序的運行效率呢？假設(shè)學生成績對于不及格、及格、中等、良好和優(yōu)秀的分布概率分別為5%，15%，40%，30%，10%，以它們?yōu)槿~子的權(quán)值來構(gòu)造哈夫曼樹，如圖7

24（b）所示。此時帶權(quán)路徑長最短，其值為205。它可以使大部分的分數(shù)值經(jīng)過較少的比較次數(shù)得到相應(yīng)的等級。但是，事情往往不是絕對的，此時每個判斷框內(nèi)的條件較為復(fù)雜，比較兩次，反而降低運行效率。所以我們采用折衷作法，調(diào)整后得圖7

24(c)判定樹。它更加切合實際。103第7章樹104圖7

24轉(zhuǎn)換五分制不同判定過程第7章樹2.哈夫曼編碼。在通信及數(shù)據(jù)傳輸中多采用二進制編碼，即由0、1組成的字符串。接收方收到一系列0、1串后，再把它還原成文字，即譯碼。例如：需傳送的電文為“ACDACAB”，其間只用到了四個字符，則只需兩個字符的串便足以分辨。令“A、B、C、D”的編碼分別為00、01、10、11，則電文的二進制代碼串為：00101100100001，總碼長14位。接收方按兩位一組進行分割，便可譯碼。但是，在傳送電文時，總希望總碼長盡可能的短。如果對每個字符設(shè)計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長便可減少。上例電文中A和C出現(xiàn)的次數(shù)較多，我們可以再設(shè)計一種編碼方案，即A、B、C、D的編碼分別為0、01、1、11，此時，電文“ACDACAB”的二進制代碼串為：011101001，總碼長9位，顯然縮短了。105第7章樹

但是，接收方收到該代碼串后無法進行譯碼。比如代碼串的“01”是代表B還是代表AC呢？因此，若要設(shè)計長度不等的編碼，必須是任一個字符的編碼都不是另一個字符的編碼的前綴，這各編碼稱為前綴編碼。電話號碼就是前綴碼，例如110是報警電話的號碼，其他的電話號碼就不能以110開頭了。利用哈夫曼樹不僅能構(gòu)造出前綴碼，而且還能使電文編碼的總長度最短。方法如下：假定電文中共用了n種字符，每種字符在電文中出現(xiàn)的次數(shù)為Wi(i=1…n)。以Wi作為哈夫曼樹葉子結(jié)點的權(quán)值，用我們前面所介紹的哈夫曼算法構(gòu)造出哈夫曼樹，然后將每個結(jié)點的左分支標上“0”，右分支標上“1”，則從根結(jié)點到代表該字符的葉子結(jié)點之間，沿途路徑上的分支號組成的代碼串就是該字符的編碼。106第7章樹