第五章樹(shù)和二叉樹(shù)

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

2、樹(shù)的周游 5.1.6 5.1.6 樹(shù)林的周游樹(shù)林的周游張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述4樹(shù)樹(shù)(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語(yǔ)言描述5(c ) 凹入表（a）樹(shù)形表示abcdefijgh張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述6(a(b(d)(e(i)(j)(c(g)(h)(d) 嵌套括號(hào)表示法cdeijf

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

4、構(gòu)描述的是層次關(guān)系。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述9 (a) 樹(shù)t (b) 樹(shù)t 圖5.2 樹(shù)t和樹(shù)t 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述10 父結(jié)點(diǎn)父結(jié)點(diǎn)，子結(jié)點(diǎn)，子結(jié)點(diǎn)，邊邊 若結(jié)點(diǎn)y是結(jié)點(diǎn)x的一棵子樹(shù)的根，則x稱(chēng)作y的父結(jié)父結(jié)點(diǎn)點(diǎn)（或父母）；y稱(chēng)作x的子結(jié)點(diǎn)子結(jié)點(diǎn)（或子女）；有序?qū)ΨQ(chēng)作從x到y(tǒng)的邊邊。例如樹(shù)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)彼此稱(chēng)作兄弟兄弟。樹(shù)t中b，c，d互為兄弟，f，g互為兄弟，等等。注意，e和f并不是兄弟。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述11 祖先祖先，子孫子孫若結(jié)點(diǎn)y在以結(jié)點(diǎn)x

5、為根的一個(gè)子樹(shù)（或樹(shù)）中，且yx，則稱(chēng)x是y的祖先祖先，y是x的子孫子孫。例如樹(shù)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)，則稱(chēng)x0，x1，xn為從x到y(tǒng)的一條路徑路徑。n稱(chēng)為這條路徑的長(zhǎng)度路徑的長(zhǎng)度。路徑中相鄰的兩個(gè)結(jié)點(diǎn)可以表示成一條邊。 例如樹(shù)t中a，c，e，i，j是從a到j(luò)的一條路徑，其長(zhǎng)度為4。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述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。 樹(shù)的深度或高度樹(shù)的深度或高度樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的深度樹(shù)的深度或樹(shù)的高度樹(shù)的高度。 例如樹(shù)t中，樹(shù)的深度為4。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述13 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)、樹(shù)的度數(shù)樹(shù)的度數(shù)結(jié)點(diǎn)的子女個(gè)數(shù)叫作結(jié)點(diǎn)的度數(shù)度數(shù)。樹(shù)中度數(shù)最大的結(jié)點(diǎn)的度數(shù)叫作樹(shù)的度數(shù)樹(shù)的度數(shù)。例如t中a，c，e，j的度數(shù)分別為3，1，2，0；t的度數(shù)為3 樹(shù)葉樹(shù)葉、分支結(jié)點(diǎn)分支結(jié)點(diǎn)度數(shù)為0的結(jié)點(diǎn)稱(chēng)作樹(shù)葉樹(shù)葉或終端結(jié)點(diǎn)終端結(jié)點(diǎn)；度數(shù)大于0的結(jié)點(diǎn)稱(chēng)作分支結(jié)點(diǎn)分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)。例如樹(shù)t中b，f，g，h，j都是樹(shù)葉，其余結(jié)點(diǎn)都是分支結(jié)點(diǎn)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描

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

