摘要: 霍夫曼編碼是一種被廣泛應用而且非常有效的數據壓縮技術，根據待壓縮數據的特征，一個可壓縮掉20%~90%。這里考慮的數據指的是字符串序列。要理解霍夫曼編碼，先要理解霍夫曼樹，即最優二叉樹，是一類帶權路徑長度最短的樹。
路徑是指從樹中一個結點到另一個結點之間的通路，路徑上的分支數目稱為路徑長度。
樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。結點的帶權路徑長度為從該結點到樹根之間的路徑長度與該結點權的乘積，樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和.
霍夫曼樹是指所有葉子結點的二叉樹中帶權路徑長度最小的二叉樹.
當給定了n個葉子結點的權值后，構造出的最優二叉樹的結點數目m就確定了，即m=2n-1,所以可用一維結構樹組來存儲最優二叉樹
閱讀全文