1、第6章 樹,數(shù)據(jù)結(jié)構(gòu)（C描述）,6.9 二叉樹的應(yīng)用哈夫曼樹,6.8 樹和森林,6.7 線索二叉樹,6.4 遍歷二叉樹,6.3 二叉樹的定義及存儲(chǔ)結(jié)構(gòu),6.1 樹的基本概念,目錄,6.2 樹的存儲(chǔ)結(jié)構(gòu),6.5 二叉排序樹,6.6 平衡二叉樹,在許多領(lǐng)域許多問(wèn)題不能或難用線性結(jié)構(gòu)表示（哈夫曼編碼、判定問(wèn)題），故研究非線性的數(shù)據(jù)結(jié)構(gòu)。樹是一種應(yīng)用十分廣泛的非線性數(shù)據(jù)結(jié)構(gòu)。,6.1 樹的基本概念,6.1.1 樹的定義,樹的定義,樹是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，稱為空樹；若n0，則稱為非空樹，在任一棵非空樹中： （1）有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)。它只有直接后繼，但沒(méi)有直接前驅(qū)

2、； （2）除根結(jié)點(diǎn)以外的其它結(jié)點(diǎn)可以劃分為m（m0）個(gè)互不相交的有限集合T0，T1，Tm-1，且每個(gè)集合Ti（i=0,1,m-1）本身又是一棵樹，稱為根的子樹。由此可知，樹的定義是一個(gè)遞歸的定義，即樹的定義中又用到了樹的概念。,從定義中看出樹結(jié)構(gòu)具有以下特點(diǎn)：,（1）有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有直接前驅(qū)，即根結(jié)點(diǎn)。 （2）除根結(jié)點(diǎn)之外，其余所有結(jié)點(diǎn)有且僅有一個(gè)直接前趨結(jié)點(diǎn)。 （3）包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼結(jié)點(diǎn)。 從此可見，樹型結(jié)構(gòu)的特點(diǎn)是，數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。 樹的結(jié)構(gòu)參見圖6-1。,在圖6-1(c)中，樹的根結(jié)點(diǎn)為A，該樹還可以分為三個(gè)互不相交子集T0，T1，T2，具體

3、請(qǐng)參見圖6-2，其中 T0=B，E，F(xiàn)，J，K，L，T1=C，G，T2=D，H，I，M,而T0，T1，T2又可以分解成若干棵不相交子樹。如：T0可以分解成T00，T01兩個(gè)不相交子集，T00=E，J，K，L，T01=F，而T00又可以分為三個(gè)不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,6.1.2 基本術(shù)語(yǔ),1.樹的結(jié)點(diǎn) 指樹中的一個(gè)數(shù)據(jù)元素，一般用一個(gè)字母表示。,2.結(jié)點(diǎn)的度 一個(gè)結(jié)點(diǎn)包含子樹的數(shù)目，稱為該結(jié)點(diǎn)的度。,3.樹葉（葉子） 度為0的結(jié)點(diǎn)，稱為葉子結(jié)點(diǎn)或樹葉，也叫終端結(jié)點(diǎn)。,4.分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)） 除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)，為分支結(jié)點(diǎn)。

4、通常又將除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。,6.雙親結(jié)點(diǎn) 若結(jié)點(diǎn)X有子女Y，則X為Y的雙親結(jié)點(diǎn)。,7.祖先結(jié)點(diǎn),8.子孫結(jié)點(diǎn) 某一結(jié)點(diǎn)的子女的子女為該結(jié)點(diǎn)子孫。,5.孩子結(jié)點(diǎn) 若結(jié)點(diǎn)X有子樹，則子樹的根結(jié)點(diǎn)為X的孩子結(jié)點(diǎn)，也稱為孩子。如圖6-1（c）中A的孩子為B，C，D。,10結(jié)點(diǎn)的層次 從根結(jié)點(diǎn)開始定義，根為第一層，根的孩子為第二層，依次類推。,11. 樹的高度（深度） 樹中結(jié)點(diǎn)所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個(gè)根結(jié)點(diǎn)的樹高度為1。,12.樹的度 樹中結(jié)點(diǎn)度的最大值稱為樹的度。,9.兄弟結(jié)點(diǎn) 具有同一個(gè)雙親的結(jié)點(diǎn)，稱為兄弟結(jié)點(diǎn)。,13. 有序樹 若一棵樹中所有子樹從左

5、到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。,14. 無(wú)序樹 若一棵樹中所有子樹的次序無(wú)關(guān)緊要，則稱為無(wú)序樹。,15森林（樹林） 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個(gè)特殊的森林。 樹與森林的關(guān)系,6.1.3 樹的表示,1樹形結(jié)構(gòu)表示法 （掌握） 具體參 見圖6-1 。,2. 凹入法表示法 具體參見圖6-3,3. 嵌套集合表示法 具體參 見圖6-4 。,4.廣義表表示法 對(duì)圖7-1（c）的樹結(jié)構(gòu)，廣義表表示法可表示為： A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）,6.2 樹的存儲(chǔ)結(jié)構(gòu) 僅考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，有兩種：多重鏈表表示法、二重鏈表表示法 6.2

