第五章樹和二叉樹

1、張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述15.1樹與樹林5.2樹和樹林的存儲表示 5.3二 叉 樹 5.4二叉樹的存儲表示5.5哈夫曼算法及其應(yīng)用張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述2線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 樹形結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)，在現(xiàn)實世界中廣泛存在，在計算機領(lǐng)域中也有廣泛應(yīng)用。 本章重點討論二叉樹的存儲結(jié)構(gòu)及其各種操作，并研究樹和森林與二叉樹之間的轉(zhuǎn)換關(guān)系。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述3 5.1.1 5.1.1 樹的定義樹的定義 5.1.2 5.1.2 基本術(shù)語基本術(shù)語 5.1.3 5.1.3 樹林樹林 5.1.4 5.1.4 樹的基本運算樹的基本運算 5.1.5 5.1.5 樹的周游

2、樹的周游 5.1.6 5.1.6 樹林的周游樹林的周游張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述4樹樹(Tree)的例子：一個家族。A有子女B,C； B和 C分別有子女D,E,F和G,H;E有 子女I , J。 T=(N,R) ,其中 N=A, B, C, D, E, F, G, H, I, J R= A, B, A, C, B, D , B, E, B, F, C, G, C, H, E, I, E, J 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述5(c ) 凹入表（a）樹形表示ABCDEFIJGH張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述6(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括號表示法CDEIJF

3、GHAB(b) 文氏圖張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述7 樹樹(Tree)：是包括n(n=0)個結(jié)點結(jié)點的有限集T。當(dāng)T非空時，滿足：（1）有且僅有一個特別標(biāo)出的稱為根根的 結(jié)點；（2）除除根結(jié)點根結(jié)點外，其余結(jié)點可分為m（m=0） 個互不相交非空的有限集T1, T2, , Tm, 其中 每一個集合本身又是一棵樹，稱為根的子樹子樹 (Subtree)。樹的遞歸定義：樹的遞歸定義：空樹空樹：不包括任何結(jié)點的樹。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述8樹結(jié)構(gòu)的特點：樹結(jié)構(gòu)的特點：（1）樹的根的結(jié)點沒前驅(qū)結(jié)點，除了根結(jié)點之外 的所有結(jié)點都有且只有一個前驅(qū)結(jié)點；（2）樹的結(jié)點可以有零個或多個后繼結(jié)點。 樹結(jié)

4、構(gòu)描述的是層次關(guān)系。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述9 (a) 樹t (b) 樹t 圖5.2 樹t和樹t 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述10 父結(jié)點父結(jié)點，子結(jié)點，子結(jié)點，邊邊 若結(jié)點y是結(jié)點x的一棵子樹的根，則x稱作y的父結(jié)父結(jié)點點（或父母）；y稱作x的子結(jié)點子結(jié)點（或子女）；有序?qū)ΨQ作從x到y(tǒng)的邊邊。例如樹t中，C是E的父結(jié)點，E是C的子結(jié)點，是從C到E的邊（它對應(yīng)著圖中的有向線段CE）。 兄弟結(jié)點兄弟結(jié)點具有同一父母的結(jié)點彼此稱作兄弟兄弟。樹t中B，C，D互為兄弟，F(xiàn)，G互為兄弟，等等。注意，E和F并不是兄弟。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述11 祖先祖先，子孫子孫若結(jié)點y在以結(jié)點x

5、為根的一個子樹（或樹）中，且yx，則稱x是y的祖先祖先，y是x的子孫子孫。例如樹t中，A是其它各結(jié)點的祖先；C是E，H，I，J的祖先。 路徑路徑，路徑長度路徑長度如果x是y的一個祖先，又有xx0，x1，xny，滿足xi（i0，1，n-1）為xi+1的父結(jié)點，則稱x0，x1，xn為從x到y(tǒng)的一條路徑路徑。n稱為這條路徑的長度路徑的長度。路徑中相鄰的兩個結(jié)點可以表示成一條邊。 例如樹t中A，C，E，I，J是從A到J的一條路徑，其長度為4。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述12 結(jié)點的層數(shù)結(jié)點的層數(shù)規(guī)定根的層數(shù)根的層數(shù)為0，其余結(jié)點的層數(shù)結(jié)點的層數(shù)等于其父母結(jié)點的層數(shù)加1。例如t中，0層的結(jié)點是A，

