1、樹和森林第6章 樹和二叉樹樹的基本概念二叉樹遍歷二叉樹和線索二叉樹赫夫曼樹及其應(yīng)用基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用路 徑路徑長(zhǎng)度樹的路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度霍 夫 曼 樹基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用DABCEFG路徑：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑長(zhǎng)度：路徑上的分支數(shù)目ae的路徑長(zhǎng)度2樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和樹長(zhǎng)度10基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用DABCEFG結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和3798結(jié)點(diǎn)F的路徑長(zhǎng)度為2，其W

2、PL=29=18其中n表示葉子結(jié)點(diǎn)的數(shù)目wi表示葉子結(jié)點(diǎn)ki的權(quán)值li表示根到ki之間的路徑長(zhǎng)度基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用赫夫曼樹：帶權(quán)路徑長(zhǎng)度最小的樹, 又稱最優(yōu)二叉樹樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算？Weighted Path Length例：有四個(gè)葉子結(jié)點(diǎn)a,b,c,d，分別帶權(quán)為7, 5, 2, 4，由它們構(gòu)成三棵不同的二叉樹6.5 赫夫曼(Huffman)樹及其應(yīng)用abdc7524cdab2457bdac7524WPL=36WPL=46WPL= 35Huffman樹構(gòu)造最優(yōu)樹(赫夫曼算法)6.5 赫夫曼(Huffman)樹及其應(yīng)用(1) 由給定的 n 個(gè)權(quán)值w0, w

3、1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴(kuò)充二叉樹 Ti 只有一個(gè)帶有權(quán)值 wi 的根結(jié)點(diǎn)，其左、右子樹均為空。 (2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹為止： 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。第一步：abcd9254第二步：第三步：第四步：abc9654d2abc9654d211abc9654d21120第一步：5629第二步：第三步：第四步：

4、7562977562977135629771316第五步：562977131629第一步：5629第二步：第三步：第四步：75629775629779716第五步：57269716132913562713第一步：56297572697161329562977131629判定樹 (赫夫曼樹的應(yīng)用之一)6.5 赫夫曼(Huffman)樹及其應(yīng)用分?jǐn)?shù)0596069707980899099比例0.050.150.40.30.1a60 a70 a80 a90 不及格 中等 良好 優(yōu)秀 及格YNYNYNYN輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行31500次比較。判定樹 (赫夫曼樹的應(yīng)用之一)6.5 赫夫曼(Huf

5、fman)樹及其應(yīng)用分?jǐn)?shù)0596069707980899099比例0.050.150.40.30.170a80 a60 及格中等良好80a90 60a70 不及格優(yōu)秀YNYYYNNN以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹，如(b)判斷樹所示。再將每一比較框的兩次比較改為一次判定樹 (赫夫曼樹的應(yīng)用之一)6.5 赫夫曼(Huffman)樹及其應(yīng)用分?jǐn)?shù)0596069707980899099比例0.050.150.40.30.1不及格Ya90 a80 a70 a60 優(yōu)秀中等及格良好YNNNYYY輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。赫夫曼編碼(赫夫曼樹的應(yīng)用之二)6.5 赫夫曼(Huffman)樹

6、及其應(yīng)用1）二進(jìn)制編碼 通信中，可以采用0、1的不同排列來表示不同的字符，稱為二進(jìn)制編碼。 發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進(jìn)制的0、1序列，即編碼； 接受端需要把接受的0、1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列，即譯碼。 赫夫曼編碼(赫夫曼樹的應(yīng)用之二)6.5 赫夫曼(Huffman)樹及其應(yīng)用等長(zhǎng)編碼不等長(zhǎng)編碼A B C D00 01 10 11發(fā)送：A B A C C C C D A B00 01 00 10 10 10 10 11 00 01 讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，縮短傳送電文的總長(zhǎng)度A B C D 1 10 0 01發(fā)送：A B A C C C

7、C D A B 1 10 1 0 0 0 0 01 1 10?無法譯碼！為此引入前綴編碼的概念赫夫曼編碼(赫夫曼樹的應(yīng)用之二)6.5 赫夫曼(Huffman)樹及其應(yīng)用2）前綴編碼 若對(duì)某一字符集進(jìn)行不等長(zhǎng)編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴。符合此要求的編碼叫做前綴編碼。利用二叉樹設(shè)計(jì)二進(jìn)制的前綴編碼6.5 赫夫曼(Huffman)樹及其應(yīng)用01abcd1100 假設(shè)有一棵如左圖所示的二叉樹，四個(gè)葉結(jié)點(diǎn)分別表示A、B、C、D四個(gè)字符，且約定左分支表示字符0 ，右分支表示字符1，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上以分支字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼。可以證明，如此得

8、到的必為二進(jìn)制前綴編碼。 赫夫曼編碼6.5 赫夫曼(Huffman)樹及其應(yīng)用 設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即： 以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一棵赫夫曼樹的問題，由此得到的二進(jìn)制前綴編碼稱赫夫曼編碼。 赫夫曼編碼6.5 赫夫曼(Huffman)樹及其應(yī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.32, 0.03, 0.21, 0.10 ，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。0.070.190.020.060.320.030.210.100.070.190.020.060.320.

9、030.210.100.050.070.190.020.060.320.030.210.100.050.110.070.190.020.060.320.030.210.100.050.110.170.070.190.020.060.320.030.210.100.050.110.170.280.070.190.020.060.320.030.210.100.050.110.170.280.400.070.190.020.060.320.030.210.100.050.110.170.280.400.600.070.190.020.060.320.030.210.100.050.110.170.

10、280.400.601.00000000011111110.070.190.020.060.320.030.210.100.050.110.170.280.400.601.0000000001111111a, b, c, d, e, f, g, h 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 abcdefgh0.070.190.020.060.320.030.210.100.050.110.170.280.400.601.0000000001111111a, b, c, d, e, f, g, h 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 abcdefgha = 1010b = 00c = 10000d = 1001e = 11f = 10001g = 01h = 1011對(duì)應(yīng)的哈夫曼編碼（左0右1）符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的WPL2(0.19+0.32+0.21)