6、.1 多重鏈表表示法 每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域和若干個(gè)指針域組成，其中，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子。一棵樹中不同結(jié)點(diǎn)的度數(shù)可能不同，每個(gè)結(jié)點(diǎn)設(shè)置的指針域的數(shù)目可能就有所不同。通常有下面的兩種方案： 1、定長(zhǎng)結(jié)點(diǎn)的多重鏈表表示法,取樹的度數(shù)作為每個(gè)結(jié)點(diǎn)的指針域的個(gè)數(shù)。 缺點(diǎn)：,由于樹中多數(shù)結(jié)點(diǎn)的度可能小于樹的度，因而這種方法將會(huì)導(dǎo)致許多結(jié)點(diǎn)的部分指針域?yàn)榭眨斐煽臻g的浪費(fèi)。,2、不定長(zhǎng)結(jié)點(diǎn)的多重鏈表示法 樹中每個(gè)結(jié)點(diǎn)都取自己的度數(shù)作為指針域的個(gè)數(shù)，顯然，對(duì)于葉結(jié)點(diǎn)就不必設(shè)指針域。另外，每個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域、指針域外，還應(yīng)設(shè)一個(gè)度數(shù)域用來(lái)指出該結(jié)點(diǎn)的度數(shù)，即指出該結(jié)點(diǎn)中指針域的個(gè)數(shù)。 6.2.2 二

7、重鏈表表示法 這種方法是對(duì)樹中的每個(gè)結(jié)點(diǎn)設(shè)三個(gè)域：數(shù)據(jù)域和2個(gè)指針域，第一個(gè)指針域給出該結(jié)點(diǎn)的第一個(gè)孩子（即最左邊子樹的根結(jié)點(diǎn)，長(zhǎng)子）的地址，第二個(gè)指針域給出該結(jié)點(diǎn)的右邊第一個(gè)兄弟結(jié)點(diǎn)（次弟）的地址。 樹的三重鏈表表示，增加了一個(gè)指針域即給出該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的地址。,6.3 二叉樹 在樹型結(jié)構(gòu)中，有一類簡(jiǎn)單而又重要的樹，它的每個(gè)結(jié)點(diǎn)最多只有2棵子樹，這種樹被稱為二叉樹。,6.3.1 二叉樹的定義,1二叉樹的定義 和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以遞歸形式給出： 二叉樹是n（n0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵不相交的左子樹和右子樹組成。,二叉樹的特點(diǎn)： 每個(gè)結(jié)

8、點(diǎn)最多有兩個(gè)孩子，或者說(shuō)，在二叉樹中，不存在度大于2的結(jié)點(diǎn) 二叉樹是有序樹（樹為無(wú)序樹），其子樹的順序不能顛倒。因此，二叉樹有五種不同的形態(tài)，參見下圖。,6.3.2 二叉樹的性質(zhì),性質(zhì)1 若二叉樹的層數(shù)從1開始，則二叉樹的第k層結(jié)點(diǎn)數(shù)，最多為個(gè) （k0）。 可以用數(shù)學(xué)歸納法證明之。,性質(zhì)2 深度（高度）為k的二叉樹最大結(jié)點(diǎn)數(shù)為 （k0）,證明： 深度為k的二叉樹，若要求結(jié)點(diǎn)數(shù)最多，則必須每一層的結(jié)點(diǎn)數(shù)都為最多，由性質(zhì)1可知，最大結(jié)點(diǎn)數(shù)應(yīng)為每一層最大結(jié)點(diǎn)數(shù)之和。即為： 20+21+2k-1=2k-1。,2k-1,2k-1,性質(zhì)3 對(duì)任意一棵二叉樹，如果葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，

9、則有n0=n2+1。,證明：設(shè)二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，根據(jù)二叉樹的定義（二叉樹中所有結(jié)點(diǎn)的度均小于或等于2)可知，該二叉樹的結(jié)點(diǎn)總數(shù) n=n0+n1+n2 (1)。 再看二叉樹中的分支數(shù)。除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入。設(shè)B為分支總數(shù)，則 n=B+1 由于這些分支是由度為1或2的結(jié)點(diǎn)射出的，所以又有B=n1+2*n2 于是得：n=n1+2n2+1 (2) 由（1）和（2）得：n0=n2+1,下面討論兩種特殊的二叉樹：滿二叉樹和完全二叉樹。,滿二叉樹 深度為k具有2k-1個(gè)結(jié)點(diǎn)的二叉樹，稱為滿二叉樹?；蛘哒f(shuō)：如果一棵二叉樹中任何結(jié)點(diǎn)，或者是葉結(jié)點(diǎn)，或者是有兩棵非空子樹，且葉子結(jié)點(diǎn)

10、都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。 從定義可知：必須是二叉樹的每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大，否則就不是滿二叉樹。,例：深（高）度為4的滿二叉樹如圖（15個(gè)結(jié)點(diǎn)）,可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，自左而右，由此引出完全二叉樹的定義。,完全二叉樹 如果一棵具有n個(gè)結(jié)點(diǎn)的深度為k的二叉樹，它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)為1 n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。（例：k=3,n=4,5,6）,從滿二叉樹及完全二叉樹定義可以得出如下結(jié)論： 滿二叉樹一定是一棵完全二叉樹 反之完全二叉樹不一定是一棵滿二叉樹。 滿二叉樹的葉子結(jié)點(diǎn)全部在最底層，

11、而完全二叉樹的葉子結(jié)點(diǎn)可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹（8個(gè)結(jié)點(diǎn)）如圖6-6所示。,性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹高度為log2(n)+1 或 log2（n+1） 。 （注意x表示取不大于x（即）的最大整數(shù)，也叫做對(duì)x下取整，x表示取不小于x（即）的最小整數(shù)，也叫做對(duì)x上取整。),1、二叉樹中度為0的結(jié)點(diǎn)數(shù)為50，度為1的結(jié)點(diǎn)數(shù)為30，總結(jié)點(diǎn)數(shù)為_。,湖南大學(xué)考研題,性質(zhì)3：n0=n2+1,2、樹最合適用來(lái)表示_。 A有序數(shù)據(jù)元素 B 無(wú)序數(shù)據(jù)元素 C元素之間無(wú)聯(lián)系的數(shù)據(jù)D元素之間分支層次關(guān)系的數(shù)據(jù),3、對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（ ）【武漢交通科技大學(xué) 一、5

