第五章樹和二叉樹

1、張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述15.1樹與樹林5.2樹和樹林的存儲(chǔ)表示 5.3二 叉 樹 5.4二叉樹的存儲(chǔ)表示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)實(shí)世界中廣泛存在，在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用。 本章重點(diǎn)討論二叉樹的存儲(chǔ)結(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 樹的基本運(yùn)算樹的基本運(yùn)算 5.1.5 5.1.5 樹的周游

2、樹的周游 5.1.6 5.1.6 樹林的周游樹林的周游張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述4樹樹(Tree)的例子：一個(gè)家族。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) 嵌套括號(hào)表示法CDEIJF

3、GHAB(b) 文氏圖張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述7 樹樹(Tree)：是包括n(n=0)個(gè)結(jié)點(diǎn)結(jié)點(diǎn)的有限集T。當(dāng)T非空時(shí)，滿足：（1）有且僅有一個(gè)特別標(biāo)出的稱為根根的 結(jié)點(diǎn)；（2）除除根結(jié)點(diǎn)根結(jié)點(diǎn)外，其余結(jié)點(diǎn)可分為m（m=0） 個(gè)互不相交非空的有限集T1, T2, , Tm, 其中 每一個(gè)集合本身又是一棵樹，稱為根的子樹子樹 (Subtree)。樹的遞歸定義：樹的遞歸定義：空樹空樹：不包括任何結(jié)點(diǎn)的樹。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述8樹結(jié)構(gòu)的特點(diǎn)：樹結(jié)構(gòu)的特點(diǎn)：（1）樹的根的結(jié)點(diǎn)沒前驅(qū)結(jié)點(diǎn)，除了根結(jié)點(diǎn)之外 的所有結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；（2）樹的結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。 樹結(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é)點(diǎn)父結(jié)點(diǎn)，子結(jié)點(diǎn)，子結(jié)點(diǎn)，邊邊 若結(jié)點(diǎn)y是結(jié)點(diǎn)x的一棵子樹的根，則x稱作y的父結(jié)父結(jié)點(diǎn)點(diǎn)（或父母）；y稱作x的子結(jié)點(diǎn)子結(jié)點(diǎn)（或子女）；有序?qū)ΨQ作從x到y(tǒng)的邊邊。例如樹t中，C是E的父結(jié)點(diǎn)，E是C的子結(jié)點(diǎn)，是從C到E的邊（它對(duì)應(yīng)著圖中的有向線段CE）。 兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)具有同一父母的結(jié)點(diǎn)彼此稱作兄弟兄弟。樹t中B，C，D互為兄弟，F(xiàn)，G互為兄弟，等等。注意，E和F并不是兄弟。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述11 祖先祖先，子孫子孫若結(jié)點(diǎn)y在以結(jié)點(diǎn)x

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

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

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