6、1層的結(jié)點有B，C，D，4層的結(jié)點是J。 樹的深度或高度樹的深度或高度樹中結(jié)點的最大層數(shù)稱為樹的深度樹的深度或樹的高度樹的高度。 例如樹t中，樹的深度為4。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述13 結(jié)點的度數(shù)結(jié)點的度數(shù)、樹的度數(shù)樹的度數(shù)結(jié)點的子女個數(shù)叫作結(jié)點的度數(shù)度數(shù)。樹中度數(shù)最大的結(jié)點的度數(shù)叫作樹的度數(shù)樹的度數(shù)。例如t中A，C，E，J的度數(shù)分別為3，1，2，0；t的度數(shù)為3 樹葉樹葉、分支結(jié)點分支結(jié)點度數(shù)為0的結(jié)點稱作樹葉樹葉或終端結(jié)點終端結(jié)點；度數(shù)大于0的結(jié)點稱作分支結(jié)點分支結(jié)點或非終端結(jié)點非終端結(jié)點。例如樹t中B，F(xiàn)，G，H，J都是樹葉，其余結(jié)點都是分支結(jié)點。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描

7、述14 無序樹無序樹、有序樹有序樹對子樹的次序不加區(qū)別的樹叫作無序樹無序樹。對子樹之間的次序加以區(qū)別的樹叫作有序樹有序樹。例如在圖5.2中，按無序樹的概念t和t是同一棵樹，按有序樹的概念則是不同的樹，本章討論的樹一般是有序樹。 結(jié)點的次序結(jié)點的次序 在有序樹中可以從左到右地規(guī)定結(jié)點的次序次序。按從左到右的順序，我們可以把一個結(jié)點的最左邊的子結(jié)點簡稱為最左子結(jié)點最左子結(jié)點，或直接稱為長子長子，而把長子右邊的結(jié)點稱為次子次子。例如在t中結(jié)點B是結(jié)點A的長子，結(jié)點C是結(jié)點A的次子，是結(jié)點B的兄弟。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述15樹林樹林：是m（m=0）棵互不相交的樹所組成的集合。就邏輯結(jié)構(gòu)而言

8、，任何一棵樹是一個二元組二元組Tree=(root,F) , 其中root稱為樹的根結(jié)點，F(xiàn)是m（m0）棵子樹構(gòu)成的樹林，F(xiàn)=(T1, T2,Tm), 其中Ti=(ri,Fi)稱作根root的第i棵子樹；當(dāng)m0時，在樹根和其子樹林之間存在下列關(guān)系: RF= | i=1,2,m, m0張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述16 創(chuàng)建一棵空樹Tree createTree( Node p, Tree t1, Tree t2, , Tree ti ) i=1, 2, 3, 判斷某棵樹是否為空int isNull ( Tree t ) 求樹中的根結(jié)點，若為空樹，則返回一特殊值Node root ( Tree

9、 t ) 求某個指定結(jié)點的父結(jié)點，當(dāng)指定結(jié)點為根時，返回一特殊值Node parent ( Node p ) 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述17 求樹中某個指定結(jié)點的最左子結(jié)點，當(dāng)指定結(jié)點為樹葉時，返回一特殊值Node leftChild ( Node p ) 求樹中某個指定結(jié)點的右兄弟結(jié)點，當(dāng)指定結(jié)點沒有右兄弟時，返回一特殊值Node rightSibling ( Node p ) 樹的周游：即按某種方式訪問樹中的所有結(jié)點，并使每個結(jié)點恰好被訪問一次。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述185.1.5 5.1.5 樹的周游樹的周游1. 周游的定義:按某一規(guī)律系統(tǒng)的訪問樹中的所有 結(jié)點，并使每個

10、結(jié)點恰好被訪問一次。2. 周游的方法：按深度方向和按寬度方向周游。 （I）按深度方向（以右圖為例）a. 先根次序b. 中根次序c. 后根次序張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述19a. 先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 訪問根結(jié)點； （2）從左到右按先根次序周游根結(jié)點的每棵子樹。 b. 中根次序 (2,1,8,5,9,3,10,6,7,4) （1）按中根次序周游根結(jié)點的最左子樹； （2）訪問根結(jié)點； （3）從左到右按中根次序周游根結(jié)點的其它各子樹。c. 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）從左到右按后根次序周游根結(jié)點的每棵子樹; （2）訪問根