12、 (4分)】 Anlog2n Blog2n Clog2n+1 D不確定 4、深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。 (1 k h)【北京航空航天大學(xué) 一、4（2分）】 Amk-1 Bmk-1 Cmh-1 Dmh-1 5、在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ ）【北京工商大學(xué) 一、3 (3分)】 A2k-1 B2k C2k-1 Dlog2k+1 6、高度為 K的二叉樹最大的結(jié)點(diǎn)數(shù)為（ ）。 【山東大學(xué) 二、3 (1分)】 A2k B2k-1 C2k -1 D2k-1-1,7、若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ） A9 B11 C15 D不確定

13、【北京工商大學(xué)一.7(3分)】,性質(zhì)3 對(duì)任意一棵二叉樹，如果葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有n0=n2+1。,6.3.3 二叉樹的存貯結(jié)構(gòu),1順序存貯結(jié)構(gòu),即用一維數(shù)組TM來(lái)存儲(chǔ)二叉樹的數(shù)據(jù)元素，按照二叉樹的結(jié)點(diǎn)層次編號(hào)依次來(lái)存放。 如：見圖 這種結(jié)構(gòu)適合于存儲(chǔ)完全二叉樹和滿二叉樹，若是一般二叉樹應(yīng)如何處理？,必須按完全二叉樹的形式來(lái)存貯樹中的結(jié)點(diǎn)，這就要虛設(shè)很多空結(jié)點(diǎn)才能使它成為一棵完全二叉樹。如圖可見這將造成空間的浪費(fèi)。,例：k=3的一般二叉樹,對(duì)于一棵二叉樹,若采用順序存貯時(shí),當(dāng)它為完全二叉樹（或滿二叉樹）時(shí),比較方便,若為非完全二叉樹,將會(huì)浪費(fèi)大量存貯存貯單元。 最壞

14、情況的非完全二叉樹是全部只有右分支,設(shè)高度為K,則需占用個(gè) 存貯單元,而實(shí)際只有k個(gè)元素,實(shí)際只需k個(gè)存儲(chǔ)單元。因此，對(duì)于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,2K-1,2二叉鏈表存貯結(jié)構(gòu),（1）二叉鏈表表示 將一個(gè)結(jié)點(diǎn)分成三部分,一部分存放結(jié)點(diǎn)本身信息,另外兩部分為指針,分別存放左、右孩子的地址。,二叉鏈表中一個(gè)結(jié)點(diǎn)可描述為:,對(duì)于圖6-7所示二叉樹,用二叉鏈表形式描述見圖6-8。,（2）二叉鏈表的類型說(shuō)明 二叉鏈表的數(shù)據(jù)類型描述如下: typedef struct btnode int data ; /結(jié)點(diǎn)數(shù)據(jù)類型 struct btnode *lchild, *rchild; /定義

15、左、右孩子為指 針型 bitree; 有時(shí)，為了便于找到結(jié)點(diǎn)中的雙親，還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向雙親的指針域，這種存貯結(jié)構(gòu)稱為三叉鏈表。,6.4 遍歷二叉樹 （二叉樹的運(yùn)算）,所謂遍歷二叉樹，就是遵從某種次序，訪問(wèn)二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。 這里提到的“訪問(wèn)”是指對(duì)結(jié)點(diǎn)施行某種操作，操作可以是輸出結(jié)點(diǎn)信息，修改結(jié)點(diǎn)的數(shù)據(jù)值等，但要求這種訪問(wèn)不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。在本書中，我們規(guī)定訪問(wèn)是輸出結(jié)點(diǎn)信息data，且以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)。 遍歷對(duì)線性結(jié)構(gòu)而言非常簡(jiǎn)單，只需順序掃描每個(gè)數(shù)據(jù)元素即可。但對(duì)非線性結(jié)構(gòu)，要找到一種規(guī)律，以便二叉樹上各結(jié)點(diǎn)能排列成一個(gè)線性序列。

