大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹和二叉樹-第六節(jié)-哈夫曼樹及其應(yīng)用

第六節(jié)哈夫曼樹及其應(yīng)用一、最優(yōu)二叉樹（哈夫曼樹）1．樹的路徑長度樹的路徑長度是從樹根到樹中每一結(jié)點的路徑長度之和。在結(jié)點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。2．樹的帶權(quán)路徑長度(WPL)結(jié)點的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點的一個有某種意義的實數(shù)。結(jié)點的帶權(quán)路徑長度：結(jié)點到樹根之間的路徑長度與該結(jié)點上權(quán)的乘積。樹的帶權(quán)路徑長度(WPL)：定義為樹中所有葉結(jié)點的帶權(quán)路徑長度之和。3．最優(yōu)二叉樹或哈夫曼樹帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹?！纠拷o定4個葉子結(jié)點a，b，c和d，分別帶權(quán)8，5，4和2。構(gòu)造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權(quán)路徑長度分別為：(a)：WPL=8×3+5×3+2×1+4×2=49(b)：WPL=8×3+5×2+2×3+4×1=44(c)：WPL=8×1+5×2+2×3+4×3=36其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。二、哈夫曼算法1、構(gòu)造哈夫曼樹的方法：①將給定的權(quán)值按照從小到大排列成｛W1，W2，…，Wm｝，并且構(gòu)造出樹林F=｛Tl，T2，…，Tm｝。此時，其中的每棵樹Ti(1≤i≤m）為左、右子樹均為空的二叉樹，二叉樹的根結(jié)點的權(quán)值為Wi

。②把F中樹根結(jié)點的權(quán)值最小的兩棵二叉樹T1和T2合并為一棵新的二叉樹T（T的左子樹為T1，右子樹為T2），并令T的根結(jié)點的權(quán)值為T1和T2的根結(jié)點的權(quán)值之和，然后將T按其根結(jié)點的權(quán)值大小依次加入到樹林F中。同時，從F中刪去T1和T2這兩棵二叉樹。③重復(fù)步驟②，直到構(gòu)造成一棵哈夫曼樹?！菊骖}選解】（例題?填空題）用6個權(quán)值分別為6、13、18、30、7和16的結(jié)點構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長度為_________。隱藏答案【解析】用6個權(quán)值構(gòu)造的過程如下圖構(gòu)造的哈夫曼樹的帶權(quán)路徑長度=（16+18+30）*2+13*3+（6+7）*4=2192、哈夫曼樹的特點：①在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近。②若有n0個權(quán)值，需要進(jìn)行n0-1次合并，構(gòu)造成為哈夫曼樹。③哈夫曼樹沒有度為1的結(jié)點。④由n0個權(quán)值構(gòu)成的哈夫曼樹，葉結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n0-1，結(jié)點總數(shù)為n0+n2=n0+n0-1=2n0-1。⑤給定一組權(quán)值，構(gòu)造出的哈夫曼樹的形態(tài)可能不唯一，但它們的帶權(quán)路徑長度都一樣。三、哈夫曼編碼1、編碼的概念（1）編碼和解碼數(shù)據(jù)壓縮過程稱為編碼。即將文件中的每個字符均轉(zhuǎn)換為一個唯一的二進(jìn)制位串。數(shù)據(jù)解壓過程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為對應(yīng)的字符。（2）前綴碼方案對字符集進(jìn)行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴(編)碼?！菊骖}選解】（例題?單選題）下述編碼中不是前綴碼的是（）A.(00，01，10，11)B.(0，1，00，11)C.(0，10，110，111)D.(1，01，000，001)隱藏答案【答案】B【解析】四個選項中除選項B外，其它三個選項的編碼滿足任一字符的編碼都不是其它字符的編碼的前綴。2、哈夫曼編碼設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼?！菊骖}選解】（例題?算法題）假設(shè)通信電文使用的字符集為{a，b，c，d，e，f，g，h}，各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，試為這8個字符設(shè)計哈夫曼編碼。要求：(1)畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值)；(2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應(yīng)的編碼。隱藏答案【解析】先按照權(quán)值構(gòu)造哈夫曼樹，注意要滿足題目的要求：樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值。構(gòu)造過程如下圖：到這里就很容易寫出每個字符的哈夫曼編碼了?！敬鸢浮浚?）（2）各字符的編碼：a（0101），b（10），c（01000），d（11），e（011），f（000）g（01001）h（001）注意：每個字符的編碼都不是另外一個編碼的前綴。當(dāng)前講授本章小結(jié)本章首先介紹了一般樹和二叉樹的基本概念。主要介紹了四種不同的遍歷二叉樹算法，前三種算法的主要區(qū)別在