1、第6章 樹(shù)和二叉樹(shù) 6.1 樹(shù)的定義和基本術(shù)語(yǔ) 6.2 二叉樹(shù) 6.3 遍歷二叉樹(shù)和線索二叉樹(shù) 6.4 樹(shù)和森林 6.6 赫夫曼樹(shù)及其應(yīng)用,6.6 赫夫曼樹(shù)及其應(yīng)用,1.基本術(shù)語(yǔ) 1）路徑和路徑長(zhǎng)度 若一棵樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k1,k2,kj，使得ki是kj的雙親（0ij），則稱(chēng)此結(jié)點(diǎn)序列是從ki kj的路徑。從k1kj所經(jīng)過(guò)的分支數(shù)稱(chēng)為這兩點(diǎn)之間的路徑長(zhǎng)度，它等于路徑上的結(jié)點(diǎn)數(shù)減1。,在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱(chēng)其為該結(jié)點(diǎn)的權(quán)。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（WPL)規(guī)定為從樹(shù)根到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。,例：結(jié)點(diǎn)c的路徑長(zhǎng)度為2，其WPL=2*9=18

2、,2）結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度,樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常記為： 其中 n 表示葉子結(jié)點(diǎn)的數(shù)目，wi 和 li分別表示葉子結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度。,3）樹(shù)的帶權(quán)路徑長(zhǎng)度,4）赫夫曼（Huffman）樹(shù) 又稱(chēng)最優(yōu)二叉樹(shù)。它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)。,例：有四個(gè)葉子結(jié)點(diǎn)a,b,c,d，分別帶權(quán)為9、4、5、2，由它們構(gòu)成三棵不同的二叉樹(shù)。,a） WPL=92 +42522240 b） WPL=4122539350 c） WPL=9152432337,a,b,c,1）根據(jù)給定的n個(gè)權(quán)值w1, w2, , wn，構(gòu)造 n棵二叉

3、樹(shù)的集合 F = T1, T2, ,Tn，其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹(shù)為空樹(shù)；,4) 重復(fù)(2)和(3)兩步，直至F中只含一棵樹(shù)為止。,3) 從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)；,2) 在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和;,2.構(gòu)造最優(yōu)樹(shù),赫夫曼算法：,3.判定樹(shù) (赫夫曼樹(shù)的應(yīng)用之一),在解決某些判定問(wèn)題時(shí)，利用赫夫曼樹(shù)可以得到最佳判定算法。 例：編制一將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。 若學(xué)生成績(jī)分布是 均勻的，可用圖(a) 二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。,

4、輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行31500次比較。,學(xué)生成績(jī)分布不是均勻的情況：,有沒(méi)有一種更好的辦法來(lái)減少比較次數(shù)呢？,(b),以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹(shù)，如（b)判斷樹(shù)所示。,再將每一比較框的兩次比較改為一次，可得到（c)判定樹(shù)。,輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。,4.赫夫曼編碼（赫夫曼樹(shù)的應(yīng)用之二）,1）二進(jìn)制編碼 通信中，可以采用0、1的不同排列來(lái)表示不同的字符，稱(chēng)為二進(jìn)制編碼。 發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進(jìn)制的0、1序列，即編碼； 接受端需要把接受的0、1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列，即譯碼。,字符：A B A C C D A,電文：00010010101100

5、,A B C D的編碼分別為：00、01、10、11,電文總長(zhǎng)度為：14,如何能縮短傳送電文的 總長(zhǎng)度，從而節(jié)省傳送 時(shí)間呢？,若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣有可能縮短傳送電文的總長(zhǎng)度。,字符：A B A C C D A A B C D的編碼分別為：0、00、1、01 電文： 0 0 0 0 1 1 0 1 0 電文總長(zhǎng)度為：9,?,無(wú)法譯碼！為此引入前綴編碼的概念,2）前綴編碼,若對(duì)某一字符集進(jìn)行不等長(zhǎng)編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴。符合此要求的編碼叫做前綴編碼。,如何設(shè)計(jì)前綴編碼？,利用二叉樹(shù)設(shè)計(jì)二進(jìn)

6、制的前綴編碼,如何得到電文總長(zhǎng)最短的二進(jìn)制前綴編碼呢？,0,1,假設(shè)有一棵如左圖所示的二叉樹(shù)，四個(gè)葉結(jié)點(diǎn)分別表示A、B、C、D四個(gè)字符，且約定左分支表示字符0，右分支表示字符1，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上以分支字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼?？梢宰C明，如此得到的必為二進(jìn)制前綴編碼。,3）赫夫曼編碼,設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即： 以 n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一棵赫夫曼樹(shù)的問(wèn)題，由此得到的二進(jìn)制前綴編碼稱(chēng)赫夫曼編碼。,例：設(shè)通信用的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.

7、32, 0.03, 0.21, 0.10 ，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。,a = 1010 b = 00 c = 10000 d = 1001 e = 11 f = 10001 g = 01 h = 1011,b g e d a h c f,typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode, *HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù) typedef char *HuffmanCode;,建立赫夫曼樹(shù)及求赫夫曼編碼的算法,赫夫曼樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，則一棵有n個(gè)葉子結(jié)點(diǎn)的赫夫曼

8、樹(shù)共有2n-1個(gè)結(jié)點(diǎn)，可以存儲(chǔ)在一個(gè)大小為2n-1的一維數(shù)組中。 由于在構(gòu)造赫夫曼樹(shù)之后，為求編碼需從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑；而為譯碼需從根出發(fā)走一條從根到葉子的路徑。所以，每個(gè)結(jié)點(diǎn)既需知道雙親的信息，又需知道孩子結(jié)點(diǎn)的信息。,void HuffmanCoding(HuffmanTree ,for (; iweight = 0; p-parent=0; p-lchild=0; p-rchild=0; / *p=0,0,0,0; 初始化HT中的內(nèi)部結(jié)點(diǎn) for (i=n+1; i=m;+i) / 建赫夫曼樹(shù)，(建立HT靜態(tài)鏈表中的鏈) Select(HT,i-1,s1,s2);/在H

9、T1i-1中選擇parent / 為0且weight最小的兩個(gè)結(jié)點(diǎn)，序號(hào)分別為s1和s2 HTs1.parent=i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; ,/從葉子到根逆向求赫夫曼編碼 HC= (HuffmanCode)malloc(n+1)*sizeof(char *); cd = (char *)malloc( n * sizeof(char) ); cdn-1=0; /編碼結(jié)束符 for (i=1;i=n;+i) /逐個(gè)字符求赫夫曼編碼 st

10、art = n-1; /編碼結(jié)束符位置 for (c=i,f=HTc.parent; f!=0; c=f,f=HTf.parent) /從葉子到根逆向求編碼 if (HTf.lchild =c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi, /釋放工作空間 /HuffanCoding,例： 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)Huffman編碼。 設(shè)權(quán)w=（5，29，7，8，14，23，3，11），n=8，則m=15 存儲(chǔ)結(jié)構(gòu)的初始狀態(tài)為：,23,11,5,3,29,14,7,8,HC,0,1,0,0,0,0,0,0,1,1,1,1,1,1,cd,0,本章小結(jié) 1.熟練掌握二叉樹(shù)的結(jié)構(gòu)特性 2.熟練二