16、,二叉樹由三部分組成：根結(jié)點(diǎn)（D），左子樹（L），右子樹（R）。要遍歷這三個(gè)基本部分，可有六種可能的順序：DLR（先序或前序） DRL（逆先序遍歷） LDR(中序） RDL（逆中序） LRD （后序） RLD（逆后序） 規(guī)定：二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。 DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。,6.4.1先序遍歷 所謂先序遍歷，就是根結(jié)點(diǎn)最先遍歷，其次左子樹，最后右子樹。,遞歸遍歷,先序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結(jié)束;否則 （1

17、）輸出（訪問(wèn)）根結(jié)點(diǎn)； （2）再按先序遍歷方式遍歷根結(jié)點(diǎn)的左子樹; （3）最后按先序遍歷方式遍歷根結(jié)點(diǎn)的右子樹;,遞歸算法如下: void preorder(bitree *root) if(root!=NULL) printf(“%d”,root-data); preorder(root-lchild); preorder (root-rchild); ,6.4.2中序遍歷 所謂中序遍歷，就是根在中間，先左子樹，然后根結(jié)點(diǎn)，最后右子樹。,遞歸遍歷,中序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結(jié)束；否則 中序遍歷左子樹; 輸出根結(jié)點(diǎn); 中序遍歷右子樹。,算法如下: void in

18、order(biteee *root) if (root!=NULL) inorder(root-lchild); printf(“%d”,root-data); inorder(root-rchild); ,6.4.3 后序遍歷 所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結(jié)點(diǎn)。,遞歸遍歷,后序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結(jié)束;否則 （1）后序遍歷左子樹: （2）后序遍歷右子樹; （3）訪問(wèn)根結(jié)點(diǎn)。,算法如下: void postorder( bitree *root) if (root!=NULL) postorder (root-lchild);

19、postorder (root-rchild); printf(“%d”,root-data); ,例如，可以利用上面介紹的遍歷算法，寫出如下圖所示二叉樹的三種遍歷序列為：,先序遍歷序列：ABDGCEFH 中序遍歷序列： BGDAECFH 后序遍歷序列： GDBEHFCA 例題,另外，在編譯原理中，有用二叉樹來(lái)表示一個(gè)算術(shù)表達(dá)式的情形。在一棵二叉樹中，若用操作數(shù)代表樹葉，運(yùn)算符代表非葉子結(jié)點(diǎn)，則這樣的樹可以代表一個(gè)算術(shù)表達(dá)式。 若按前序、中序、后序?qū)υ摱鏄溥M(jìn)行遍歷，則得到的遍歷序列分別稱為前綴表達(dá)式(或稱波蘭式)、中綴表達(dá)式、后綴表達(dá)式(逆波蘭式)。具體參見圖6-12。,右圖所對(duì)應(yīng)的前綴表達(dá)

20、式： -*abc。 右圖所對(duì)應(yīng)的中綴表達(dá)式：a*b-c。 右圖所對(duì)應(yīng)的后綴表達(dá)式：ab*c-。,6.4.4 遍歷二叉樹的非遞歸算法,遞歸算法：簡(jiǎn)明，但效率較低，且有的程序設(shè)計(jì)語(yǔ)言不允許函數(shù)遞歸調(diào)用。 故要討論遍歷二叉樹的非遞歸算法。 均用棧保存遍歷過(guò)程中經(jīng)歷的結(jié)點(diǎn)的左右孩子（指向孩子的指針），用一維數(shù)組SM作為棧存放元素，top為棧頂指針。,1、先序遍歷二叉樹的非遞歸算法 利用一個(gè)一維數(shù)組作為棧，來(lái)存儲(chǔ)二叉鏈表中結(jié)點(diǎn)，,算法思想為： 從二叉樹根結(jié)點(diǎn)開始，先輸出結(jié)點(diǎn)信息，沿左子樹一直走到末端(左孩子為空)為止，在走的過(guò)程中，遇到結(jié)點(diǎn)有右孩子的，則把指向結(jié)點(diǎn)右孩子的指針進(jìn)棧，當(dāng)左子樹為空時(shí)，從棧頂

21、退出一個(gè)指針信息（即退出某結(jié)點(diǎn)的右孩子）。如此重復(fù)，直到棧為空。,void preorder(bitree *root) bitree *p,*s100; int top=0; /top為棧頂指針 p=root; do while(p!=NULL) printf(“%d”,p-data); if(p-rchild!=NULL) stop+=p-rchild; p=p-lchild; if(top=0) p=s-top; while(top=0);,2中序遍歷二叉樹的非遞歸算法,同樣利用一個(gè)一維數(shù)組作棧，來(lái)存貯二叉鏈表中結(jié)點(diǎn)， 算法思想為： 從二叉樹根結(jié)點(diǎn)開始，沿左子樹一直走到末端(左孩子為空)

22、為止，在走的過(guò)程中，把依次遇到的結(jié)點(diǎn)進(jìn)棧,待左子樹為空時(shí),從棧中退出結(jié)點(diǎn)并訪問(wèn),然后再轉(zhuǎn)向它的右子樹。如此重復(fù)，直到?？栈蛑羔槥榭罩?。,算法如下: void inorder ( bitree *root) bitree *p,*s100; /s為一個(gè)棧，top為棧頂指針 int top=0; p=root; do while(p!=NULL) stop +=p;p=p-lchild; if(top=0) p=s-top; printf(“%d”,p-data); p=p-rchild; while(top=0);,6.4.5 遍歷算法應(yīng)用舉例,例1 由二叉樹的前序序列和中序序列建立該二叉樹,分

23、析： 若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。 另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)，因此，可按如下方法建立二叉樹：,1.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn);,2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列(左、右子樹);,3.根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序序列;,4.對(duì)左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。,假設(shè)前序序列為A