11、結(jié)點。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述20（II）按寬度方向周游 先訪問層數(shù)為0的結(jié)點，然后從左到右逐個訪 問層數(shù)為1的結(jié)點，依此類推，直到訪問完樹中 的全部結(jié)點。 層次序列（1，2，3，4，5，6，7，8，9，10）張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述211. 先根（A, B, C, K, D, E, H, F, J, G )2. 后根 ( B, K, C, A, H, E, J, F, G, D )5.1.6 5.1.6 樹林的周游樹林的周游張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述22 5.2.1 5.2.1 樹的存儲表示樹的存儲表示 5.2.2 5.2.2 樹林的存儲表示樹林的存儲表示 5.2.3

12、5.2.3 樹和樹林的其它表示法樹和樹林的其它表示法* *張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述235.2.1 5.2.1 樹的存儲表示樹的存儲表示 樹的父指針表示法 樹的子表表示法 樹的長子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述24struct ParTreeNode/* 樹中結(jié)點結(jié)構(gòu) */ DataTypeinfo; /* 結(jié)點中的元素 */intparent; /* 結(jié)點的父結(jié)點位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放樹中的結(jié)點 */ int n; /* 樹中結(jié)點的個數(shù) */; typedef struct

13、 ParTree *PParTree;樹的父指針表示法用一組連續(xù)空間存儲樹的結(jié)點，并附設(shè)一個指示器指示其雙親結(jié)點的位置。結(jié)構(gòu)類型如下：張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述25 優(yōu)點：a)容易找到父結(jié)點及其所有的祖先； b)能找到結(jié)點的子女和兄弟； 缺點：a)沒有表示出結(jié)點之間的左右次序； b)找結(jié)點的子女和兄弟比較費事。改進方法：按一種周游次序在數(shù)組中存放結(jié)點,。常見的一種方法是依次存放樹的先根序列，如下圖：張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述26(a) (b) 圖5.5 一棵樹的父指針表示 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述27樹的子表表示法 結(jié)點表中的每一元素又包含一個子表，存放該結(jié)點的所有子結(jié)點。

14、結(jié)點表順序存放，子表用鏈接表示。struct EdgeNode /* 子表中節(jié)點的結(jié)構(gòu) */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 結(jié)點表中節(jié)點的結(jié)構(gòu) */DataTypeinfo;struct EdgeNode*children;張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述28子表表示的樹結(jié)構(gòu)定義如下：struct ChiTree /* 樹結(jié)構(gòu) */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根結(jié)點的位置 */ intn; /* 結(jié)點的個數(shù) */typedef struct

15、ChiTree * PChiTree; 求某個結(jié)點的最左子女運算很容易實現(xiàn)，找到結(jié)點的全部子女也很容易，但求某個結(jié)點的父母和右兄弟實現(xiàn)起來比較費事。另一個缺點是：合并若干個子樹構(gòu)成一個新樹時（createTree_chitree操作）也要考慮多個結(jié)點表的合并問題，由于這些結(jié)點表通常用順序方式表示，所以合并起來比較麻煩。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述29 info parent 0 a 1 b 2 d 3 e 4 h 5 i 6 j 7 c 8 f 9 g 1 7 2 3 4 6 8 9 5 圖5.6 樹的子表表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述30 在樹的每個結(jié)點中，除信息域外，增加指向

16、其最左子女和右兄弟的指針。struct CSNode; /* 樹中結(jié)點結(jié)構(gòu) */typedef struct CSNode *PCSNode;/* 結(jié)點的指針類型 */struct CSNode /* 結(jié)點結(jié)構(gòu)定義 */ DataType info;/* 結(jié)點中的元素 */PCSNode lchild; /* 結(jié)點的最左子女的指針 */PCSNode rsibling;/* 結(jié)點的右兄弟的指針 */; typedef struct CSNode *CSTree; /* 樹類型定義 */ 樹的長子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述31 t a b d c e h i j f g 圖5.

17、7 樹的長子兄弟表法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述325.2.2 5.2.2 樹林的存儲表示樹林的存儲表示 父指針表示法 子表表示法 長子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述33樹林的父結(jié)點表示方法 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述34 info parent 0 A 1 B 2 C 3 K 4 D 5 E 6 H 7 F 8 J 9 G 1 2 3 5 9 8 6 7 樹林的子表表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述35 t A B D C E H J K F G 樹林的長子兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述36 5.3.1 5.3.1 二叉樹的基本概念二叉樹的基本概念 5

