數(shù)據(jù)結(jié)構(gòu)課件:第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件:第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件:第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件:第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件:第6章 樹和二叉樹4赫夫曼樹及其應(yīng)用_第5頁(yè)
已閱讀5頁(yè),還剩22頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、樹和森林第6章 樹和二叉樹樹的基本概念二叉樹遍歷二叉樹和線索二叉樹赫夫曼樹及其應(yīng)用基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用路 徑路徑長(zhǎng)度樹的路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度霍 夫 曼 樹基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用DABCEFG路徑:由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑長(zhǎng)度:路徑上的分支數(shù)目ae的路徑長(zhǎng)度2樹的路徑長(zhǎng)度:從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和樹長(zhǎng)度10基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用DABCEFG結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度:結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度:樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和3798結(jié)點(diǎn)F的路徑長(zhǎng)度為2,其W

2、PL=29=18其中n表示葉子結(jié)點(diǎn)的數(shù)目wi表示葉子結(jié)點(diǎn)ki的權(quán)值li表示根到ki之間的路徑長(zhǎng)度基本術(shù)語(yǔ)6.5 赫夫曼(Huffman)樹及其應(yīng)用赫夫曼樹:帶權(quán)路徑長(zhǎng)度最小的樹, 又稱最優(yōu)二叉樹樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算?Weighted Path Length例:有四個(gè)葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)為7, 5, 2, 4,由它們構(gòu)成三棵不同的二叉樹6.5 赫夫曼(Huffman)樹及其應(yīng)用abdc7524cdab2457bdac7524WPL=36WPL=46WPL= 35Huffman樹構(gòu)造最優(yōu)樹(赫夫曼算法)6.5 赫夫曼(Huffman)樹及其應(yīng)用(1) 由給定的 n 個(gè)權(quán)值w0, w

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

4、7562977562977135629771316第五步:562977131629第一步:5629第二步:第三步:第四步:75629775629779716第五步:57269716132913562713第一步:56297572697161329562977131629判定樹 (赫夫曼樹的應(yīng)用之一)6.5 赫夫曼(Huffman)樹及其應(yīng)用分?jǐn)?shù)0596069707980899099比例0.050.150.40.30.1a60 a70 a80 a90 不及格 中等 良好 優(yōu)秀 及格YNYNYNYN輸入10000個(gè)數(shù)據(jù),則需進(jìn)行31500次比較。判定樹 (赫夫曼樹的應(yīng)用之一)6.5 赫夫曼(Huf

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論