24、BDGHCEFI，,中序序列為GDHBAECIF，,則得到的二叉樹如下頁(yè)所示,1。A為根結(jié)點(diǎn),A BDGH CEFI,GDHB A ECIF,2. B為左子樹的根結(jié)點(diǎn),B DGH,GDH B,3. D為左子樹的左子樹的根結(jié)點(diǎn),4。C為右子樹的根結(jié)點(diǎn),5。F為右子樹的右子樹的根結(jié)點(diǎn),C E FI,E C IF,思考：能否根據(jù)中序、后序求前序？能否根據(jù)前序、后序求中序？,例2 按層次遍歷一棵二叉樹,對(duì)于一棵二叉樹，若規(guī)定遍歷順序?yàn)閺纳系较?上層遍歷完才進(jìn)入下層)，從左到右(同一層從左到右進(jìn)行，這樣的遍歷稱為按層次遍歷：例1的樹的層次遍歷序列為：ABCDEFGHI。下面用一個(gè)一維數(shù)組來(lái)模擬隊(duì)列，實(shí)現(xiàn)

25、二叉樹的層次遍歷。,Void lorder (bitree * t) bitree *qmaxsize,*p; / maxsize為最大容量 int f,r; / f,r類似于頭尾指針 q0=t; f=r=0; while (fdata); if(p -lchild!=NULL) r+; qr=p-1child; /入隊(duì) if (p-rchild!=NULL) r+; qr=p-rchild; /入隊(duì) ,作業(yè)： 1、一棵度為2的樹與一棵二叉樹有何區(qū)別？ 2、用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的前序、中序、后序遍歷序列。 3、假設(shè)一棵二叉樹的前序序列為EBAD

26、CFHGIKJ和中序序列為ABCDEFGHIJK，請(qǐng)寫出二叉樹的后序遍歷序列。 4、假設(shè)一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請(qǐng)寫出二叉樹前序遍歷序列。,6.5 二叉排序樹(二叉搜索樹，二叉查找樹） 1什么是二叉排序樹,二叉排序樹（Binary Sorting Tree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹： (1)若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字； (2)若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字； (3)左、右子樹本身又都是一棵二叉排序樹。 下圖各例是否為二叉排序樹？（為了

27、討論問(wèn)題的方便，假設(shè)樹中每個(gè)結(jié)點(diǎn)的值是一個(gè)十進(jìn)制整數(shù)）,2、下面給出構(gòu)造二叉排序樹的算法： 將一個(gè)給定的數(shù)據(jù)元素構(gòu)造為相應(yīng)的二叉排序樹，通常采用逐步插入結(jié)點(diǎn)的方法來(lái)構(gòu)造二叉排序樹。 設(shè)k=k1,k2,.,kn為數(shù)據(jù)元素序列，從k1開始依次取序列中的元素，每取出一個(gè)元素ki,按下列原則建立二叉排序樹的一個(gè)新結(jié)點(diǎn)： （1）若二叉排序樹為空，則新的數(shù)據(jù)元素就是二叉排序樹的根結(jié)點(diǎn)。 （2）若二叉排序樹非空，則將新的數(shù)據(jù)元素與該二叉樹的根結(jié)點(diǎn)的值進(jìn)行比較，若小于根結(jié)點(diǎn)的值，則將新的數(shù)據(jù)元素插入到根結(jié)點(diǎn)的左子樹中；否則，插入到右子樹中。 這個(gè)過(guò)程是一個(gè)遞歸的過(guò)程，因?yàn)閿?shù)據(jù)元素插入到左子樹或右子樹也同樣是按

