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

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

樹的實(shí)例和基本概念7.1.1樹的實(shí)例7.1.2樹的基本概念7.1.3樹的常用術(shù)語7.1.4樹的表示方法7.2二叉樹7.2.1二叉樹的定義7.2.2二叉樹的重要性質(zhì)7.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)7.2.4二叉樹二叉鏈表生成算法4第7章樹7.3二叉樹的遍歷7.3.1二叉樹遍歷的定義7.3.2遍歷的遞歸方法7.3.3二叉樹遍歷的非遞歸實(shí)現(xiàn)7.4二叉樹其它運(yùn)算的實(shí)現(xiàn)7.5線索二叉樹7.5.1線索二叉樹的基本概念7.5.2線索二叉樹的邏輯表示圖7.5.3中序次序線索化算法7.5.4在中序線索樹上檢索某結(jié)點(diǎn)的前驅(qū)或后繼7.5.5在中序線索樹上遍歷二叉樹5第7章樹7.6樹與森林7.6.1樹的存儲(chǔ)結(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上機(jī)實(shí)驗(yàn)本章小結(jié)習(xí)題6第7章樹7.1樹的實(shí)例和基本概念

前幾章主要討論了線性表以及它的一些實(shí)例，這些數(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樹的實(shí)例下面我們舉兩個(gè)樹型結(jié)構(gòu)最常見的實(shí)例。例1：如圖7.1學(xué)院的行政機(jī)構(gòu)，可以把一所高校名稱看成樹根，把下設(shè)的若干個(gè)系名看成它的樹枝中間結(jié)點(diǎn)，把每個(gè)系分出的若干專業(yè)方向看成樹葉，這樣也形成一個(gè)樹形結(jié)構(gòu)。8圖7.1學(xué)院的行政機(jī)構(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。從以上兩個(gè)實(shí)例可以看出，樹型結(jié)構(gòu)是一種層次結(jié)構(gòu)，就像一棵倒掛的樹。9圖7.2WINDOWS2000系統(tǒng)的注冊表第7章樹7.1.2樹的基本概念樹（Ttree）是由n(n≥0)個(gè)結(jié)點(diǎn)構(gòu)成的有限集合T，n=0的樹稱為空樹；當(dāng)n≠0時(shí)，樹中的結(jié)點(diǎn)應(yīng)該滿足以下兩個(gè)條件：⑴有且僅有一個(gè)特定的結(jié)點(diǎn)稱之為根(root)；⑵)其余結(jié)點(diǎn)分成m(m≥0)個(gè)互不相交的有限集合T1，T2，…Tm，其中每一個(gè)集合又都是一棵樹，稱T1，T2，…Tm為根結(jié)點(diǎn)的子樹(Subtree)。10第7章樹

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

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

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

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

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

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

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

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

lbn

+1（其中

x

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

(i-1)/2

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

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

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

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

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

由于一棵非空二叉樹是由根結(jié)點(diǎn)、左子樹和右子樹三個(gè)基本部分組成，遍歷二叉樹只要按照依次遍歷這三部分即可。假定我們以D、L、R分別表示訪問根結(jié)點(diǎn)，遍歷左子樹和遍歷右子樹則可以有六種遍歷形式：DLR、LDR、LRD、DRL、RDL、RLD，若依習(xí)慣規(guī)定先左后右，則上述六種形式可歸并為三種形式，即：DLR：前序遍歷LDR：中序遍歷LRD：后序遍歷下面將分別具體介紹這三種形式的遍歷規(guī)則的遞歸和非遞歸實(shí)現(xiàn)。39第7章樹7.3.2遍歷的遞歸方法1．前序遍歷前序遍歷可以遞歸的描述如下：如果根不空：⑴訪問根結(jié)點(diǎn)；⑵按前序次序遍歷左子樹；⑶按前序次序遍歷右子樹；否則返回。前序遍歷的遞歸算法如下：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é)點(diǎn)；⑶按中序遍歷右子樹；否則返回。中序遍歷遞歸算法如下：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é)點(diǎn)；否則返回。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二叉樹遍歷的非遞歸實(shí)現(xiàn)二叉樹遍歷的遞歸程序思路清晰，易于理解，但執(zhí)行效率較低。為了提高程序的執(zhí)行效率，我們可以采用非遞歸方式實(shí)現(xiàn)二叉樹的遍歷算法。因此，我們首先給出一個(gè)順序棧的定義及其部分操作的實(shí)現(xiàn)，在此基礎(chǔ)上討論二叉樹遍歷的非遞歸實(shí)現(xiàn)。#definecharDataTypetypedefstructNode/*結(jié)點(diǎn)的結(jié)構(gòu)體定義*/{DataTypedata;/*數(shù)據(jù)域*/structNode*leftChild;/*左子樹指針*/structNode*rightChild;/*右子樹指針*/}BiTreeNode;45第7章樹typedefstruct/*棧結(jié)構(gòu)定義*/{BiTreeNode*data[MaxStackSize];inttag[MaxStackSize];/*為棧中每個(gè)元素設(shè)置的標(biāo)記，用于后序遍歷*/inttop;}SeqStack;voidpush(SeqStack*s,BiTreeNode*x);/*進(jìn)棧*/voidpop(SeqStack*s,BiTreeNode**x)/*出棧*/1.二叉樹前序遍歷的非遞歸實(shí)現(xiàn)二叉樹前序遍歷的非遞歸操作可表示為：voidPreOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法先序遍歷二叉樹。處理過程為：46第7章樹當(dāng)t！=NULL或s.top!=-1：⑴當(dāng)t！=NULL：訪問t所指結(jié)點(diǎn)，t壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵若s.top!=-1，彈出棧頂元素給t，t移向其右子樹，重復(fù)⑴，否則⑶。⑶當(dāng)t！=NULL或s.top！=-1重復(fù)⑴。否則，結(jié)束。程序如下：voidPreOrder1(BiTreeNode*t)/*非遞歸實(shí)現(xiàn)二叉樹的前序遍歷*/{SeqStacks;s.top=-1;while((t!=NULL)||(s.top!=-1))/*當(dāng)前處理的子樹不為空或棧不為空則循環(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.二叉樹中序遍歷的非遞歸實(shí)現(xiàn)二叉樹中序遍歷的非遞歸操作可表示為：voidInOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法中序遍歷二叉樹。48第7章樹處理過程為：當(dāng)t！=NULL或s.top!=-1：⑴當(dāng)t！=NULL：t壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵若s.top!=-1，彈出棧頂元素給t，訪問t所指結(jié)點(diǎn)，t移向其右子樹，重復(fù)⑴，否則⑶。⑶當(dāng)t！=NULL或s.top！=-1重復(fù)⑴。否則，結(jié)束。程序如下：voidInOrder1(BiTreeNode*t)/*非遞歸實(shí)現(xiàn)二叉樹的前序遍歷*/{SeqStacks;s.top=-1;49第7章樹while((t!=NULL)||(s.top!=-1))/*當(dāng)前處理的子樹不為空或棧不為空則循環(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.二叉樹后序遍歷的非遞歸實(shí)現(xiàn)二叉樹后序遍歷的非遞歸操作，比先序和中序要復(fù)雜，要區(qū)分第一次經(jīng)過（s.tag[s.top]==0）和第二次經(jīng)過（s.tag[s.top]==1）,當(dāng)從棧中彈出并且s.tag[s.top]==0時(shí)，要使s.tag[s.top]=1再壓棧，訪問其右子樹。當(dāng)從棧中彈出并且s.tag[s.top]==1時(shí)才可訪問。二叉樹后序遍歷的非遞歸操作可表示為：voidPostOrder1(BiTreeNode*t)；其中，參數(shù)t表示指定的樹根指針，其類型為BiTreeNode。操作的功能為：用非遞歸的方法后序遍歷二叉樹。51第7章樹處理過程為：當(dāng)t！=NULL或s.top!=-1：⑴當(dāng)t！=NULL：t壓棧，tag=0壓棧，t移向其左子樹，重復(fù)⑴。否則執(zhí)行⑵。⑵當(dāng)s.top!=-1而且s.tag[s.top]==1：彈出棧頂元素給t，訪問t所指結(jié)點(diǎn)，，重復(fù)⑵，否則⑶。⑶若s.top！=-1，彈出棧頂元素給t，s.tag[s.top]=1，t移向其右子樹，否則t=NULL。重復(fù)⑴。否則，結(jié)束。程序如下：voidPostOrder1(BiTreeNode*t)/*非遞歸實(shí)現(xiàn)二叉樹的后序遍歷*/{SeqStacks;s.top=-1;52第7章樹while((t!=NULL)||(s.top!=-1))/*當(dāng)前處理的子樹不為空或棧不為空則循環(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二叉樹其它運(yùn)算的實(shí)現(xiàn)1．二叉樹的查找locate(t,x)