18、.3.2 5.3.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 5.3.3 5.3.3 二叉樹的基本運算二叉樹的基本運算 5.3.4 5.3.4 二叉樹的周游二叉樹的周游 5.3.5 5.3.5 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述37二叉樹： 它是結(jié)點的有限集合，這個集合或者為空集或者由一個根及兩棵不相交的分別稱作這個根的“左子樹”和“右子樹”的二叉樹組成。 它的每一個結(jié)點至多有兩棵子樹，并且子樹有左右之分，不能隨意顛倒。5.3.1 5.3.1 二叉樹的基本概念二叉樹的基本概念張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述38二叉樹的基本形態(tài)：左子樹右子樹右子樹左子樹（1）空二叉樹

19、（2）只有一個根結(jié)點（3）有根結(jié)點 和左子樹（4）有根結(jié)點 和右子樹（5）有根結(jié)點 和左，右子樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述39 二叉樹不是樹的特殊情形，它們是兩個概念。 樹和二叉樹之間最主要的差別是：二叉樹中結(jié)點的子樹要區(qū)分為左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。 （3）和（4）是兩棵不同的二叉樹，但作為樹，它們是相同的。 在二叉樹中可定義類似樹中的概念。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述40 滿二叉樹滿二叉樹：如果一棵二叉樹的任何結(jié)點或者是樹葉，或者有兩棵非空子樹，則此二叉樹稱作“滿二叉樹”。 完全二叉樹完全二叉樹：如果一棵二叉樹至多只有最下

20、面的兩層結(jié)點度數(shù)可以小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為“完全二叉樹”。完全二叉樹不一定是滿二叉樹。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述41滿二叉樹完全二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述42擴充二叉樹擴充二叉樹 ： 把原二叉樹的結(jié)點都變?yōu)槎葦?shù)為2的分支結(jié)點，也就是說，如果原結(jié)點的度數(shù)為2，則不變，度數(shù)為1，則增加一個分支，度數(shù)為0（樹葉）增加兩個分支。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述43在擴充的二叉樹里，新增加的外部結(jié)點的個數(shù)比原來的內(nèi)部結(jié)點個數(shù)多1。 “外部路徑長度”E：在擴充的二叉樹里從根到每個外部結(jié)點的路徑長度之和?！皟?nèi)部路徑長度”I：在擴充的二叉

21、樹里從根到每個內(nèi)部結(jié)點的路徑長度之和。 E = I + 2n 其中，n是內(nèi)部結(jié)點的個數(shù)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述44證明：當(dāng)n=1時，I=0, E=2, 此等式成立。 設(shè)有n個內(nèi)部結(jié)點的擴充二叉樹，下式成立。 En=In+2n (1) 對于 n+1 個內(nèi)部結(jié)點的擴充二叉樹，去掉一個 作為原來二叉樹路徑長度為K的內(nèi)部結(jié)點，內(nèi)部路徑長度變?yōu)椋?In=In+1-K (2) 外部路徑長度變?yōu)椋篍n=En+1-2(K+1)+K= En+1 -K-2 即： En+1= En+K+2 En+1= (In+2n) +K+2= (In+1-K) +2n+K+2= In+1+2(n+1) 代入（1） 代入

22、（2）張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述45abceef張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述46性質(zhì)性質(zhì)1. 在非空二叉樹的第i層上至多有2i個結(jié)點（i0）。歸納： i=0, 結(jié)點數(shù)=1=20 . 假設(shè)對于j(0j i), 結(jié)點數(shù)至多有2j . 對于i=j+1, 結(jié)點數(shù)至多為 2* 2j=2j+1 .性質(zhì)性質(zhì)2. 深度為k的二叉樹至多有2k+1-1個結(jié)點（k 0）。 K k M= mi 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k5.3.2 5.3.2 二叉樹的性質(zhì)二叉樹的性質(zhì)張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述47性質(zhì)性質(zhì)3. 對任何一棵非空二叉樹T，如果葉結(jié)點數(shù) 為n0

23、， 度為2的結(jié)點數(shù)為n2，則n0=n2+1。 n0+n1+n2 = 所有 結(jié)點的度數(shù)和+1 = n1+ 2*n2 +1 性質(zhì)性質(zhì)4. 具有n個結(jié)點的完全二叉樹的深度k為log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述48性質(zhì)性質(zhì)5. 如果對一棵有n個結(jié)點的完全二叉樹按層次次序 從1開始編號，則對任一結(jié)點i（1 in)，有： 1）i=1，序號結(jié)點i是根；i1, 其雙親結(jié)點是 i/2 。 2）2i n，序號為i的結(jié)點的左子女結(jié)點的序號為2i； 2in ,序