28、這個(gè)原則遞歸進(jìn)行的。（例）,例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過(guò)程如下圖所示。,（注：排列順序不一樣，得到的二叉排序樹也不一樣）,二叉排序樹與關(guān)鍵字排列順序有關(guān)嗎?,a、遞歸算法 bitree *Inserttree(bitree *t, int x) if(t=NULL) t=( bitree *)malloc(sizeof(bitree); t-data=x; t-lchild=NULL; t-rchild=NULL; else,若二叉排序樹為空，則新的數(shù)據(jù)元素就是二叉排序樹的根結(jié)點(diǎn)。,if(xdata) t-lchild=In

29、serttree(t-lchild,x); else t-rchild=Inserttree(t-rchild,x); return(t); b、生成二叉排序樹的非遞歸算法： bitree *creat(bitree *t) bitree *s,*p,*q; int x;,若二叉排序樹非空，則將新的數(shù)據(jù)元素與該二叉樹的根結(jié)點(diǎn)的值進(jìn)行比較，若小于根結(jié)點(diǎn)的值，則將新的數(shù)據(jù)元素插入到根結(jié)點(diǎn)的左子樹中；否則，插入到右子樹中。,scanf(“%d”,while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lch

30、ild=s; else q-rchild=s; /插入結(jié)點(diǎn)算法,scanf(“%d”, ,3、二叉排序 樹上的查找(檢索算法）,（1）二叉排序 樹的查找思想 若二叉排樹為空，則查找 失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹的葉子結(jié)點(diǎn)時(shí)，還沒(méi)有找到待找結(jié)點(diǎn)，則查找不成功。 （2）二叉排序樹查找的算法實(shí)現(xiàn),a、遞歸算法：,bitree *bstsrch(bitree *t,int k) if(t=NULL)|(t-data=k) return(t); else if(t-da

31、ta rchild,k); else return(bstsrch(t-lchild,k); ,b、非遞歸算法,bitree *search(bitree *t,int k) while(t!=NULL) if(t-data=k) return(t); else if(t-datarchild; else t=t-lchild; return(NULL); ,4、刪除運(yùn)算 在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)需注意：要保證刪除后所得的二叉樹仍是一棵二叉檢索樹?？紤]下面三種情況： 1）若要?jiǎng)h除的是葉子結(jié)點(diǎn) 最簡(jiǎn)單的一種，只要將其雙親結(jié)點(diǎn)與它之間的鏈接的指針置空即可。如圖 2）若要?jiǎng)h除的結(jié)點(diǎn)只有左子樹或只有

32、右子樹，即單支結(jié)點(diǎn)。 a、若被刪除的結(jié)點(diǎn)沒(méi)有左子樹，則可用其右子樹的根結(jié)點(diǎn)取代被刪除結(jié)點(diǎn)的位置。 b、若被刪除結(jié)點(diǎn)沒(méi)有右子樹，則可用其左子樹的根結(jié)點(diǎn)取代被刪除結(jié)點(diǎn)的位置。,3）若刪除的結(jié)點(diǎn)具有左、右子樹。,方法：首先將該結(jié)點(diǎn)的中序前趨結(jié)點(diǎn)的值賦給該結(jié)點(diǎn)的值，然后再刪除它的中序前趨結(jié)點(diǎn)。由于此時(shí)，它的中序前趨結(jié)點(diǎn)的右指針為空，只要將中序前趨結(jié)點(diǎn)的左指針鏈接到中序前趨結(jié)點(diǎn)所在的鏈接位置即可。,5二叉排序樹查找的性能分析,在二叉排序樹查找中，成功的查找次數(shù)不會(huì)超過(guò)二叉樹的深度，而具有n個(gè)結(jié)點(diǎn)的二叉排序樹的深度，最好為 log2（n+1） ，最壞為n。因此，二叉排序樹查找的最好時(shí)間復(fù)雜度為O(log2

33、n)，最壞的時(shí)間復(fù)雜度為O(n)，一般情形下，其時(shí)間復(fù)雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。 即使關(guān)鍵字相同的一組數(shù)據(jù)，若先后插入的次序不同，所生成的二叉排序樹也不同，則查找的時(shí)間性能也不同，當(dāng)要求查找的性能較高時(shí)，要對(duì)構(gòu)成二叉排序樹的過(guò)程進(jìn)行“平衡化”處理，形成二叉平衡樹。,6.6 平衡二叉樹 1平衡二叉樹的概念,平衡二叉樹(balanced binary tree)是由阿德爾森一維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。,平衡二叉樹: 若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的深度之差的絕對(duì)值

34、不超過(guò)1，則稱這樣的二叉樹為平衡二叉樹。 平衡因子：將該結(jié)點(diǎn)的左子樹深度減去右子樹深度的值，稱為該結(jié)點(diǎn)的平衡因子(balance factor)。 也就是說(shuō)，一棵二叉排序樹中，所有結(jié)點(diǎn)的平衡因子只能為0、1、-1時(shí)，則該二叉排序樹就是一棵平衡二叉樹，,2. 非平衡二叉樹的平衡處理,若一棵二叉排序樹是平衡二叉樹，扦入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹，這時(shí)，就可以對(duì)該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。 處理的原則應(yīng)該是處理與扦入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡處理。,（1）LL型 的處理(左左型) 如圖7-10所示，在C的左孩子B上扦入一個(gè)左孩子結(jié)

35、點(diǎn)A，使C的平衡因子由1變成了2，成為不平衡的二叉樹序樹。這時(shí)的平衡處理為：將C順時(shí)針旋轉(zhuǎn)，成為B的右子樹，而原來(lái)B的右子樹則變成C的左子樹，待扦入結(jié)點(diǎn)A作為B的左子樹。(注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子),（2）LR型的處理(左右型) 如圖7-11所示，在C的左孩子A上扦入一個(gè)右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C 之間，使之成為L(zhǎng)L型，然后按第(1)種情形LL型處理。,（3）RR型的處理(右右型) 如圖7-12所示，在A的右孩子B上扦入一個(gè)右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時(shí)的平衡處理為：

36、將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹，而原來(lái)B的左子樹則變成A的右子樹，待扦入結(jié)點(diǎn)C成為B的右子樹。,（4）RL型的處理(右左型) 如圖7-13所示，在A的右孩子C上扦入一個(gè)左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時(shí)的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3) 種情形RR型處理。,例1，給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹。 分析：平衡二叉樹實(shí)際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過(guò)程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過(guò)程見圖7-14。,例2：給定一個(gè)關(guān)鍵

37、字序列13，24，37，90，53，試生成一棵平衡二叉樹。 作業(yè)：將一組關(guān)鍵字（47,16,21,36,29,59,19,54)生成一二叉平衡樹。,3平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹的最好時(shí)間復(fù)雜相同，都為O(log2n)。 一般二叉平衡樹主要應(yīng)用于查找。,例3，對(duì)例1給定的關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數(shù)及成功的平均查找長(zhǎng)度。 分析：由于關(guān)鍵字序列的順序己經(jīng)確定

38、，故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見圖7-14，得到的二叉排序樹見圖7-15。,從圖7-15的二叉排序樹可知，查找6需4次，假設(shè)7個(gè)記錄的查找概率相等，為1/7，則該二叉排序樹的平均查找長(zhǎng)度為 ASL=(1+2+2+3+3+3+4)/7=18/72.57。 從圖7-16的平衡二叉樹可知，查找6需2次，平均查找長(zhǎng)度 ASL=(1+2+2+3+3+3+3)/7=17/72.43。,從結(jié)果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。,#includeh1.h #include #include bitree *creat(bitree *t) bitree *s,*p,*q;