該運(yùn)算實(shí)現(xiàn)返回二叉樹t中值為x的結(jié)點(diǎn)的位置。根據(jù)二叉樹的定義，首先應(yīng)該將x與t的根結(jié)點(diǎn)的值進(jìn)行比較，若相等，則返回指向根結(jié)點(diǎn)的指針；否則，進(jìn)入t的左子樹查找，若查找仍未成功，則進(jìn)入t的右子樹查找；查找過程中如找到值為x的結(jié)點(diǎn)，則返回；否則意味著t中無x結(jié)點(diǎn)。在左子樹和右子樹中的查找過程與在整棵二叉樹中查找的過程完全相同，只是處理的對象范圍不同，因此可以通過遞歸方式加以實(shí)現(xiàn)。具體實(shí)現(xiàn)過程算法如下。54第7章樹BiTreeNode*locate(BiTreeNode*t,DataTypex)/*在二叉樹t中查找值為x的結(jié)點(diǎn)*/{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)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)NumOfNode(t)

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

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

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

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

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

此算法中pr是全局變量，在主程序中置初值為空。在inThread函數(shù)中pr始終作為當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)的指針。在線索化過程中，邊判斷二叉樹的結(jié)點(diǎn)有無左、右孩子，邊給相應(yīng)標(biāo)志域置0或1，邊建立線索。在閱讀此算法時(shí)，將inThread（p->leftChild和inThread(p->rightChild)之間的一組語句看成一個(gè)整體，把這段語句理解為“訪問”，很明顯這里應(yīng)用了典型的中序遍歷算法思路。在遞歸調(diào)用結(jié)束時(shí)p為空，這表明pr已是最后一個(gè)結(jié)點(diǎn)，應(yīng)該沒有后繼結(jié)點(diǎn)。所以在返回主程序后還要使pr->rch=NULL，至此整個(gè)線索化結(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章樹

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

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

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

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

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

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

85第7章樹86圖7

18

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

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

為了直觀起見，在圖7.21中，把帶權(quán)的葉子結(jié)點(diǎn)畫成方形，其它非葉子結(jié)點(diǎn)仍為圓形。請看圖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é)點(diǎn)數(shù)相同，它們的權(quán)值也相同，但是它們的WPL帶權(quán)路徑長各不相同。圖7.21（c）WPL最小。它就是哈夫曼樹，最優(yōu)樹。哈夫曼樹：是在具有同一組權(quán)值的葉子結(jié)點(diǎn)的不同二叉樹中，帶權(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個(gè)葉子結(jié)點(diǎn)看作n棵樹（有一個(gè)結(jié)點(diǎn)的二叉樹），把它們看作一個(gè)森林。(2)在森林中把權(quán)值最小和次小的兩棵樹合并成一棵樹，該樹根結(jié)點(diǎn)的權(quán)值是兩棵子樹權(quán)值之和。這時(shí)森林中還有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章樹

此時(shí)我們或許會(huì)問，n個(gè)葉子構(gòu)成的哈夫曼樹其帶權(quán)路徑長度惟一嗎？答案是確實(shí)惟一。樹形惟一嗎？答案是不惟一。因?yàn)閷⑸种袃煽脵?quán)值最小和次小的子樹合并時(shí)，哪棵做左子樹，哪棵做右子樹并不嚴(yán)格限制。圖7

