6tree

1、1,赫夫曼樹及其應(yīng)用,路徑從一個結(jié)點到另一個結(jié)點的分支構(gòu)成路徑長度路徑上的分支的個數(shù)樹的路徑長度從樹根到每一個結(jié)點的路徑長度之和,2,赫夫曼樹及其應(yīng)用,以下我們只討論二叉樹問題：樹的路徑長度最短的是哪一種？完全二叉樹,3,赫夫曼樹及其應(yīng)用,權(quán)(weight)給結(jié)點賦予一定的數(shù)值結(jié)點的帶權(quán)路徑長度從樹根到該節(jié)點的路徑長度×該結(jié)點的權(quán)樹的帶權(quán)路徑長度Weighted Path Length所有葉結(jié)點

2、的帶權(quán)路徑長度之和WPL =,4,赫夫曼樹及其應(yīng)用,例,5,赫夫曼樹及其應(yīng)用,最優(yōu)二叉樹又稱赫夫曼樹(Huffman)有n個權(quán)值{w1,w2,...,wn}構(gòu)造一棵有n個葉結(jié)點的二叉樹每個葉結(jié)點的權(quán)值為wi其中WPL最小的那一棵稱作最優(yōu)二叉樹，即赫夫曼樹最優(yōu)又能怎樣？,6,赫夫曼樹及其應(yīng)用,例一個判斷成績等級的程序if(a < 60) b = “不及格”else if(a < 70) b = “及格

3、” else if(a < 80) b = “中等” else if(a < 90) b = “良好” else b = “優(yōu)秀”一個a最多要經(jīng)過4次比較才能得出b我們當然希望比較的總次數(shù)最小,7,假設(shè)有如下統(tǒng)計數(shù)據(jù)原判定樹為：,8,若一共有10000個輸入數(shù)據(jù)則總共的比較次數(shù)= 500*1 + 1500*2 + 4000*3 + 3000*4 +

4、1000*4 = 31500,9,構(gòu)造一棵赫夫曼樹有5個葉結(jié)點，權(quán)值分別為：0.05, 0.15, 0.4, 0.3, 0.1,10,根據(jù)這棵赫夫曼樹導(dǎo)出新的判定樹：總的比較次數(shù)= 500*3 + 1500*3 + 4000*2 + 3000*2 + 1000*2= 22000,11,赫夫曼樹及其應(yīng)用,赫夫曼樹的構(gòu)造算法(1)根據(jù)給定的n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,

5、…,Tn}，其中每棵二叉樹只含一個帶權(quán)的根結(jié)點，其左右子樹均空(2)在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和(3)在F中刪除這兩棵二叉樹，同時將新得到的二叉樹加入F(4)重復(fù)(2)和(3)，直到F只含一棵二叉樹,12,赫夫曼樹及其應(yīng)用,例：設(shè)結(jié)點a,b,c,d的權(quán)值分別為7,5,2,4，試構(gòu)造赫夫曼樹(1)F = {

6、 }(2)F = { },13,(3)F = { }(4)F = { },14,赫夫曼樹及其應(yīng)用,理解為什么赫夫曼樹的帶權(quán)路徑長度最?。克褭?quán)值小的結(jié)點放在底層權(quán)值大的結(jié)點放在上層,15,赫夫曼樹的應(yīng)用——赫夫曼編碼,例某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符(A,B,C,D,E,F,G,H)，其使用概率分別為0.05、0.29、0.07、0.08、0.14

7、、0.23、0.03、0.11，如何設(shè)計這些字符的二進制編碼，以使通信中總碼長盡可能短？方案一：固定長度編碼8個字符，只需要3位二進制數(shù)就能表示比如000代表A，001代表B，...111代表H這樣平均每個字符用3位二進制數(shù)表示,16,赫夫曼樹的應(yīng)用——赫夫曼編碼,方案二：赫夫曼編碼平均每個字符的編碼長度= 4*0.05 + 2*0.29 + 4*0.07 + 4*0.08 + 3*0.14 + 2*0.23 +

8、 4*0.03 + 3*0.11= 2.71,17,赫夫曼樹的應(yīng)用——赫夫曼編碼,赫夫曼編碼的方法以字符出現(xiàn)頻率為權(quán)值，構(gòu)造赫夫曼樹左分支表示0，右分支表示1，把從根到葉子的路徑上所有分支構(gòu)成的0,1作為葉子的二進制編碼，即為赫夫曼編碼比如A：0110B：10C：1110...,18,赫夫曼樹的應(yīng)用——赫夫曼編碼,【數(shù)據(jù)結(jié)構(gòu)】typedef struct{　unsigned weight;　unsig

9、ned p;　unsigned lc;　unsigned rc;}HTNode,*HuffmanTree;typedef char * *HuffmanCode;,19,赫夫曼樹的應(yīng)用——赫夫曼編碼,,,,,,15,,,,,14,,,,,13,,,,,12,,,,,11,,,,,10,,,,,9,0,0,0,11,8,0,0,0,3,7,0,0,0,23,6,0,0,0,14,5,0,0,0,8,4,0,0,0,7,3,0,0

10、,0,29,2,0,0,0,5,1,,,,,0,rc,lc,p,weight,,HT,,⑴為赫夫曼樹的存儲開辟空間，含 n 個葉子結(jié)點的赫夫曼樹共2n-1 個結(jié)點；⑵生成 n 個葉子結(jié)點，使它們的權(quán)值為給定的 n 個權(quán)值，雙親和左右孩子均為0 ；,20,赫夫曼樹的應(yīng)用——赫夫曼編碼,,,,,,15,,,,,14,,,,,13,,,,,12,,,,,11,,,,,10,7,1,0,8,9,0,0,0,11,8,0,0,9,3,7,0,0

11、,0,23,6,0,0,0,14,5,0,0,0,8,4,0,0,0,7,3,0,0,0,29,2,0,0,9,5,1,,,,,0,rc,lc,p,weight,,HT,,⑶在雙親為０的結(jié)點中選兩個　權(quán)值最小的，生成以這兩個　結(jié)點為左、右孩子的分支結(jié)　點。⑷重復(fù)⑶，直至生成 n-1 個　分支結(jié)點。,21,赫夫曼樹的應(yīng)用——赫夫曼編碼,,,,,,15,,,,,14,,,,,13,,,,,12,,,,,11,4,3,0,15,10

12、,7,1,0,8,9,0,0,0,11,8,0,0,9,3,7,0,0,0,23,6,0,0,0,14,5,0,0,10,8,4,0,0,10,7,3,0,0,0,29,2,0,0,9,5,1,,,,,0,rc,lc,p,weight,,HT,,⑶在雙親為０的結(jié)點中選兩個　權(quán)值最小的，生成以這兩個　結(jié)點為左、右孩子的分支結(jié)　點。⑷重復(fù)⑶，直至生成 n-1 個　分支結(jié)點。,22,赫夫曼樹的應(yīng)用——赫夫曼編碼,求出編碼 對赫夫

13、曼樹中的每個葉子結(jié)點，求從根到它的路徑： ⑴ 開辟 n 個存儲空間，用以保存分別指向 n 個編碼串的指針變量； ⑵ 開辟空間，用以暫存當前所求編碼串 ⑶ 對每個葉子結(jié)點，從該結(jié)點開始向根逆向求編碼。,23,,,12,2,15,58,14,6,11,15,42,13,10,5,14,29,12,8,9,13,19,11,4,3,12,15,10,1,7,11,8,9,0,0,11,11,8,0,0,9,3,7,0,0,13,23,6