第6章樹和二叉樹

1、第6章 樹和二叉樹 第第6章章 樹和二叉樹樹和二叉樹 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 二叉樹的定義二叉樹的定義 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.4 樹、森林樹、森林 6.6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用 6.7 樹的計(jì)數(shù)樹的計(jì)數(shù)第6章 樹和二叉樹 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 樹是n（n0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n0時(shí)，該集合滿足如下條件： (1) 其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，

2、Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 第6章 樹和二叉樹 圖6.1 樹的圖示方法EFBAGKLMHIJCD第6章 樹和二叉樹 ADT Tree 數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性。 數(shù)據(jù)關(guān)系R： 若D為空集，則為空樹。若D中僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān)系： (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒有前驅(qū)。 (2)若D- root ，則存在D- root 的一個(gè)劃分D1，D2Dm ( m0 ) 對(duì)任意jk ( 1j, km ) 有DjDk=,且對(duì)任

3、意的i( 1im ) 唯一存在數(shù)據(jù)元素 xiH. (3)對(duì)應(yīng)于D- root 的劃分，H- , 有唯一的一個(gè)劃分H1，H2，,Hm ( m0 ), 對(duì)任意jk ( 1j, km )有HjHk=,且對(duì)任意i(1im ) ,H1是Di上的二元關(guān)系，(Di, Hi )是一棵符合本定義的樹，成為根root的子樹。 第6章 樹和二叉樹 樹的基本術(shù)語 結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的分支信息。 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。 葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。 分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。 孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。在圖

4、6.1中， B、C是A的孩子。 雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。在圖6.1中，A 是B、C的雙親。 兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)H、I、 J互為兄弟結(jié)點(diǎn)。 第6章 樹和二叉樹 堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。 祖先結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)K的祖先是A、B、E。 子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫 。在圖6.1中，結(jié)點(diǎn)D的子孫是H、I、 J、 M。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。 樹的度： 樹中所有結(jié)

5、點(diǎn)的度的最大值。 樹的高度（深度）： 樹中所有結(jié)點(diǎn)的層次的最大值。 有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。否則稱為無序樹 。 森林：m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹。 第6章 樹和二叉樹 6.2 二叉樹的定義二叉樹的定義 6.2.1 二叉樹的定義二叉樹的定義 定義：我們把滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹二叉樹（Binary Tree）： （1） 每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即度都不大于2）； （2）二叉樹的子樹有左右之分，其次序不能任意顛倒。 由此定義可以看出，一個(gè)二叉樹

6、中的每個(gè)結(jié)點(diǎn)只能含有0、 1或2個(gè)孩子，而且每個(gè)孩子有左右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。 第6章 樹和二叉樹 圖6.2 二叉樹的五種基本形態(tài)。 (a) 空二叉樹(b) 只有根結(jié)點(diǎn) 的二叉樹(c) 只有左子樹 的二叉樹(d) 左右子樹均非 空的二叉樹(e) 只有右子樹的二叉樹第6章 樹和二叉樹 與樹的基本操作類似，二叉樹有如下基本操作： (1) InitBiTree（&T）; 操作結(jié)果：構(gòu)造空二叉樹。 (2) DestoryBitree（&T）; 初始條件：二叉樹T存在。 操作結(jié)果：銷毀二叉樹T。 (3) GreateBiTree（&T,

7、definition）; 初始條件：definition給出二叉樹T的定義。 操作結(jié)果：按definition構(gòu)造二叉樹T。 (4) ClearBiTree（&T）; 初始條件：二叉樹T存在。 操作結(jié)果：將二叉樹T清為空樹。第6章 樹和二叉樹 (5) BiTreeEmpty（T）; 初始條件：二叉樹T存在。 操作結(jié)果：若T為空二叉樹，則返回TRUE，否則FLASE。 (6) BiTreeDepth（T）; 初始條件：二叉樹T存在。 操作結(jié)果：返回T的深度。 (7) Root（T）； 初始條件：二叉樹T存在。 操作結(jié)果：返回T的根。 (8) Value(T,e); 初始條件：二叉樹T存在

8、，e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：返回e的值。第6章 樹和二叉樹 (9) Assign（T，&e,value）; 初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：結(jié)點(diǎn)e賦值為value。 (10) Parent（T，e）； 初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。 操作節(jié)點(diǎn)：返回e的右孩子。若e無左孩子，則返回“空”； (11) LeftChild（T，e）; 初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：返回e的左孩子。若e無左孩子，則返回“空”。 (12) RightChild（T，e）; 初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：返回e 的右孩子。 第6

9、章 樹和二叉樹 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 性質(zhì)性質(zhì)1: 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 證明：證明： 用數(shù)學(xué)歸納法。 歸納基礎(chǔ)：當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。 歸納假設(shè)：假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。 現(xiàn)證明當(dāng)i=k+1時(shí)， 結(jié)論成立： 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。 第6章 樹和二叉樹 性質(zhì)性質(zhì)2: 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k1）。 證明證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大