24、號為i的結(jié)點無左子女。 3）2i+1 n，序號為i的結(jié)點的右子女結(jié)點的序號 為2i+1; 2i+1 n,序號為i的結(jié)點無右子女。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述49性質(zhì)5的證明：對于（2）和（3） 當(dāng)i=1時， 2i=2 n ，左子女結(jié)點的序號為2。2i+1=3 n， 右子女結(jié)點的序號為3。 假設(shè)對于序號為j的結(jié)點，命題成立。 對于i=j+1，其左子女結(jié)點的序號等于j的右子女結(jié)點的序號加1，即：2j+1+1=2(j+1) 其右子女結(jié)點的序號等于：2(j+1)+1根據(jù)（2）和（3），知的父結(jié)點為i/2. 完全二叉樹的層次序列，反映了它的結(jié)構(gòu)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述50123jj+1 2

25、j 2j+1 2(j+1) 2(j+1)+1張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述515.3.3 5.3.3 二叉樹的基本運算二叉樹的基本運算創(chuàng)建一棵空二叉樹；判斷某棵二叉樹是否為空；求二叉樹的根結(jié)點，若為空，則返回一特殊值；求二叉樹中某個指定結(jié)點的父結(jié)點，當(dāng)指定結(jié)點為根時，返回一特殊值；求二叉樹中某個指定結(jié)點的左子女結(jié)點，當(dāng)指定結(jié)點沒有左子女時，返回一特殊值；求二叉樹中某個指定結(jié)點的右子女結(jié)點，當(dāng)指定結(jié)點沒有右子女時，返回一特殊值；二叉樹的周游。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述52二叉樹的周游二叉樹的周游(Traversing Binary Tree)： 按某條搜索路徑訪問二叉樹中的所有結(jié)點 ，使

26、得每個結(jié)點被訪問一次且僅被訪問一次。三種方式： 先根次序 (DLR) 對稱序 (LDR) 后根次序 (LRD)DLR張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述53ABDCEFIHG 圖5.15 二叉樹先根次序A B D C E G F H I 后根次序D B G E H I F C A 對稱序（中根次序）D B A E G C H F I張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述54 對右圖進行先根、后根和中根次序周游得到如下的結(jié)點序列： 先根：-ab+cd 前綴表示 后根：ab-cd+ 后綴表示 (波蘭表示法) 對稱序：a-b c+d 中綴表示-+abcd圖 5.16 表達式的二叉樹表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C

27、語言描述551遞歸算法先根次序中根次序后根次序二. 非遞歸算法 (用自定義的棧來代替系統(tǒng)的棧)先根次序中根次序后根次序 1 2張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述565.3.5 5.3.5 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換 1. 樹、樹林轉(zhuǎn)換為二叉樹執(zhí)行步驟：（1）在所有相鄰的兄弟結(jié)點之間連一條線；（2）對每個非終端結(jié)點，只保留它到其最左子女的 連線，刪去它與其它子女的連線；（3）以根結(jié)點為軸心，將整棵樹進行旋轉(zhuǎn)。樹、樹林樹、樹林 二叉樹二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述57ABCKDEFGHJ圖5.20 樹林轉(zhuǎn)換為二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述58執(zhí)行步驟：（1）若某結(jié)點

28、是其父母的左子女，則把該結(jié)點 的右子女，右子女的右子女， ,都與 該結(jié)點的父母用線連接起來； （2）去掉原二叉樹中所有父母到右子女的連線。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述59ABDCEKHFJG圖 5.22 二叉樹轉(zhuǎn)換為樹林張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述60二叉樹的存儲表示 5.4.1 5.4.1 順序表示順序表示 5.4.2 5.4.2 鏈接表示鏈接表示 5.4.3 5.4.3 二叉樹的生成二叉樹的生成 5.4.4 5.4.4 線索二叉樹線索二叉樹* *張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述61 用一組地址連續(xù)的存儲單元按層次次序依次存儲完全二叉樹的結(jié)點。完全二叉樹的層次序列反映了它的層次結(jié)構(gòu)。