8、，任何一棵樹是一個(gè)二元組二元組Tree=(root,F) , 其中root稱為樹的根結(jié)點(diǎn)，F(xiàn)是m（m0）棵子樹構(gòu)成的樹林，F(xiàn)=(T1, T2,Tm), 其中Ti=(ri,Fi)稱作根root的第i棵子樹；當(dāng)m0時(shí)，在樹根和其子樹林之間存在下列關(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é)點(diǎn)，若為空樹，則返回一特殊值Node root ( Tree

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

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

11、結(jié)點(diǎn)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述20（II）按寬度方向周游 先訪問層數(shù)為0的結(jié)點(diǎn)，然后從左到右逐個(gè)訪 問層數(shù)為1的結(jié)點(diǎn)，依此類推，直到訪問完樹中 的全部結(jié)點(diǎn)。 層次序列（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 樹的存儲(chǔ)表示樹的存儲(chǔ)表示 5.2.2 5.2.2 樹林的存儲(chǔ)表示樹林的存儲(chǔ)表示 5.2.3

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

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

14、結(jié)點(diǎn)表順序存放，子表用鏈接表示。struct EdgeNode /* 子表中節(jié)點(diǎn)的結(jié)構(gòu) */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 結(jié)點(diǎn)表中節(jié)點(diǎn)的結(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é)點(diǎn)的位置 */ intn; /* 結(jié)點(diǎn)的個(gè)數(shù) */typedef struct

15、ChiTree * PChiTree; 求某個(gè)結(jié)點(diǎn)的最左子女運(yùn)算很容易實(shí)現(xiàn)，找到結(jié)點(diǎn)的全部子女也很容易，但求某個(gè)結(jié)點(diǎn)的父母和右兄弟實(shí)現(xiàn)起來比較費(fèi)事。另一個(gè)缺點(diǎn)是：合并若干個(gè)子樹構(gòu)成一個(gè)新樹時(shí)（createTree_chitree操作）也要考慮多個(gè)結(jié)點(diǎn)表的合并問題，由于這些結(jié)點(diǎn)表通常用順序方式表示，所以合并起來比較麻煩。 張乃孝 算法與數(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 在樹的每個(gè)結(jié)點(diǎn)中，除信息域外，增加指向

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

17、7 樹的長(zhǎng)子兄弟表法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述325.2.2 5.2.2 樹林的存儲(chǔ)表示樹林的存儲(chǔ)表示 父指針表示法 子表表示法 長(zhǎng)子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述33樹林的父結(jié)點(diǎn)表示方法 張乃孝 算法與數(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 樹林的長(zhǎng)子兄弟表示法張乃孝 算法與數(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 二叉樹的基本運(yùn)算二叉樹的基本運(yùn)算 5.3.4 5.3.4 二叉樹的周游二叉樹的周游 5.3.5 5.3.5 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述37二叉樹： 它是結(jié)點(diǎn)的有限集合，這個(gè)集合或者為空集或者由一個(gè)根及兩棵不相交的分別稱作這個(gè)根的“左子樹”和“右子樹”的二叉樹組成。 它的每一個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且子樹有左右之分，不能隨意顛倒。5.3.1 5.3.1 二叉樹的基本概念二叉樹的基本概念張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述38二叉樹的基本形態(tài)：左子樹右子樹右子樹左子樹（1）空二叉樹

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

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

21、樹里從根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長(zhǎng)度之和。 E = I + 2n 其中，n是內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述44證明：當(dāng)n=1時(shí)，I=0, E=2, 此等式成立。 設(shè)有n個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹，下式成立。 En=In+2n (1) 對(duì)于 n+1 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹，去掉一個(gè) 作為原來二叉樹路徑長(zhǎng)度為K的內(nèi)部結(jié)點(diǎn)，內(nèi)部路徑長(zhǎng)度變?yōu)椋?In=In+1-K (2) 外部路徑長(zhǎng)度變?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個(gè)結(jié)點(diǎn)（i0）。歸納： i=0, 結(jié)點(diǎn)數(shù)=1=20 . 假設(shè)對(duì)于j(0j i), 結(jié)點(diǎn)數(shù)至多有2j . 對(duì)于i=j+1, 結(jié)點(diǎn)數(shù)至多為 2* 2j=2j+1 .性質(zhì)性質(zhì)2. 深度為k的二叉樹至多有2k+1-1個(gè)結(jié)點(diǎn)（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. 對(duì)任何一棵非空二叉樹T，如果葉結(jié)點(diǎn)數(shù) 為n0

23、， 度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 n0+n1+n2 = 所有 結(jié)點(diǎn)的度數(shù)和+1 = n1+ 2*n2 +1 性質(zhì)性質(zhì)4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度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. 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層次次序 從1開始編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1 in)，有： 1）i=1，序號(hào)結(jié)點(diǎn)i是根；i1, 其雙親結(jié)點(diǎn)是 i/2 。 2）2i n，序號(hào)為i的結(jié)點(diǎn)的左子女結(jié)點(diǎn)的序號(hào)為2i； 2in ,序

24、號(hào)為i的結(jié)點(diǎn)無左子女。 3）2i+1 n，序號(hào)為i的結(jié)點(diǎn)的右子女結(jié)點(diǎn)的序號(hào) 為2i+1; 2i+1 n,序號(hào)為i的結(jié)點(diǎn)無右子女。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述49性質(zhì)5的證明：對(duì)于（2）和（3） 當(dāng)i=1時(shí)， 2i=2 n ，左子女結(jié)點(diǎn)的序號(hào)為2。2i+1=3 n， 右子女結(jié)點(diǎn)的序號(hào)為3。 假設(shè)對(duì)于序號(hào)為j的結(jié)點(diǎn)，命題成立。 對(duì)于i=j+1，其左子女結(jié)點(diǎn)的序號(hào)等于j的右子女結(jié)點(diǎn)的序號(hào)加1，即：2j+1+1=2(j+1) 其右子女結(jié)點(diǎn)的序號(hào)等于：2(j+1)+1根據(jù)（2）和（3），知的父結(jié)點(diǎn)為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 二叉樹的基本運(yùn)算二叉樹的基本運(yùn)算創(chuàng)建一棵空二叉樹；判斷某棵二叉樹是否為空；求二叉樹的根結(jié)點(diǎn)，若為空，則返回一特殊值；求二叉樹中某個(gè)指定結(jié)點(diǎn)的父結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)為根時(shí)，返回一特殊值；求二叉樹中某個(gè)指定結(jié)點(diǎn)的左子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有左子女時(shí)，返回一特殊值；求二叉樹中某個(gè)指定結(jié)點(diǎn)的右子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有右子女時(shí)，返回一特殊值；二叉樹的周游。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述52二叉樹的周游二叉樹的周游(Traversing Binary Tree)： 按某條搜索路徑訪問二叉樹中的所有結(jié)點(diǎn) ，使

26、得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。三種方式： 先根次序 (DLR) 對(duì)稱序 (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 對(duì)稱序（中根次序）D B A E G C H F I張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述54 對(duì)右圖進(jìn)行先根、后根和中根次序周游得到如下的結(jié)點(diǎn)序列： 先根：-ab+cd 前綴表示 后根：ab-cd+ 后綴表示 (波蘭表示法) 對(duì)稱序：a-b c+d 中綴表示-+abcd圖 5.16 表達(dá)式的二叉樹表示張乃孝 算法與數(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é)點(diǎn)之間連一條線；（2）對(duì)每個(gè)非終端結(jié)點(diǎn)，只保留它到其最左子女的 連線，刪去它與其它子女的連線；（3）以根結(jié)點(diǎn)為軸心，將整棵樹進(jìn)行旋轉(zhuǎn)。樹、樹林樹、樹林 二叉樹二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述57ABCKDEFGHJ圖5.20 樹林轉(zhuǎn)換為二叉樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述58執(zhí)行步驟：（1）若某結(jié)點(diǎn)

28、是其父母的左子女，則把該結(jié)點(diǎn) 的右子女，右子女的右子女， ,都與 該結(jié)點(diǎn)的父母用線連接起來； （2）去掉原二叉樹中所有父母到右子女的連線。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述59ABDCEKHFJG圖 5.22 二叉樹轉(zhuǎn)換為樹林張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述60二叉樹的存儲(chǔ)表示 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ù)的存儲(chǔ)單元按層次次序依次存儲(chǔ)完全二叉樹的結(jié)點(diǎn)。完全二叉樹的層次序列反映了它的層次結(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 對(duì)于一般二叉樹，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。圖514 一般二叉樹及其順序表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述63采用順序表示，類型聲明如下： struct SeqBTree /* 順序樹類型定義 */ DataType nodelistMAXNODE;int n;/* 改造成完全二叉樹后，結(jié)點(diǎn)的個(gè)數(shù) */ ；typedef struct SeqBTree *PSeqBTree;張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述

30、64 二叉樹的鏈接表示是指用一個(gè)鏈表來存儲(chǔ)一棵二叉樹，二叉樹中的每一個(gè)結(jié)點(diǎn)用鏈表中的一個(gè)鏈結(jié)點(diǎn)來存儲(chǔ)，最常用的鏈接表示方式是左-右指針表示法（llink-rlink表示法，也稱做二叉鏈表），這種表示法在每個(gè)鏈結(jié)點(diǎn)中除存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，再設(shè)置兩個(gè)指針字段：llink和rlink，分別存放結(jié)點(diǎn)的左子女和右子女所在鏈結(jié)點(diǎn)的存儲(chǔ)地址，當(dāng)結(jié)點(diǎn)的某個(gè)子女為空時(shí)，則相應(yīng)的指針為空指針。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述65struct BinTreeNode;/* 二叉樹中結(jié)點(diǎn) */typedef struct BinTreeNode *PBinTreeNode;/* 結(jié)點(diǎn)的指針類型 */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ǔ)，可以在周游過程中進(jìn)行各種操作，如可以在周游過程中生成結(jié)點(diǎn)，從而建立一棵二叉樹。 例：讀入字符序列： ABDCEGFHI建立圖5.13所示的二叉樹，其中，表示空結(jié)點(diǎn)。算法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增加兩個(gè)指針（2利用結(jié)構(gòu)中的空鏈域，并設(shè)立標(biāo)志。線索線索：指向結(jié)點(diǎn)前驅(qū)或后繼的指針。線索二叉樹線索二叉樹：加上線索的二叉樹。線索化線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹

33、的過程。按對(duì)稱序線索化二叉樹按對(duì)稱序線索化二叉樹: :按對(duì)稱序周游二叉樹，周游到那個(gè)結(jié)點(diǎn)對(duì)那個(gè)結(jié)點(diǎn)加線索。按對(duì)稱序周游對(duì)稱序穿線樹按對(duì)稱序周游對(duì)稱序穿線樹: :沿線索周游。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述71struct ThrTreeNode;typedef struct ThrTreeNode*PThrTreeNode;struct ThrTreeNode /*結(jié)點(diǎn)類型*/ 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 按對(duì)稱序線索化二叉樹按對(duì)稱序線索化二叉樹算法算法5.7 按對(duì)稱序周游對(duì)稱序穿線樹按對(duì)稱序周游對(duì)稱序穿線樹張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語言描述73 對(duì)稱序穿線樹里的線索總是指向二叉樹中更高層的結(jié)點(diǎn)，也就是說是“向上”指的(如下圖）。利用該“向上”指的線索我們可以在對(duì)稱序穿線樹里找出指定結(jié)點(diǎn)在先根下的后繼結(jié)點(diǎn)和后根下的前驅(qū)結(jié)點(diǎn)。張乃孝 算法與數(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 哈夫曼樹哈夫曼樹擴(kuò)充二叉樹的外部路徑長(zhǎng)度：其中：li為從根到第i個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度，m為外部結(jié)點(diǎn)的個(gè)數(shù) 1miiEl擴(kuò)充二叉樹的帶權(quán)的外部路徑長(zhǎng)度 其中：wi是第i個(gè)外部結(jié)點(diǎn)的權(quán)值，li為從根到第i個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度，m為外部結(jié)