10、值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為 kikikii111122層上的最大結(jié)點(diǎn)個(gè)數(shù)第故結(jié)論成立。 第6章 樹和二叉樹 性質(zhì)性質(zhì)3: 對(duì)任意一棵二叉樹T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)。因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度小于等于2，所以有n=n0+n1+n2 設(shè)二叉樹中分支數(shù)目為B，因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n=B+1第6章 樹和二叉樹 又因?yàn)槎鏄渲械姆种Ф际怯啥葹?和度為2的結(jié)點(diǎn)發(fā)出， 所以分支數(shù)目為B=n1+2n2 整理上述兩式可得到 n=

11、B+1=n1+2n2+1 將n=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故結(jié)論成立。 第6章 樹和二叉樹 滿二叉樹：滿二叉樹： 深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。圖6.3(a)所示的二叉樹，即為一棵滿二叉樹。 滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進(jìn)行編號(hào)（1， 2， ， n）。第6章 樹和二叉樹 完全二叉樹：完全二叉樹： 深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1n的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹， 如圖6.3(

12、b)所示。 滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。 完全二叉樹的特點(diǎn)： 葉子只能在層次最大的兩層上出現(xiàn)； 對(duì)任意一個(gè)結(jié)點(diǎn)，右分支下的子孫的最大層次為L，則左分支為L或L+1 。第6章 樹和二叉樹 圖6.3 滿二叉樹與完全二叉樹 8910111213452136714158910111213452136714(a) 滿二叉樹(b) 完全二叉樹第6章 樹和二叉樹 性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。 證明：假設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點(diǎn)總數(shù)為n1=2k-1-1 k層滿二叉樹的結(jié)點(diǎn)總數(shù)為n2=2k-1 顯然有n1n

13、n2，進(jìn)一步可以推出n1+1nn2+1。 將n1=2k-1-1和n2=2k-1代入上式，可得2k-1n2k，即 k-1log2n1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為i/2。 （2） 如2in，則序號(hào)為i的結(jié)點(diǎn)無左孩子；如2in，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i。 （3）如2i1n，則序號(hào)為i的結(jié)點(diǎn)無右孩子；如2i1n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i1。 第6章 樹和二叉樹 可以用歸納法證明其中的（2）和（3）： 當(dāng)i=1時(shí)，由完全二叉樹的定義知，如果2i=2n，說明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以其左孩子存在且序號(hào)為2；反之，如果2n，說明二叉樹中不存在序號(hào)為2的結(jié)點(diǎn)，

14、其左孩子不存在。同理，如果2i+1=3n，說明其右孩子存在且序號(hào)為3；如果3n，則二叉樹中不存在序號(hào)為3的結(jié)點(diǎn)，其右孩子不存在。 假設(shè)對(duì)于序號(hào)為j(1ji)的結(jié)點(diǎn)，當(dāng)2jn時(shí)，其左孩子存在且序號(hào)為2j，當(dāng)2jn 時(shí)，其左孩子不存在；當(dāng)2j+1n時(shí)，其右孩子存在且序號(hào)為2j+1，當(dāng)2j+1n時(shí)，其右孩子不存在。 第6章 樹和二叉樹 當(dāng)i=j+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子存在， 則其左孩子結(jié)點(diǎn)的序號(hào)一定等于序號(hào)為j的結(jié)點(diǎn)的右孩子的序號(hào)加1，即其左孩子結(jié)點(diǎn)的序號(hào)等于（2j+1）+1=2（j+1）=2i，且有2in；如果2in，則左孩子不存在。若右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的序號(hào)應(yīng)等于其左

15、孩子結(jié)點(diǎn)的序號(hào)加1，即右孩子結(jié)點(diǎn)的序號(hào)為2i+1，且有2i+1n；如果2i+1n，則右孩子不存在。 故（2）和（3）得證。 第6章 樹和二叉樹 由（2）和（3）我們可以很容易證明（1）。 當(dāng)i=1時(shí)，顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。當(dāng)i1時(shí)，設(shè)序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為m，如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，根據(jù)（2）有i=2m，即m=i/2; 如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，根據(jù)（3）有i=2m+1，即m=（i-1）/2=i/2-1/2，綜合這兩種情況，可以得到，當(dāng)i1時(shí)，其雙親結(jié)點(diǎn)的序號(hào)等于i/2。證畢。 第6章 樹和二叉樹 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)

16、二叉樹的結(jié)構(gòu)是非線性的， 每一結(jié)點(diǎn)最多可有兩個(gè)后繼。 二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種： 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元，依次自上而下、自左至右存用一組地址連續(xù)的存儲(chǔ)單元，依次自上而下、自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為i 的的結(jié)點(diǎn)元素存儲(chǔ)在數(shù)組的第結(jié)點(diǎn)元素存儲(chǔ)在數(shù)組的第i 1個(gè)分量中。個(gè)分量中。 圖6.4 二叉樹與順序存儲(chǔ)結(jié)構(gòu) 第6章 樹和二叉樹 圖6.5 單支二叉樹與其順序存儲(chǔ)結(jié)構(gòu) ABCD(a) 單支二叉樹ABCD(b) 順序存儲(chǔ)結(jié)構(gòu)第6章 樹和二叉樹 2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱?/p>

