數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 5.4 哈夫曼樹

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計哈夫曼樹的相關(guān)概念哈夫曼算法哈夫曼編碼5.4哈夫曼樹路徑若樹中存在某個節(jié)點(diǎn)序列k1,k2,…,kj滿足Ki是ki+1的雙親則該節(jié)點(diǎn)序列是樹上的一條路徑路徑長度路徑經(jīng)過的邊數(shù)，稱為路徑長度樹的路徑長度從樹根到樹中每一個節(jié)點(diǎn)的路徑長度之和哈夫曼樹的相關(guān)概念節(jié)點(diǎn)的權(quán)給樹的節(jié)點(diǎn)賦以一定意義的數(shù)值，稱為節(jié)點(diǎn)的權(quán)節(jié)點(diǎn)的帶權(quán)路徑長度從樹根到某節(jié)點(diǎn)的路徑長度與該節(jié)點(diǎn)的權(quán)的積樹的帶權(quán)路徑長度（WPL）

樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和哈夫曼樹相關(guān)概念2357例：4個節(jié)點(diǎn)的權(quán)值分別為2，3，5，7。以下是以它們?yōu)槿~子節(jié)點(diǎn)構(gòu)造二叉樹，計算各二叉樹的帶權(quán)路徑長度WPL。WPL=2*3+3*3+5*2+7*1=32WPL=2*2+3*2+5*2+7*2=34WPL=2*1+3*2+5*3+7*3=44由n個帶權(quán)葉子節(jié)點(diǎn)構(gòu)成的二叉樹具有不同形態(tài)其中帶權(quán)路徑長度（WPL）最小的二叉樹又叫最優(yōu)二叉樹，或最佳判定樹哈夫曼樹的概念最佳判定樹以各分?jǐn)?shù)段人數(shù)的比例為權(quán)值構(gòu)造最佳判定樹使得大部分?jǐn)?shù)據(jù)經(jīng)過較少次數(shù)的比較得到結(jié)果最佳判定樹構(gòu)造哈夫曼樹的方法——哈夫曼算法根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根節(jié)點(diǎn)的二叉樹，令其權(quán)值為分別wj在森林中選取兩棵根節(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹置新二叉樹根節(jié)點(diǎn)權(quán)值為其左右子樹根節(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹，并將新得到的二叉樹加入森林中重復(fù)上述步驟，直到只含一棵樹為止這棵樹即哈夫曼樹哈夫曼算法例：已知權(quán)值集合{2，4，6，7，8}，構(gòu)造哈夫曼樹。哈夫曼編碼電報通訊中，電文以二進(jìn)制的0,1序列傳送發(fā)送端將電文中的字符轉(zhuǎn)換成0,1的二進(jìn)制序列接收端將收到的0,1序列轉(zhuǎn)換成對應(yīng)的字符序列(譯碼)假定電文是英文，電文字符串由26個英文字母組成，需要編碼的字符集是{A,B,C,D,…,Z}方法一：等長的二進(jìn)制編碼方法二：不等長的二進(jìn)制編碼

A:010B:0101C:01011前綴碼任一字符的編碼，不能是其他字符的前綴哈夫曼編碼假設(shè)字符集D={d1,d2,d3,…,dn}每個字符di的編碼長度為li每個字符di在電文中出現(xiàn)的次數(shù)是ci

則電文的總長度為:∑ci*li每個字符di在電文中出現(xiàn)頻度的概率是wi

每個字符di的編碼長度為li則電文的平均總長度為:∑wi*li

哈夫曼編碼尋找最優(yōu)前綴碼的方法用d1,d2,d3,…,dn作為葉子節(jié)點(diǎn)用w1,w2,w3,…,wn作為葉子節(jié)點(diǎn)的權(quán)構(gòu)造最優(yōu)二叉樹將樹中每個節(jié)點(diǎn)的左分支置為0，右分支置為1從根到葉子節(jié)點(diǎn)的一個標(biāo)號序列，就是該葉子節(jié)點(diǎn)的編碼例：設(shè)某語言有ABCDEF六種字母，出現(xiàn)的概率分別為0.11，0.12，0.13，0.15，0.22，0.27。A：0