哈夫曼樹的構(gòu)造：就是將給定的數(shù)據(jù)中選擇最小的兩個權值進行合并，然后重復該操作，構(gòu)造出一個二叉樹。使其帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。
例如：給定幾個數(shù)值：0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.01
可以將其擴大一百倍，以方便計算，不會影響哈夫曼樹的構(gòu)造
W={7, 19, 2, 6, 32, 3, 21, 10}
選擇最小的2，3進行合并為5，5 和 6 為最小的再進行合并為 11 ， 重復該操作可以得到該哈夫曼樹。
哈夫曼編碼：
在進行數(shù)據(jù)壓縮的時候，為了使壓縮后的數(shù)據(jù)文件盡可能短，可采用不定長編碼。其基本思想是：為出現(xiàn)次數(shù)較多的字符編以較短的編碼。為確保對數(shù)據(jù)文件進行有效的壓縮和對壓縮文件進行正確的解碼，可以利用哈夫曼樹來設計二進制編碼。
編碼的概念：
（1）前綴編碼：如果在一個編碼方案中，任何一個編碼都不是其他任何編碼的前綴（最左子串），則稱編碼是前綴編碼。00，001這個就不是前綴編碼。其實就是通過這些編碼準確得出數(shù)據(jù)信息，不會混淆。
（2）哈夫曼編碼：對一棵具有n個葉子的哈夫曼樹，若對樹中的每個左分支賦予0，右分支賦予1，則從根到每個葉子的路徑上，各個支的賦值分別構(gòu)成一個二進制，該二進制就稱為哈夫曼編碼
哈夫曼編碼性質(zhì)：
（1）哈夫曼編碼是前綴編碼
（2）哈夫曼編碼是最優(yōu)前綴編碼
| 字母編號 | 出現(xiàn)頻率 | 哈夫曼編碼 | 等長編碼 |
| 1 | 0.07 | 1100 | 000 |
| 2 | 0.19 | 00 | 001 |
| 3 | 0.02 | 11110 | 010 |
| 4 | 0.06 | 1110 | 011 |
| 5 | 0.32 | 10 | 100 |
| 6 | 0.03 | 11111 | 101 |
| 7 | 0.21 | 01 | 110 |
| 8 | 0.10 | 1101 | 111 |
由上面的例子得出該表
如何得出這個哈夫曼編碼？以0.07擴大一百倍之后是7為例子講解：
從葉子結(jié)點到根節(jié)點：7 ——> 17是左分支，所以賦予0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 17 ——> 28是左分支，所以賦予0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 28 ——> 60是右分支，所以賦予1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 60 ——> 100是右分支，所以賦予1
哈夫曼編碼是從根節(jié)點到葉子結(jié)點：所以0.07的哈夫曼編碼是1100.
等長編碼就相當于一個從根節(jié)點到葉子節(jié)點的路徑為K的滿二叉樹，上面列表就是通過一個從根節(jié)點到葉子節(jié)點的路徑為3的滿二叉樹得來的等長編碼，方法和得到哈夫曼編碼一樣。
以0.07擴大一百倍后為7來講解以下;
?從葉子結(jié)點到根節(jié)點： 7——> 26 是左分支，所以賦予0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 26 ——>34 是左分支，所以賦予0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 34 ——>100是左分支，所以賦予0
等長編碼是從根節(jié)點到葉子結(jié)點，所以等長編碼是000
在對多個有序表進行兩兩合并時，若表長不同，則最壞的情況下總的比較次數(shù)依賴于表的合并次序（歸并排序），可以借助哈夫曼樹的構(gòu)造思想，依次選擇最短的兩個表進行合并，這樣可以獲得最壞的情況下最佳的合并效率?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-455134.html
?文章來源：http://www.zghlxwxcb.cn/news/detail-455134.html
?
到了這里，關于哈夫曼樹與哈夫曼編碼及等長編碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