17、儲(chǔ)結(jié)構(gòu) 對(duì)于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、 左孩子域和右孩子： LChildDataRChild其中，LChild域指向該結(jié)點(diǎn)的左孩子，Data域記錄該結(jié)點(diǎn)的信息，RChild域指向該結(jié)點(diǎn)的右孩子。 第6章 樹和二叉樹 用C語言可以這樣聲明二叉樹的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)： typedef struct BiTNodeTElemType data; struct BiTNode *LChild; struct BiTNode *RChild; BiTNode, *BiTree; 有時(shí)，為了便于找到父結(jié)點(diǎn)，可以增加一個(gè)Parent域，

18、Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。該結(jié)點(diǎn)結(jié)構(gòu)如下： LChildDataparentRChild第6章 樹和二叉樹 圖6.6 二叉樹和二叉鏈表 BCDGEFADEFCBGA(a) 二叉樹T(b) 二叉樹 T 的二叉鏈表第6章 樹和二叉樹 若一個(gè)二叉樹含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n1個(gè)空的鏈域。此結(jié)論證明如下： 證明：分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。 不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹的操作也不同。如要找某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，在三叉鏈表中很容易實(shí)現(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找?？梢姡诰唧w應(yīng)用中，需要根據(jù)二叉樹的形態(tài)和需

19、要進(jìn)行的操作來決定二叉樹的存儲(chǔ)結(jié)構(gòu)。 第6章 樹和二叉樹 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.3.1 二叉樹的遍歷二叉樹的遍歷 圖6.7 二叉樹結(jié)點(diǎn)的基本結(jié)構(gòu) LChildDataRChildLChildRChildData第6章 樹和二叉樹 遍歷二叉樹：按某種搜索路徑，使二叉樹每個(gè)結(jié)點(diǎn)均被訪問一次，且僅被訪問一次。 訪問的含義很廣。 遍歷需尋找某中規(guī)律，使二叉樹的結(jié)點(diǎn)能排列在一個(gè)線形隊(duì)列上 。 我們用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、 遍歷右子樹， 那么對(duì)二叉樹的遍歷順序就可以有六種方式： (1) 訪問根，遍歷左子樹，遍歷右子樹（記做DLR）。 (2) 訪問根，遍歷

20、右子樹，遍歷左子樹（記做DRL）。 (3) 遍歷左子樹，訪問根，遍歷右子樹（記做LDR）。 (4) 遍歷左子樹，遍歷右子樹，訪問根（記做LRD）。 (5) 遍歷右子樹，訪問根，遍歷左子樹（記做RDL）。 (6) 遍歷右子樹，遍歷左子樹，訪問根（記做RLD）。 第6章 樹和二叉樹 注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進(jìn)行遍歷。 下面就分別介紹三種遍歷方法的遞歸定義。 先序遍歷（DLR）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作 (1) 訪問根結(jié)點(diǎn)； (2) 按先序遍歷左子樹； (3) 按先序遍歷右子樹。 第6章 樹和二叉樹 中序遍歷（LDR）操作過程

21、： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作： (1) 按中序遍歷左子樹； (2) 訪問根結(jié)點(diǎn)； (3) 按中序遍歷右子樹。 后序遍歷（LRD）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作： (1) 按后序遍歷左子樹； (2) 按后序遍歷右子樹； (3) 訪問根結(jié)點(diǎn)。 第6章 樹和二叉樹 對(duì)于如圖6.8所示的二叉樹，其先序、中序、后序遍歷的序列如下： 先序遍歷： A、 B、 D、 F、 G、 C、 E、 H 。 中序遍歷： B、 F、 D、 G、 A、 C、 E、 H 。 后序遍歷： F、 G、 D、 B、 H、 E、 C、 A 。 圖6.8 二叉樹 CEHGFBDA第

22、6章 樹和二叉樹 最早提出遍歷問題是對(duì)存儲(chǔ)在計(jì)算機(jī)中的表達(dá)式求值。例如：（a+b*c）-d/e。該表達(dá)式用二叉樹表示如圖6.9所示。當(dāng)我們對(duì)此二叉樹進(jìn)行先序、中序、后序遍歷時(shí)，便可獲得表達(dá)式的前綴、中綴、后綴書寫形式： 前綴： -+a*bc/de 中綴： a+b*c-d/e 后綴： abc*+de/- 其中中綴形式是算術(shù)表達(dá)式的通常形式，只是沒有括號(hào)。 前綴表達(dá)式稱為波蘭表達(dá)式。算術(shù)表達(dá)式的后綴表達(dá)式被稱作逆波蘭表達(dá)式。 在計(jì)算機(jī)內(nèi)，使用后綴表達(dá)式易于求值。 第6章 樹和二叉樹 圖6.9 算術(shù)式的二叉樹表示 /edcb*a第6章 樹和二叉樹 1） 先序遍歷先序遍歷 Status PreOrde

23、rTraverse ( Bitree T, Status ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( Visit ( T-data ) )5 if ( PreOrderTraverse ( T-lchild , Visit ) ) 6 if ( PreOrderTraverse ( T-rchild, Visit ) ) return OK;7 return ERROR;8 9 else return OK;10 第6章 樹和二叉樹 2） 中序遍歷中序遍歷 Status InOrderTraverse ( Bitree T, Status

24、 ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( InOrderTraverse ( T-lchild , Visit ) )5 if ( Visit ( T-data ) )6 if ( InOrderTraverse ( T-rchild, Visit ) ) return OK;7 return ERROR;8 9 else return OK;10 第6章 樹和二叉樹 圖6.10 中序遍歷二叉樹的遞歸過程 ABDCE(a) 二叉樹的遍歷走向BD第一次經(jīng)過第二次經(jīng)過第三次經(jīng)過(b) 遍歷中三次經(jīng)過結(jié)點(diǎn)的情形第6章 樹和二叉樹 基于棧的遞

25、歸消除基于棧的遞歸消除 依棧的狀態(tài)變化，可直接寫出相應(yīng)的非遞歸算法，棧元素包含兩項(xiàng)，遞歸調(diào)用語句編號(hào)（返回地址），指向根結(jié)點(diǎn)的指針。若棧頂記錄中指針值為空，則應(yīng)退至上一層，若從左子樹返回，應(yīng)退到指針?biāo)傅母Ｈ羰菑挠易訕浞祷?，表明本層的遍歷結(jié)束，應(yīng)繼續(xù)退棧。 第6章 樹和二叉樹 Status InOrderTraverse( BiTree T, Status ( * Visit ) ( TelemType e ) ) InitStack ( S ); Push ( S, T ); While( !StackEmpty ( S ) ) while ( GetTop ( S, p ) &p

26、) Push ( S, p-lchild ); Pop ( S, p ); if ( !StackEmpty ( S ) ) Pop ( S, p ); if ( !Visit ( p-data ) ) return ERROR; Push ( S, p-rchild ); / if / While return OK;/ InOrderTraverse 第6章 樹和二叉樹 Status InOrderTraverse ( BiTree T, Status ( *Visit ) ( TelemType e ) ) InitStack ( S ); p=T; While ( p | !Stack

27、Empty ( S ) ) if ( p ) Push ( S, p ); p=p-lchild; else Pop ( S, p ); if ( !Visit ( p-data ) ) return ERROR; p=p-rchild; return OK; 第6章 樹和二叉樹 圖6.11 中序遍歷二叉樹的非遞歸算法處理流程 ABDCE(a) 二叉樹的遍歷走向BD第一次經(jīng)過第二次經(jīng)過第三次經(jīng)過(b) 遍歷中三次經(jīng)過結(jié)點(diǎn)的情形第6章 樹和二叉樹 遍歷算法應(yīng)用遍歷算法應(yīng)用 1. 輸出二叉樹中的結(jié)點(diǎn)輸出二叉樹中的結(jié)點(diǎn) 遍歷算法將走遍二叉樹中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹中的結(jié)點(diǎn)并無次序要求，因此可用三

28、種遍歷中的任何一種算法完成。 下面寫出先序遍歷順序的實(shí)現(xiàn)算法。 2. 輸出二叉樹中的葉子結(jié)點(diǎn)輸出二叉樹中的葉子結(jié)點(diǎn) 輸出二叉樹中的葉子結(jié)點(diǎn)與輸出二叉樹中的結(jié)點(diǎn)相比，它是一個(gè)有條件的輸出問題，即在遍歷過程中走到每一個(gè)結(jié)點(diǎn)時(shí)需進(jìn)行測試，看是否有滿足葉子結(jié)點(diǎn)的條件。第6章 樹和二叉樹 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中的葉子結(jié)點(diǎn), root為指向二叉樹根結(jié)點(diǎn)的指針 */ if (root! =NULL) if (root -LChild=NULL & root -RChild=NULL) printf (root -data); /* 輸出葉子結(jié)

29、點(diǎn) */ PreOrder(root -LChild); /* 先序遍歷左子樹 */PreOrder(root -RChild); /* 先序遍歷右子樹 */ 第6章 樹和二叉樹 3. 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目 /* LeafCount是保存葉子結(jié)點(diǎn)數(shù)目的全局變量, 調(diào)用之前初始化值為0 */void leaf(BiTree root) if(root! =NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild=NULL & root -RChild=NULL) LeafCount+; 第6章 樹和二叉樹 /*

30、采用遞歸算法，如果是空樹，返回0；如果只有一個(gè)結(jié)點(diǎn)，返回1；否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和 */int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if(root-lchild=NULL)&(root-rchild=NULL) LeafCount =1; else LeafCount =leaf(root-lchild)+leaf(root-rchild); /* 葉子數(shù)為左右子樹的葉子數(shù)目之和 */ return LeafCount; 第6章 樹和二叉樹 4. 建立二叉鏈表方式存儲(chǔ)的二叉樹建立二叉

31、鏈表方式存儲(chǔ)的二叉樹 給定一棵二叉樹，我們可以得到它的遍歷序列；反過來，給定一棵二叉樹的遍歷序列，我們也可以創(chuàng)建相應(yīng)的二叉鏈表。 這里所說的遍歷序列是一種“擴(kuò)展的遍歷序列”。在通常的遍歷序列中，均忽略空子樹，而在擴(kuò)展的遍歷序列中，必須用特定的元素表示空子樹。A B C D E G F 其中用表示空子樹。第6章 樹和二叉樹 Status CreateBiTree( BiTree &T ) scanf ( &ch ); if ( ch = ) T = NULL; else if ( !( T=( BiTNode * ) malloc (sizeof(BiTNode ) ) ) )

32、exit ( OVERFLOW ); T-data=ch; CreateBiTree( T-lchild ); CreateBiTree( T-rchild ); return OK; 第6章 樹和二叉樹 圖圖6.12 二叉樹高度示意圖二叉樹高度示意圖 bt左子樹右子樹hlhrHighmax(hlhr)l5 求二叉樹的高度求二叉樹的高度第6章 樹和二叉樹 設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下: 若bt為空，則高度為0。 若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1， 如圖6.12所示。 二叉樹的高度(深度)為二叉樹中結(jié)點(diǎn)層次的最大值，即結(jié)點(diǎn)的層次自根結(jié)點(diǎn)起遞推。設(shè)根結(jié)點(diǎn)為第1層的結(jié)點(diǎn)

33、，所有h層的結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)在h+1層，則可以通過先序遍歷計(jì)算二叉樹中的每個(gè)結(jié)點(diǎn)的層次，其中最大值即為二叉樹的高度。 第6章 樹和二叉樹 int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹的高度遞歸算法 */ int hl, hr, max; if(bt! =NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度 */ max=hlhr?hl: hr; /* 得到左、 右子樹深度較大者*/ return(max+1); /* 返回樹的深度 *

34、/ else return(0); /* 如果是空樹， 則返回0 */ 第6章 樹和二叉樹 6. 按樹狀打印的二叉樹按樹狀打印的二叉樹 例：例：假設(shè)以二叉鏈表存儲(chǔ)的二叉樹中，每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母, 要求實(shí)現(xiàn)如圖6.13所示打印結(jié)果。 這實(shí)際是一個(gè)二叉樹的橫向顯示問題：因?yàn)槎鏄涞臋M向顯示應(yīng)是二叉樹豎向顯示的90旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為先右子樹再根結(jié)點(diǎn)再左子樹的RDL結(jié)構(gòu)， 實(shí)現(xiàn)算法如下： 第6章 樹和二叉樹 ABCDEF輸出CAEFDB圖6.13 樹狀打印的三叉樹示意第6章 樹和二叉樹 void PrintTree(Bitre

35、e root, int nLayer) /* 按豎向樹狀打印的二叉樹 */ if(root= =NULL) return; PrintTree(root-rchild, nLayer+1); for(int i=0; idata); PrintTree(root-lchild, nLayer+1); 第6章 樹和二叉樹 6.3.2 線索二叉樹線索二叉樹 1. 基本概念基本概念 二叉樹的遍歷運(yùn)算是將二叉樹中結(jié)點(diǎn)按一定規(guī)律線性化的過程。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息可采用以下兩種方法：第一種方法是將二叉樹遍歷

36、一遍，在遍歷過程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問浪費(fèi)時(shí)間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來。 第6章 樹和二叉樹 我們知道，在有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)鏈域，但只有n-1個(gè)有用的非空鏈域，其余n+1個(gè)鏈域是空的。我們可以利用剩下的n+1個(gè)空鏈域來存放遍歷過程中結(jié)點(diǎn)的前驅(qū)和后繼信息。現(xiàn)作如下規(guī)定：若結(jié)點(diǎn)有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點(diǎn)。為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下所示： LC

