數(shù)據(jù)結(jié)構(gòu)課件：第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用

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

2、PL=29=18其中n表示葉子結(jié)點的數(shù)目wi表示葉子結(jié)點ki的權(quán)值li表示根到ki之間的路徑長度基本術(shù)語6.5 赫夫曼(Huffman)樹及其應(yīng)用赫夫曼樹：帶權(quán)路徑長度最小的樹, 又稱最優(yōu)二叉樹樹的帶權(quán)路徑長度如何計算？Weighted Path Length例：有四個葉子結(jié)點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 個權(quán)值w0, w

3、1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴(kuò)充二叉樹 Ti 只有一個帶有權(quán)值 wi 的根結(jié)點，其左、右子樹均為空。 (2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹為止： 在 F 中選取兩棵根結(jié)點的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(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個數(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個數(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)換成對應(yīng)的字符序列，即譯碼。 赫夫曼編碼(赫夫曼樹的應(yīng)用之二)6.5 赫夫曼(Huffman)樹及其應(yī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)頻率低的字符具有較長的編碼，縮短傳送電文的總長度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）前綴編碼 若對某一字符集進(jìn)行不等長編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴。符合此要求的編碼叫做前綴編碼。利用二叉樹設(shè)計二進(jìn)制的前綴編碼6.5 赫夫曼(Huffman)樹及其應(yīng)用01abcd1100 假設(shè)有一棵如左圖所示的二叉樹，四個葉結(jié)點分別表示A、B、C、D四個字符，且約定左分支表示字符0 ，右分支表示字符1，則可以從根結(jié)點到葉子結(jié)點的路徑上以分支字符組成的字符串作為該葉子結(jié)點的編碼?？梢宰C明，如此得

8、到的必為二進(jìn)制前綴編碼。 赫夫曼編碼6.5 赫夫曼(Huffman)樹及其應(yīng)用 設(shè)計電文總長最短的二進(jìn)制前綴編碼即： 以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計一棵赫夫曼樹的問題，由此得到的二進(jìn)制前綴編碼稱赫夫曼編碼。 赫夫曼編碼6.5 赫夫曼(Huffman)樹及其應(yīng)用例：設(shè)通信用的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，試為這8個字母設(shè)計哈夫曼編碼。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對應(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)