29、ABCGFEDHIJ A B C D E F G H I J 下標(biāo) 0 1 2 3 4 5 6 7 8 9張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述62 對于一般二叉樹，則應(yīng)將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組的相應(yīng)分量中。圖514 一般二叉樹及其順序表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述63采用順序表示，類型聲明如下： struct SeqBTree /* 順序樹類型定義 */ DataType nodelistMAXNODE;int n;/* 改造成完全二叉樹后，結(jié)點的個數(shù) */ ；typedef struct SeqBTree *PSeqBTree;張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述

30、64 二叉樹的鏈接表示是指用一個鏈表來存儲一棵二叉樹，二叉樹中的每一個結(jié)點用鏈表中的一個鏈結(jié)點來存儲，最常用的鏈接表示方式是左-右指針表示法（llink-rlink表示法，也稱做二叉鏈表），這種表示法在每個鏈結(jié)點中除存儲結(jié)點本身的數(shù)據(jù)外，再設(shè)置兩個指針字段：llink和rlink，分別存放結(jié)點的左子女和右子女所在鏈結(jié)點的存儲地址，當(dāng)結(jié)點的某個子女為空時，則相應(yīng)的指針為空指針。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述65struct BinTreeNode;/* 二叉樹中結(jié)點 */typedef struct BinTreeNode *PBinTreeNode;/* 結(jié)點的指針類型 */struct

31、BinTreeNode DataType info;/* 數(shù)據(jù)域 */PBinTreeNode llink;/* 指向左子女 */PBinTreeNode rlink;/* 指向右子女 */;typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述66ABDCEFIHGt A B C E F I H G D 圖5.15 二叉樹的二叉鏈表表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述67tA B D C E F I H G 圖5.15 三叉鏈表表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述68 周游是二叉樹各種操

32、作的基礎(chǔ)，可以在周游過程中進行各種操作，如可以在周游過程中生成結(jié)點，從而建立一棵二叉樹。 例：讀入字符序列： ABDCEGFHI建立圖5.13所示的二叉樹，其中，表示空結(jié)點。算法5.5 按先根序列創(chuàng)建二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述69t A B C E F I H G D 圖5.15 二叉樹的二叉鏈表表示線索二叉樹線索二叉樹* * 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述70保存遍歷過程中得到的信息以供某些操作使用（1增加兩個指針（2利用結(jié)構(gòu)中的空鏈域，并設(shè)立標(biāo)志。線索線索：指向結(jié)點前驅(qū)或后繼的指針。線索二叉樹線索二叉樹：加上線索的二叉樹。線索化線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹

33、的過程。按對稱序線索化二叉樹按對稱序線索化二叉樹: :按對稱序周游二叉樹，周游到那個結(jié)點對那個結(jié)點加線索。按對稱序周游對稱序穿線樹按對稱序周游對稱序穿線樹: :沿線索周游。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述71struct ThrTreeNode;typedef struct ThrTreeNode*PThrTreeNode;struct ThrTreeNode /*結(jié)點類型*/ DataType info;PThrTreeNode llink, rlink;int ltag, rtag;typedef struct ThrTreeNode *ThrTree, /*樹類型*/typedef Th

34、rTree *PThrTree; /*類型的指針類型*/張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述72Struct SeqStack /*棧元素的類型為PThrTreeNode*/ PThrTreeNode sMAXNODE; int t; ;typedef Struct SeqStack *PSeqStack;算法算法5.6 按對稱序線索化二叉樹按對稱序線索化二叉樹算法算法5.7 按對稱序周游對稱序穿線樹按對稱序周游對稱序穿線樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述73 對稱序穿線樹里的線索總是指向二叉樹中更高層的結(jié)點，也就是說是“向上”指的(如下圖）。利用該“向上”指的線索我們可以在對稱序穿線樹里找出指定結(jié)點在先根下的后繼結(jié)點和后根下的前驅(qū)結(jié)點。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述74哈夫曼算法及其應(yīng)用 5.5.1 5.5.1 哈夫曼樹哈夫曼樹 5.5.2 5.5.2 哈夫曼哈夫曼(Huffman)(Huffman)算法算法 5.5.3 5.5.3 哈夫曼編碼哈夫曼編碼張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述755.5.1 5.5.1 哈夫曼樹哈夫曼樹擴充二叉樹的外部路徑長度：其中：li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)點的個數(shù) 1miiEl擴充二叉樹的帶權(quán)的外部路徑長度 其中：wi是第i個外部結(jié)點的權(quán)值，li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)