22之中的做法是把權(quán)值較小的當(dāng)作左子樹，權(quán)值較大的當(dāng)作右子樹。如果反過來也可以，畫出的樹形有所不同，但WPL值相同。2.哈夫曼算法實(shí)現(xiàn)討論算法實(shí)現(xiàn)需選擇合適的存儲(chǔ)結(jié)構(gòu)，因?yàn)楣蚵鼧渲袥]有度為1的結(jié)點(diǎn)。這里選用順序存儲(chǔ)結(jié)構(gòu)。由二叉樹性質(zhì)可知n0=n2+1，而現(xiàn)在總結(jié)點(diǎn)數(shù)為n0+n2，也即2n0-1，葉子數(shù)n0若用n表示則二叉樹結(jié)點(diǎn)總數(shù)為2n-1。向量的大小就定義為2n-1。假設(shè)n,<10，存儲(chǔ)結(jié)構(gòu)如下：97第7章樹typedefstruct/*哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)*/{intweight;/*權(quán)值*/intflag;/*標(biāo)記*/intparent;/*雙親結(jié)點(diǎn)下標(biāo)*/intleftChild;/*左孩子下標(biāo)*/intrightChild;/*右孩子下標(biāo)*/}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é)點(diǎn)（在此是數(shù)組元素）的指針，算法如下。98第7章樹99圖7.23哈夫曼樹向量存儲(chǔ)結(jié)構(gòu)示意(a)初始狀態(tài)；(b)最終狀態(tài)第7章樹voidHaffman(intweight[],intn,HaffNodehaffTree[])/*建立葉結(jié)點(diǎn)個(gè)數(shù)為n權(quán)值數(shù)組為weight的哈夫曼樹haffTree*/{inti,j,m1,m2,x1,x2;/*哈夫曼樹haffTree[]初始化。n個(gè)葉結(jié)點(diǎn)共有2n-1個(gè)結(jié)點(diǎn)*/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個(gè)非葉結(jié)點(diǎn)*/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ù)組元素，其它略去未畫。在以上算法中主要有一個(gè)二重循環(huán)，內(nèi)循環(huán)的平均循環(huán)次數(shù)均為O(n),外循環(huán)大約n次，所以該算法的時(shí)間復(fù)雜度為O(n2)。7.7.3哈夫曼樹的應(yīng)用

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

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

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

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

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

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