37、hildLtagDataRtagRChild第6章 樹和二叉樹 其中： 在這種存儲(chǔ)結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。 以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。對(duì)二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程叫做線索化。線索化了的二叉樹稱為線索二叉樹。 0 LChild域指示結(jié)點(diǎn)的左孩子LChild域指示結(jié)點(diǎn)的遍歷前驅(qū)0 RChild域指示結(jié)點(diǎn)的右孩子1 RChild域指示結(jié)點(diǎn)的遍歷后繼 LTag= RTag= 第6章 樹和二叉樹 圖圖6.14 線索二叉樹線索二叉樹 ABCDEFGH(a) 二叉樹ABCDEFGH(b )先序線索二叉樹ACDEFGH(c) 中序線索二叉樹A

38、BCDEFGH(d) 后序線索二叉樹BNULLNULLNULLNULL第6章 樹和二叉樹 3. 在線索二叉樹中找前驅(qū)、在線索二叉樹中找前驅(qū)、 后繼結(jié)點(diǎn)后繼結(jié)點(diǎn) 1）對(duì)中序線索樹： 找后繼 若 rtag=1 則rchild指示后繼 若 rtag=0 右子樹的最左下結(jié)點(diǎn)為后繼 找前驅(qū) 若 ltag=1 則lchild指示前驅(qū) 若 ltag=0 左子樹最右下結(jié)點(diǎn)為前驅(qū) 第6章 樹和二叉樹 對(duì)后序線索樹找后繼，分3種情況 若結(jié)點(diǎn)x是二叉樹的根，則后繼為空； 若x是雙親的右孩子或是雙親的左孩子且雙親沒有右子樹，則后繼為雙親； 若x是雙親的左孩子，且雙親有右子樹，則后繼為雙親右子樹，第一個(gè)遍歷的結(jié)點(diǎn)。 可

