Huffman編碼樹_第1頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、huffman編碼樹先容易回顧一下哈夫曼二叉樹的概念:哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中全部的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為wpl=(w1*l1+w2*l2+w3*l3+.+ wn*ln)，n個權值wi(i=1,2,.n)構成一棵有n個葉結點的二叉樹，相應的葉結點的路徑長度為li(i=1,2,.n)。可以證實哈夫曼樹的wpl是最小的。 構造哈夫曼樹的算法如下： 1）對給定的n個權值w1,w2,w3,.,wi,.,wn構成n棵二叉樹的初始集合f=t1,t2,t

2、3,.,ti,., tn，其中每棵二叉樹ti中惟獨一個權值為wi的根結點，它的左右子樹均為空。 2）在f中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。 3）從f中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序羅列加入到集合f中。 4）重復2）和3），直到集合f中惟獨一棵二叉樹為止。 下面舉一個很一般的例子: 對于權2,3,5,7,11,13,17,19,23,29,31,37,41,求具有最小帶權外部路徑長度的二叉樹. 1 找到最小權值和次小權值2和3,然后2+3=5構成兩個節點的父母,并將5作為下次合并的新權值; 5 / 2 3

3、2 此時權值更新為5,5,7,11,13,17,19,23,29,31,37,41;然后根據1 的模式找到5和5 并產生其父母10，并作為下次合并的新權值; 10 / 5 5 / 2 3 3 同理 10,7,11,13,17,19,23,29,31,37,41； 17 / 7 10 / 5 5 / 2 3 4 17，11,13,17,19,23,29,31,37,41； 此時注重最小數和次小樹不再是前兩位，所以要另起一棵樹,由11 和13構成； 17 / 7 10 24 / / 5 5 11 13 / 2 3 5 好了依次比到最后: 17,17,24,19,23,29,31,37,41； 19,24,23,29,31,34,37,41; 24,29,31,34,37,41,42; 31,34,37,41,42,53; 37,41,42,53,65; 42,53,65,78; 65,78,95; 95,143; 238; 完整的樹圖： 238 / 95 143 / / 42 53 65 78 / / / / 19 23 24 29 31 34 37 41 / / 11 13 17 17 / 7 10 / 5 5 / 2

溫馨提示

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

評論

0/150

提交評論