39、 int x; printf(input the nodes value:0-ENDn); scanf(%d, ,if(s-datadata) q-lchild=s; else q-rchild=s; printf(input the nodes value:n); scanf(%d, ,湖南大學(xué)01-03,1、樹最合適用來(lái)表示_。 A有序數(shù)據(jù)元素 B 無(wú)序數(shù)據(jù)元素 C元素之間無(wú)聯(lián)系的數(shù)據(jù)D元素之間分支層次關(guān)系的數(shù)據(jù) 2、中序遍歷二叉排序樹就可以得到排好序的結(jié)點(diǎn)序列。（ ）（判斷正誤）,一維數(shù)組存放一棵完全二叉樹: ABCDEFGHIJK，請(qǐng)給出該二叉樹的后序遍歷序列。 算法設(shè)計(jì)題略,1、在二

40、叉排序樹上成功地找到一個(gè)結(jié)點(diǎn)，在平均情況下的時(shí)間復(fù)雜性是 , 在最壞情況下的時(shí)間復(fù)雜性是 。設(shè)結(jié)點(diǎn)個(gè)數(shù)為 n，以大O形式給出時(shí)間復(fù)雜性。 2、已知一棵二叉樹是以二叉鏈表的形式存儲(chǔ)的，其結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下：（本題10 分。） struct node int data; / 結(jié)點(diǎn)的數(shù)據(jù)場(chǎng)。 struct node *left; / 給出結(jié)點(diǎn)的左兒子的地址。 struct node * right; / 給出結(jié)點(diǎn)的右兒子的地址。 ； 請(qǐng)?jiān)?、2二題的 處進(jìn)行填空，完成題目要求的功能。注意，每空只能填一個(gè)語(yǔ)句，多填為 0 分。 (1) 求出以T 為根的二叉樹或子樹的結(jié)點(diǎn)個(gè)數(shù)。 int size (str

41、uct node * T ) if ( ) return 0; else ; (2) 求出以T為根的二叉樹或子樹的高度。注：高度定義為樹的總的層次數(shù)。 int height(struct node * T ) if ( T = NULL ) ; else ; ,上海交通大學(xué)2004年數(shù)據(jù)結(jié)構(gòu)考研試題,提示： 用遞歸形式,O(log2n) O(n) T = NULL return ( 1 +size(T-left) + size(T-right) ) return 0 return 1 +( ( height(T-left) height(T-right)? height(T-left): he

42、ight(T-right) ),6.7線索二叉樹 6.7.1 線索的概念,遍歷二叉樹：就是將樹中所有結(jié)點(diǎn)排成一個(gè)線性序列。好處：在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。,帶來(lái)麻煩，希望不進(jìn)行遍歷就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼記錄下來(lái)。 為了做到這一點(diǎn)，可以在原來(lái)的二叉鏈表結(jié)點(diǎn)中，再增加兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后繼，但這樣做將會(huì)浪費(fèi)大量存貯單元，存貯空間的利用率相當(dāng)?shù)?一個(gè)結(jié)點(diǎn)中有4個(gè)指針，1個(gè)指左孩子，1個(gè)指右孩子，1個(gè)指前驅(qū)，1個(gè)指后繼)，而原來(lái)的左、右孩子域有許多空指針又沒(méi)有利用起來(lái)。,為了

43、不浪費(fèi)存貯空間，我們利用原有的孩子指針為空時(shí)來(lái)存放直接前驅(qū)和后繼，這樣的指針?lè)Q為“線索”（thread)，加線索的過(guò)程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對(duì)應(yīng)的二叉鏈表稱為線索二叉鏈表（簡(jiǎn)稱為線索鏈表）。 在線索二叉樹中，由于有了線索，無(wú)需遍歷二叉樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。 但是，我們?cè)鯓觼?lái)區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢?為此，在二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域ltag、rtag。,ltag和rtag定義如下：,0 lchild域指向結(jié)點(diǎn)的左孩子 ltag= 1 lchild域指向結(jié)點(diǎn)在某種遍歷下的直 接前驅(qū),0 rch

44、ild域指向結(jié)點(diǎn)的右孩子 rtag= 1 rchild域指向結(jié)點(diǎn)在某種遍歷下的直接后繼,這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有5個(gè)域，但其中只有2個(gè)指針，較原來(lái)的4個(gè)指針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)可描述如下：,2線索的分類,另外，根據(jù)遍歷的不同要求，線索二叉樹可以分為： （1）前序前驅(qū)線索二叉樹(只需畫出前驅(qū)) （2）前序后繼線索二叉樹(只需畫出后繼),（3）前序線索二叉樹(前驅(qū)和后繼都要標(biāo)出) （4）中序前驅(qū)線索二叉樹(只需畫出前驅(qū)) （5）中序后繼線索二叉樹(只需畫出中序后繼) （6）中序線索二叉樹(中序前驅(qū)和后繼都要標(biāo)出) （8）后序前驅(qū)線索二叉樹(只需畫出后序前驅(qū)) （8）后序后繼線

45、索二叉樹(中需畫出后序后驅(qū)) （9）后序線索二叉樹(前驅(qū)和后繼都要標(biāo)出),6.7.2線索的描述,1結(jié)點(diǎn)數(shù)據(jù)類型描述,typedef struct bithrnode int data; int ltag ,rtag; /左、右標(biāo)志域 struct bithrnode *lchild, *rchild; binode ;,2線索的畫法,在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的直接后繼，左右孩子不為空時(shí)，不需畫前驅(qū)和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。,前序序列為：ABCD,中序序列為：BADC,后序序列為：BDCA,仿線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹的線

46、索鏈表上添加一個(gè)頭結(jié)點(diǎn)，其中l(wèi)child指向根結(jié)點(diǎn)，rchild指向自己，并且原先指向空的線索均指向該頭結(jié)點(diǎn)。如此處理，使得在線索二叉樹中查找某結(jié)點(diǎn)的前趨、后繼結(jié)點(diǎn)的算法中不必再判斷線索是否為空的情況。,6.8 樹和森林 6.8.1 樹、森林和二叉樹的轉(zhuǎn)換 1樹轉(zhuǎn)換成二叉樹,可以分為三步： （1） 連線 指相鄰兄弟之間連線，加一虛線。,（2） 抹線 指抹掉雙親與除最左孩子外其它孩子之間的連線。,（3） 旋轉(zhuǎn) 只需將樹作適當(dāng)?shù)男D(zhuǎn)，具體：將圖形上原有的實(shí)線均向左斜，加上的虛線均向右斜，且變成實(shí)線，調(diào)整成二叉樹的樹型結(jié)構(gòu)。,具體實(shí)現(xiàn)過(guò)程見圖7-20。,由轉(zhuǎn)換可知：在二叉樹中，左分支上的各結(jié)點(diǎn)在原來(lái)