39、見，在后序線索化樹上找后繼時(shí)需知道雙親，即需帶標(biāo)志域的三叉鏈表作為存儲(chǔ)結(jié)構(gòu)。 第6章 樹和二叉樹 在中序線索二叉樹上遍歷二叉樹，雖時(shí)間復(fù)雜度也為O（n ）但常數(shù)因子比前面討論的算法小，且不需要設(shè)棧，若經(jīng)常找前驅(qū)、后繼，應(yīng)采用線索鏈表做為存儲(chǔ)結(jié)構(gòu)。 為方便起見，在二叉鏈表上添加一個(gè)頭結(jié)點(diǎn)，并令lchild指向二叉樹的根rchild指向最后訪問的結(jié)點(diǎn)。同樣，第一個(gè)訪問結(jié)點(diǎn)的lchild和最后訪問結(jié)點(diǎn)的rchild指向頭結(jié)點(diǎn)，雙向線索鏈表。 第6章 樹和二叉樹 6.4 樹和森林樹和森林6.4.1 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu) 樹的主要存儲(chǔ)方法有以下三種： 1. 雙親表示法雙親表示法 這種方法用一組連續(xù)的

40、空間來存儲(chǔ)樹中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來指示其雙親結(jié)點(diǎn)在表中的位置， 其結(jié)點(diǎn)的結(jié)構(gòu)如下： DataParent數(shù)據(jù) 雙親 第6章 樹和二叉樹 圖6.18 樹的雙親表示法 第6章 樹和二叉樹 雙親表示法的形式說明如下： #define MAX_TREE_SIZE 100typedef struct PTNode TelemType data; int parent;PTNode;typedef struct PTNode nodes MAX_TREE_SIZE ; int r, n;Ptree; PARENT ( T, x ) 常數(shù)量時(shí)間;反復(fù)PARENT操作可找到樹的根，即R

