哈夫曼編碼運用到了哪一種資料結構

哈夫曼編碼運用到的資料結構為「樹型結構」。在哈夫曼演算法的支持下構造出一棵最優二元樹，我們把這類樹命名為哈夫曼樹。因此，確切地說，哈夫曼編碼是在哈夫曼樹的基礎之上建構出來的一種編碼形式。

本教學操作環境：windows7系統、Dell G3電腦。

哈夫曼編碼運用到的資料結構為「樹型結構」。

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

哈夫曼編碼借助了資料結構當中的樹型結構，在哈夫曼演算法的支持下構造出一棵最優二元樹，我們把這類樹命名為哈夫曼樹。因此，確切地說，哈夫曼編碼是在哈夫曼樹的基礎上建構出來的一種編碼形式，它的本身有著非常廣泛的應用。

哈夫曼樹

給定N權值作為N個葉子結點，建構一棵二元樹，若該樹的權限路徑長度達到最小，稱這樣的二元樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度總和，記為WPL=（W1*L1 W2*L2 W3*L3 ... Wn*Ln），N權值Wi（i=1 ,2,...n）構成一棵有N個葉結點的二元樹，對應的葉結點的路徑長度為Li（i=1,2,...n）。可以證明哈夫曼樹的WPL是最小的。

想要查閱更多相關文章，請造訪PHP中文網！ ！

以上是哈夫曼編碼運用到了哪一種資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！