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

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

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

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

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

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

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

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