41、OOT（x ）;求解孩子，需遍歷整個(gè)鏈表。第6章 樹和二叉樹 2. 孩子表示法孩子表示法 這種方法通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表），而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。 這種存儲(chǔ)結(jié)構(gòu)的形式說明如下： typedef struct CTNode int child; struct CTNode *next; *ChildPtr; 第6章 樹和二叉樹 typedef struct TelemType data; ChildPtr firstchild; CTBox; typedef struc

42、t CTBox nodes MAX_TREE_SIZE ; int n, r; Ctree; 第6章 樹和二叉樹 圖6.19 樹的孩子鏈表表示法 第6章 樹和二叉樹 3. 孩子兄弟表示法孩子兄弟表示法圖6.20 樹的孩子兄弟表示法 第6章 樹和二叉樹 孩子兄弟表示法的類型定義如下： 鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域 typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling;CSNode, *CSTree;

43、這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)樹的各種操作，例如：如果要訪問結(jié)點(diǎn)x的第i個(gè)孩子，則只要先從FirstChild域找到第一個(gè)孩子結(jié)點(diǎn)，然后沿著這個(gè)孩子結(jié)點(diǎn)的Nextsibling域連續(xù)走i-1步，便可找到x的第i個(gè)孩子。如果在這種結(jié)構(gòu)中為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)Parent域，則同樣可以方便地實(shí)現(xiàn)查找雙親的操作。 第6章 樹和二叉樹 6.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 1. 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹 圖6.21 樹 ACBDEFGH第6章 樹和二叉樹 將一棵樹轉(zhuǎn)換為二叉樹的方法是： (1) 樹中所有相鄰兄弟之間加一條連線。 (2) 對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其

44、它孩子結(jié)點(diǎn)之間的連線。 (3) 以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。 可以證明，樹做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。 圖6.22給出了將圖6.21所示的樹轉(zhuǎn)換為二叉樹的轉(zhuǎn)換過程示意。 第6章 樹和二叉樹 圖6.22 樹到二叉樹的轉(zhuǎn)換 ABDEFCGHABDEFCGHABDEFCHG第6章 樹和二叉樹 圖6.23 樹與二叉樹的對(duì)應(yīng) DABCE對(duì)應(yīng)ABCDEABCDEEABCDABCDE存儲(chǔ)存儲(chǔ)解釋解釋第6章 樹和二叉樹 2. 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹 森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈

45、表表示。森林轉(zhuǎn)換為二叉樹的方法如下： （1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子， 當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。 第6章 樹和二叉樹 圖6.24 森林轉(zhuǎn)換為二叉樹的過程 ABCDEFGHIJ(a) 森林ABCDEFGHIJ(b) 森林中每棵樹對(duì)應(yīng)的二叉樹ABEFGHIHCD(c) 森林對(duì)應(yīng)的二叉樹第6章 樹和二叉樹 如果F= T1, T2, , Tm 是森林，按以下規(guī)則轉(zhuǎn)換成一棵二叉樹B= ( root, LB, RB ) （1）若F為空即m=0，則B為空

46、樹 （2）若F非空，則B的根root為森林第一棵樹的根ROOT（T1）B的左子樹LB是從T1中各結(jié)點(diǎn)的子樹森林F1= T11，T12，T1m1 轉(zhuǎn)換成二叉樹，其右子樹RB是從森林F= T2，T3，Tm 轉(zhuǎn)換成二叉樹。 第6章 樹和二叉樹 3. 二叉樹還原為樹或森林二叉樹還原為樹或森林 樹和森林都可以轉(zhuǎn)換為二叉樹，二者的不同是：樹轉(zhuǎn)換成的二叉樹，其根結(jié)點(diǎn)必然無右孩子，而森林轉(zhuǎn)換后的二叉樹，其根結(jié)點(diǎn)有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下： （1） 若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、 右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。 （2） 刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)