47、的樹中是父子關(guān)系，而右分支上的各結(jié)點(diǎn)在原來(lái)的樹中是兄弟關(guān)系。,由于根結(jié)點(diǎn)沒(méi)有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)的右孩子必為空,2森林轉(zhuǎn)換成二叉樹,（1）將森林中每一棵樹分別轉(zhuǎn)換成二叉樹 這在剛才的樹轉(zhuǎn)換成二叉樹中已經(jīng)介紹過(guò)。,（2）合并 使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到第n-2 棵的右邊并成為它的右子樹，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。,3二叉樹還原成樹,與樹轉(zhuǎn)換成二叉樹的步驟剛好相反： a. 加線：若某節(jié)點(diǎn)I是雙親節(jié)點(diǎn)的左孩子，則將該節(jié)點(diǎn)的右孩子及沿著此右孩子的右鏈不斷搜索到的所有右孩子，都分別與節(jié)點(diǎn)I的雙

48、親節(jié)點(diǎn)用虛線連接起來(lái)。 b. 抹線：抹掉原二叉樹中所有雙親節(jié)點(diǎn)與右孩子的連線。 c. 旋轉(zhuǎn)：將樹中虛線均變?yōu)閷?shí)線，并按層次排好。,A,B,E,C,D,F,A,B,C,D,E,F,調(diào)整后,A,B,C,D,E,F,4. 二叉樹還原成森林,(1) 右鏈斷開（即抹線） 將二叉樹的根結(jié)點(diǎn)的右鏈及右鏈的右鏈等全部斷開，得到若干棵無(wú)右子樹的二叉樹。 具體操作見圖7-21(b)。 （2）二叉樹還原成樹,具體操作步驟見圖7-21(c)。,6.8.2 樹和森林的遍歷,在樹和森林中，一個(gè)結(jié)點(diǎn)可能有兩棵以上的子樹，因而不便討論它們的中序遍歷。故樹和森林的遍歷通常有兩種方式，先序遍歷和后序遍歷。 下面分別討論：,（1）

49、樹的先序遍歷 若樹非空，則先訪問(wèn)根結(jié)點(diǎn)，然后按照從左到右的順序先序遍歷各子樹。 例： （2）樹的后序遍歷 若樹非空，則依次后序遍歷各子樹，最后訪問(wèn)根結(jié)點(diǎn)。 例： 樹的先序遍歷與其轉(zhuǎn)換的相應(yīng)的二叉樹的先序遍歷的結(jié)果序列相同；后序遍歷與相應(yīng)二叉樹的中序序列相同。,（2）森林的后序遍歷 按順序后序遍歷森林中的每一棵樹。,同樣，森林的先序遍歷等價(jià)于它轉(zhuǎn)換成的二叉樹的先序遍歷，森林的后序遍歷等價(jià)于它轉(zhuǎn)換成的二叉樹的中序遍歷。,森林的遍歷有兩種方式：先序遍歷和后序遍歷。 （1）先序遍歷 若森林非空，則先訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。,

50、6.9 二叉樹的應(yīng)用 哈夫曼樹 (Huffman),6.9.1基本術(shù)語(yǔ),1路徑、路徑長(zhǎng)度、樹的路徑長(zhǎng)度 路徑：在一棵樹中，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分 支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。 路徑長(zhǎng)度：路徑上分支的數(shù)目?；蚵窂缴线叺臄?shù)目。 樹的路徑長(zhǎng)度：是從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。一般記為PL。,哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑最短的樹，有廣泛的應(yīng)用。,2結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度、樹的帶權(quán)路徑長(zhǎng)度 結(jié)點(diǎn)的權(quán)：在許多應(yīng)用中，常將樹中結(jié)點(diǎn)賦上一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 樹的帶權(quán)路徑長(zhǎng)度：是樹中的所有

51、葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。與樹的路徑長(zhǎng)度區(qū)別 通常記作 wpl= ，其中n 為葉子結(jié)點(diǎn)數(shù)目，wi為第i 個(gè) 葉子結(jié)點(diǎn)的權(quán)值，li 為第i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度，即根到第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。,7.9.2 哈夫曼樹構(gòu)造,1哈夫曼樹的定義 在一棵二叉樹中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。因?yàn)闃?gòu)造這種樹的算法最早由哈夫曼于1952年提出，故稱為哈夫曼樹。,例如，給定葉子結(jié)點(diǎn)的權(quán)分別為1,3,5,8，則可以得到如圖7-22所示的不同二叉樹。 從圖7-22可知，圖7-22 (b)的長(zhǎng)度最短，圖7-22 (c)為較差情形，當(dāng)然讀者還可以自已構(gòu)造出具有不同的wpl情形來(lái)。,從上可見，滿二叉樹不一定是最優(yōu)二叉樹。 2哈夫曼樹的構(gòu)造 即哈夫曼算法 假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1,w2,wn,則哈夫曼樹的構(gòu)造規(guī)則為：,將給定的一組權(quán)值w1,w2,wn生成有n 棵樹的森林F=T1，T2，T3，.Tn；(每棵樹僅有一個(gè)結(jié)點(diǎn)) (2) 在森林F中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹作為一棵