6tree

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

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

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

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

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

6、 }(2)F = { },13,(3)F = { }(4)F = { },14,赫夫曼樹(shù)及其應(yīng)用,理解為什么赫夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度最??？它把權(quán)值小的結(jié)點(diǎn)放在底層權(quán)值大的結(jié)點(diǎn)放在上層,15,赫夫曼樹(shù)的應(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è)計(jì)這些字符的二進(jìn)制編碼，以使通信中總碼長(zhǎng)盡可能短？方案一：固定長(zhǎng)度編碼8個(gè)字符，只需要3位二進(jìn)制數(shù)就能表示比如000代表A，001代表B，...111代表H這樣平均每個(gè)字符用3位二進(jìn)制數(shù)表示,16,赫夫曼樹(shù)的應(yīng)用——赫夫曼編碼,方案二：赫夫曼編碼平均每個(gè)字符的編碼長(zhǎ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,赫夫曼樹(shù)的應(yīng)用——赫夫曼編碼,赫夫曼編碼的方法以字符出現(xiàn)頻率為權(quán)值，構(gòu)造赫夫曼樹(shù)左分支表示0，右分支表示1，把從根到葉子的路徑上所有分支構(gòu)成的0,1作為葉子的二進(jìn)制編碼，即為赫夫曼編碼比如A：0110B：10C：1110...,18,赫夫曼樹(shù)的應(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,赫夫曼樹(shù)的應(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,,⑴為赫夫曼樹(shù)的存儲(chǔ)開(kāi)辟空間，含 n 個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)共2n-1 個(gè)結(jié)點(diǎn)；⑵生成 n 個(gè)葉子結(jié)點(diǎn)，使它們的權(quán)值為給定的 n 個(gè)權(quán)值，雙親和左右孩子均為0 ；,20,赫夫曼樹(shù)的應(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é)點(diǎn)中選兩個(gè)　權(quán)值最小的，生成以這兩個(gè)　結(jié)點(diǎn)為左、右孩子的分支結(jié)　點(diǎn)。⑷重復(fù)⑶，直至生成 n-1 個(gè)　分支結(jié)點(diǎn)。,21,赫夫曼樹(shù)的應(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é)點(diǎn)中選兩個(gè)　權(quán)值最小的，生成以這兩個(gè)　結(jié)點(diǎn)為左、右孩子的分支結(jié)　點(diǎn)。⑷重復(fù)⑶，直至生成 n-1 個(gè)　分支結(jié)點(diǎn)。,22,赫夫曼樹(shù)的應(yīng)用——赫夫曼編碼,求出編碼 對(duì)赫夫

13、曼樹(shù)中的每個(gè)葉子結(jié)點(diǎn)，求從根到它的路徑： ⑴ 開(kāi)辟 n 個(gè)存儲(chǔ)空間，用以保存分別指向 n 個(gè)編碼串的指針變量； ⑵ 開(kāi)辟空間，用以暫存當(dāng)前所求編碼串 ⑶ 對(duì)每個(gè)葉子結(jié)點(diǎn)，從該結(jié)點(diǎn)開(kāi)始向根逆向求編碼。,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