資料結構哈夫曼樹

　　資料結構哈夫曼樹是由德國數學家馮·哈夫曼發現的，又稱為最優二叉樹，是一種帶權路徑長最短的樹結構。哈夫曼樹的特點是引出的路程最短，哈夫曼樹的形狀是單支形式，對於程式設計具有重大的意義，使某些很難完成的任務變得簡單，可以有條理的完成。樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和，節點的帶樹路徑長度為從該節點到樹根之間的路徑長度與該節點權的乘積。

　　哈夫曼樹不唯一，因為沒有限定左右子樹，並且有權值重複時，可能樹的高度都不唯一，唯一的只是帶權路徑長度之和最小。

　　哈夫曼樹(Huffman)樹又稱最優二叉樹，是指對於一組帶有確定權值的葉子結點所構造的具有帶權路徑長度最短的二叉樹。從樹中一個結點到另一個結點之間的分支構成了兩結點之間的路徑，路徑上的分支個數稱為路徑長度。二叉樹的路徑長度是指由根結點到所有葉子結點的路徑長度之和。如果二叉樹中的葉子結點都有一定的權值，則可將這一概念。

　　設二叉樹具有n個帶權值的葉子結點，則從根結點到每一個葉子結點的路徑長度與該葉子結點權值的乘積之和稱為二叉樹路徑長度，記做：WPL=W1L1+W2L2+WnLn等等；其中：n為二叉樹中葉子結點的個數；Wk為第k個葉子的權值；Lk為第k個葉子結點的路徑長度。

　　由哈夫曼樹的生成過程可得如下性質：

　　1、給定權值的哈夫曼樹不唯一，但是最小的二叉樹，為定值。

　　2、權值越大的節點離根節點就越近。

　　3、哈夫曼樹中無度的節點。

　　4、左子樹上所有的結點的資料值均小於根結點的資料值，右子樹上所有的結點的資料值均大於或等於根結點的資料值。