8、，任何一棵樹(shù)是一個(gè)二元組二元組tree=(root,f) , 其中root稱(chēng)為樹(shù)的根結(jié)點(diǎn)，f是m（m0）棵子樹(shù)構(gòu)成的樹(shù)林，f=(t1, t2,tm), 其中ti=(ri,fi)稱(chēng)作根root的第i棵子樹(shù)；當(dāng)m0時(shí)，在樹(shù)根和其子樹(shù)林之間存在下列關(guān)系: rf= | i=1,2,m, m0張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述16創(chuàng)建一棵空樹(shù)tree createtree( node p, tree t1, tree t2, , tree ti ) i=1, 2, 3, 判斷某棵樹(shù)是否為空int isnull ( tree t )求樹(shù)中的根結(jié)點(diǎn)，若為空樹(shù)，則返回一特殊值node root ( tree t

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

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

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

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

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

14、表順序存放，子表用鏈接表示。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語(yǔ)言描述28子表表示的樹(shù)結(jié)構(gòu)定義如下：struct chitree /* 樹(shù)結(jié)構(gòu) */ struct chitreenode nodelistmaxnum; introot; /* 根結(jié)點(diǎn)的位置 */ intn; /* 結(jié)點(diǎn)的個(gè)數(shù) */typedef struct ch

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

16、左子女和右兄弟的指針。struct csnode; /* 樹(shù)中結(jié)點(diǎn)結(jié)構(gòu) */typedef struct csnode *pcsnode;/* 結(jié)點(diǎn)的指針類(lèi)型 */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; /* 樹(shù)類(lèi)型定義 */ 樹(shù)的長(zhǎng)子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述31 t a b d c e h i j f g 圖5.7

17、樹(shù)的長(zhǎng)子兄弟表法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述325.2.2 5.2.2 樹(shù)林的存儲(chǔ)表示樹(shù)林的存儲(chǔ)表示 父指針表示法 子表表示法 長(zhǎng)子-兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述33樹(shù)林的父結(jié)點(diǎn)表示方法 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述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ù)林的子表表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述35 t a b d c e h j k f g 樹(shù)林的長(zhǎng)子兄弟表示法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述36 5.3.1 5.3.1 二叉樹(shù)的基本概念二叉樹(shù)的基本概念 5.3

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

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

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

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語(yǔ)言描述44證明：當(dāng)n=1時(shí)，i=0, e=2, 此等式成立。 設(shè)有n個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù)，下式成立。 en=in+2n (1) 對(duì)于 n+1 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù)，去掉一個(gè) 作為原來(lái)二叉樹(shù)路徑長(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） 代入（2

22、）張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述45abceef張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述46性質(zhì)性質(zhì)1. 在非空二叉樹(shù)的第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的二叉樹(shù)至多有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 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述47性質(zhì)性質(zhì)3. 對(duì)任何一棵非空二叉樹(shù)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)的完全二叉樹(shù)的深度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語(yǔ)言描述48性質(zhì)性質(zhì)5. 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層次次序 從1開(kāi)始編號(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 ,序號(hào)為

24、i的結(jié)點(diǎn)無(wú)左子女。 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)無(wú)右子女。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述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. 完全二叉樹(shù)的層次序列，反映了它的結(jié)構(gòu)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述50123jj+1 2j

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

26、個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。三種方式： 先根次序 (dlr) 對(duì)稱(chēng)序 (ldr) 后根次序 (lrd)dlr張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述53abdcefihg 圖5.15 二叉樹(shù)先根次序a b d c e g f h i 后根次序d b g e h i f c a 對(duì)稱(chēng)序（中根次序）d b a e g c h f i張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述54 對(duì)右圖進(jìn)行先根、后根和中根次序周游得到如下的結(jié)點(diǎn)序列： 先根：-ab+cd 前綴表示 后根：ab-cd+ 后綴表示 (波蘭表示法) 對(duì)稱(chēng)序：a-b c+d 中綴表示-+abcd圖 5.16 表達(dá)式的二叉樹(shù)表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言

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

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

29、列反映了它的層次結(jié)構(gòu)。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語(yǔ)言描述62 對(duì)于一般二叉樹(shù)，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。圖514 一般二叉樹(shù)及其順序表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述63采用順序表示，類(lèi)型聲明如下： struct seqbtree /* 順序樹(shù)類(lèi)型定義 */ datatype nodelistmaxnode;int n;/* 改造成完全二叉樹(shù)后，結(jié)點(diǎn)的個(gè)數(shù) */ ；typedef struct seqbtree *pseqbtree;張乃孝 算

30、法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述64 二叉樹(shù)的鏈接表示是指用一個(gè)鏈表來(lái)存儲(chǔ)一棵二叉樹(shù)，二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)用鏈表中的一個(gè)鏈結(jié)點(diǎn)來(lái)存儲(chǔ)，最常用的鏈接表示方式是左-右指針表示法（llink-rlink表示法，也稱(chēng)做二叉鏈表），這種表示法在每個(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語(yǔ)言描述65struct bintreenode;/* 二叉樹(shù)中結(jié)點(diǎn) */typedef struct bintreenode *pbintreenode;/* 結(jié)點(diǎn)的指針類(lèi)

31、型 */struct bintreenode datatype info;/* 數(shù)據(jù)域 */pbintreenode llink;/* 指向左子女 */pbintreenode rlink;/* 指向右子女 */;typedef struct bintreenode *bintree; typedef bintree *pbintree; 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述66abdcefihgt a b c e f i h g d 圖5.15 二叉樹(shù)的二叉鏈表表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述67ta b d c e f i h g 圖5.15 三叉鏈表表示張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述6

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

33、遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程。按對(duì)稱(chēng)序線索化二叉樹(shù)按對(duì)稱(chēng)序線索化二叉樹(shù): :按對(duì)稱(chēng)序周游二叉樹(shù)，周游到那個(gè)結(jié)點(diǎn)對(duì)那個(gè)結(jié)點(diǎn)加線索。按對(duì)稱(chēng)序周游對(duì)稱(chēng)序穿線樹(shù)按對(duì)稱(chēng)序周游對(duì)稱(chēng)序穿線樹(shù): :沿線索周游。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述71struct thrtreenode;typedef struct thrtreenode*pthrtreenode;struct thrtreenode /*結(jié)點(diǎn)類(lèi)型*/ datatype info;pthrtreenode llink, rlink;int ltag, rtag;typedef struct thrtreenode *thrtree, /*樹(shù)類(lèi)型*

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