摘要: 霍夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮技術(shù)，根據(jù)待壓縮數(shù)據(jù)的特征，一個可壓縮掉20%~90%。這里考慮的數(shù)據(jù)指的是字符串序列。要理解霍夫曼編碼，先要理解霍夫曼樹，即最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹。

路徑是指從樹中一個結(jié)點到另一個結(jié)點之間的通路，路徑上的分支數(shù)目稱為路徑長度。

樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。結(jié)點的帶權(quán)路徑長度為從該結(jié)點到樹根之間的路徑長度與該結(jié)點權(quán)的乘積，樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和.

霍夫曼樹是指所有葉子結(jié)點的二叉樹中帶權(quán)路徑長度最小的二叉樹.

當(dāng)給定了n個葉子結(jié)點的權(quán)值后，構(gòu)造出的最優(yōu)二叉樹的結(jié)點數(shù)目m就確定了，即m=2n-1,所以可用一維結(jié)構(gòu)樹組來存儲最優(yōu)二叉樹
  閱讀全文