47、點(diǎn)的連線。 （3） 整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。 第6章 樹和二叉樹 圖6.25 二叉樹到森林的轉(zhuǎn)換示例 ABECFGHIJD(a) 添加連線ABECFGHIJD(b) 刪除右孩子結(jié)點(diǎn)的連線ABCDEFGHIJ(c) 整理第6章 樹和二叉樹 同樣，我們可以用遞歸的方法描述上述轉(zhuǎn)換過程。 如果B=（ root，LB，RB ）是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F= T1, T2, , Tm （1）若B為空，則F為空； （2）若B為非空，則F中第一棵樹T1的根ROOT（T1）即為二叉樹B的根root；T1中根結(jié)點(diǎn)的子樹森林F1是由B的左子樹LB轉(zhuǎn)換成的森林F中除T

48、1之外其余樹組成的森林F= T2，T3，Tm 是由B的右子樹RB轉(zhuǎn)換成的森林。 根據(jù)這個(gè)遞歸的定義，我們同樣可以寫出遞歸的轉(zhuǎn)換算法。 第6章 樹和二叉樹 6.4.3 樹的遍歷樹的遍歷 1. 樹的遍歷樹的遍歷 樹的遍歷方法主要有以下兩種： 1） 先根遍歷 若樹非空，則遍歷方法為： (1) 訪問根結(jié)點(diǎn)。 (2) 從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。 例如，圖6.21中樹的先根遍歷序列為ABECFHGD。 第6章 樹和二叉樹 2） 后根遍歷 若樹非空，則遍歷方法為： （1） 從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹。 （2） 訪問根結(jié)點(diǎn)。 例如，圖6.21中樹的后根遍歷序列為EBHFGCDA。

49、 2. 森林的遍歷森林的遍歷 森林的遍歷方法主要有以下三種： 1） 先序遍歷 若森林非空，則遍歷方法為： (1) 訪問森林中第一棵樹的根結(jié)點(diǎn)。 (2) 先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林。 (3) 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 例如，圖6.24(a)中森林的先序遍歷序列為ABCDEFGHIJ。 第6章 樹和二叉樹 2） 中序遍歷若森林非空， 則遍歷方法為： (1) 中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。 (2) 訪問第一棵樹的根結(jié)點(diǎn)。 (3) 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 例如，圖6.24(a)中森林的中序遍歷序列為BCDAFEHJIG。 第6章 樹和二叉樹

50、 6.5 樹與等價(jià)問題typedef PTree MFSet;int find_mfset(MFSet S, int i)/找集合找集合S中中i所在子集的根。所在子集的根。if(iS.n) return -1;for(j=i; S.nodesj.parent; j=S.nodesj.parent);return j;算法算法6.8第6章 樹和二叉樹 Status merge_mfset(MFSet &S, int i, int j)if(iS.n |jS.n) return ERROR;S.nodesi.parent=j;return OK;算法算法6.9void mix_mfset(

51、MFSet &S, int i, int j)if(iS.n |jS.n) return ERROR;if(S.nodesi.parentS.nodesj.parent)S.nodesj.parent+=S.nodesi.parent;S.nodesi.parent=j;elseS.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i; return OK;第6章 樹和二叉樹 int fix_mfset(MFSet &S, int i)if(iS.n) return -1;for(j=i; S.nodesj.parent0; j=S.

52、nodesj.parent);for(k=i; k!=j; k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;算法算法6.11第6章 樹和二叉樹 6.6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用 6.6.1 最優(yōu)二叉樹最優(yōu)二叉樹 1. 路徑和路徑長度路徑和路徑長度 路徑是指從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列， 路徑長度是指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支數(shù)目。 樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。 完全二叉樹是路徑長度最短的二叉樹。 第6章 樹和二叉樹 2. 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度 在實(shí)際的應(yīng)用中，人們常常給樹的

53、每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)權(quán)。在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)從樹根到某一結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長度的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長度。 第6章 樹和二叉樹 3. 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為： iniiWWPL11 其中n為葉子結(jié)點(diǎn)的個(gè)數(shù)，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長度。 例如， 圖 6.26中三棵二叉樹的帶權(quán)路徑長度分別為： WPL(a)=7252224236WPL(

54、b)=4273532146WPL(c)=7152234335 假設(shè)假設(shè)n個(gè)權(quán)值個(gè)權(quán)值 w1, w2, , wn 構(gòu)造一棵有構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為二叉樹，每個(gè)葉子的權(quán)值為wi 則則WPL最小的二叉樹，叫做最最小的二叉樹，叫做最優(yōu)二叉樹優(yōu)二叉樹 。第6章 樹和二叉樹 圖6.26 具有不同帶權(quán)路徑長度的二叉樹 ABCD7524(a) 帶權(quán)路徑長度為36ABCD7524(b) 帶權(quán)路徑長度為46ADCB7524(c) 帶權(quán)路徑長度為35第6章 樹和二叉樹 問題1: 什么樣的二叉樹的路徑長度PL最??？ 一棵樹的路徑長度為0，結(jié)點(diǎn)至多只有1個(gè)（根）； 路徑長度為1，結(jié)

55、點(diǎn)至多只有2個(gè)（兩個(gè)孩子）； 路徑長度為2，結(jié)點(diǎn)至多只有4個(gè)； 依此類推，路徑長度為k，結(jié)點(diǎn)至多只有2k個(gè), 所以n個(gè)結(jié)點(diǎn)二叉樹其路徑長度至少等于如圖6.27所示序列的前n項(xiàng)之和。 圖圖6.27 結(jié)點(diǎn)序列及結(jié)點(diǎn)的路徑長度結(jié)點(diǎn)序列及結(jié)點(diǎn)的路徑長度 結(jié)點(diǎn)路徑長度0，1， 1， 2，2，2，2， 3， 3， 3， 3， 3， 3， 3， 3， 4，4，結(jié)點(diǎn)數(shù)n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=15 第6章 樹和二叉樹 由圖6.27可知，結(jié)點(diǎn)n對(duì)應(yīng)的路徑長度為log2n，所以前n項(xiàng)之和為 。完全二叉樹的路徑長度 (h為樹的深度)，所以完全二叉樹具有最小路徑長度的性質(zhì)

56、，但不具有唯一性。有些樹并不是完全二叉樹，但也可以具有最小路徑長度，如圖6.28所示。 nkk12loghkhkh12210log2221202 圖6.28 具有相同最小路徑長度的不同形態(tài)的二叉樹 ABCDE(a) PL 0 1 1 2 2 6BCDEA(b) PL 0 1 1 2 2 6第6章 樹和二叉樹 問題問題2: 什么樣的樹的帶權(quán)路徑長度最小？ 例如：給定一個(gè)權(quán)值序列2, 3, 4, 7，可構(gòu)造如圖6.29所示的多種二叉樹的形態(tài)。 圖圖6.29 具有不同帶權(quán)路徑長度的二叉樹具有不同帶權(quán)路徑長度的二叉樹 234723477432(a) W PL 22 23 24 27 32(b) W P

57、L 12 23 34 37 41(c) W PL 17 24 33 32 7 8 9 6 30第6章 樹和二叉樹 4. 赫赫夫曼樹夫曼樹 構(gòu)造赫夫曼算法的步驟如下： （1） 用給定的n個(gè)權(quán)值w1, w2, , wn對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F=T1, T2, , Tn，其中每一棵二叉樹Ti(1in)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空。 （2） 在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。 第6章 樹和二叉樹 （3） 從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。 （4）

58、重復(fù)（2）、（3）操作， 直到森林中只含有一棵二叉樹為止，此時(shí)得到的這棵二叉樹就是赫夫曼樹。 第6章 樹和二叉樹 6.6.2 赫赫夫曼編碼夫曼編碼 電報(bào)需將傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串，如ABACCDA設(shè)A、B、C、D編碼分別為00、01、10、11則0001001010110014位，對(duì)方接收時(shí)將其譯碼。在傳送電文時(shí)，希望總長度盡可能的短，如A、B、C、D分別編碼為0、00、1和01，則上述7個(gè)字符轉(zhuǎn)換成總長為9位000011010，但是這樣的電文無法譯碼。0000可有多種譯法AAAA或ABA、BB，設(shè)計(jì)時(shí)用前綴編碼。 前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，可利

59、用二叉樹設(shè)計(jì)前綴編碼。 第6章 樹和二叉樹 設(shè)計(jì)電文總長最短的前綴編碼，設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi編碼長度為Li，有n種字符，電文總長wiLi ( i=1n) 對(duì)應(yīng)二叉樹上，若置wi為葉子結(jié)點(diǎn)的權(quán)，恰為WPL,即設(shè)計(jì)赫夫曼樹，得到的前綴編碼為赫夫曼編碼，赫夫曼樹中沒有度為1的結(jié)點(diǎn)（嚴(yán)格的（正則的）二叉樹），一棵有n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，可以存儲(chǔ)在2n-1的一維數(shù)組中，另外需知道雙親。 第6章 樹和二叉樹 表 6 1 指令的使用頻率 指令使用頻率(Pi）I10.40I20.30I30.15I40.05I50.04I60.03I70.03第6章 樹和二叉樹 表表 6 2

60、指令的變長編碼指令的變長編碼 指令使用頻率(Pi）I10I21I300I401I5000I6001I7010第6章 樹和二叉樹 圖6.30 構(gòu)造赫夫曼樹示例 1.000.030.030.060.050.040.090.150.150.300.300.600.40I7I6I5I4I3I2I1第6章 樹和二叉樹 表表 6 3 指令的赫夫曼編碼指令的赫夫曼編碼 指令使用頻率(Pi）I10I210I3110I411100I511101I611110I711111第6章 樹和二叉樹 可以驗(yàn)證，該編碼是前綴編碼。若一段程序有1000條指令， 其中I1大約有400條，I2大約有300條，I3大約有150條，I4大約有50條，I5大約有40條，I6大約有30條，I7大約有30條。對(duì)于定長編碼，該段程序的總位數(shù)大約為3100