1. 樹的帶權(quán)路徑長(zhǎng)度

設(shè)二叉樹具有 n 個(gè)帶權(quán)葉結(jié)點(diǎn)，從根結(jié)點(diǎn)到各葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉節(jié)點(diǎn)權(quán)值的乘積之和稱為 樹的帶權(quán)路徑長(zhǎng)度（Weighted Path Length of Tree，WPL）。

設(shè)為二叉樹第 i 個(gè)葉結(jié)點(diǎn)的權(quán)值，為從根結(jié)點(diǎn)到第 i 個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度，則WPL計(jì)算公式如下：

如上圖所示，其 WPL 計(jì)算過(guò)程與結(jié)果如下：

2. 結(jié)構(gòu)

對(duì)于給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹，其中，WPL 最小的二叉樹稱為霍夫曼樹（Huffman Tree）。

對(duì)于霍夫曼樹來(lái)說(shuō)，其葉結(jié)點(diǎn)權(quán)值越小，離根越遠(yuǎn)，葉結(jié)點(diǎn)權(quán)值越大，離根越近，此外其僅有葉結(jié)點(diǎn)的度為 0，其他結(jié)點(diǎn)度均為 2。

3. 霍夫曼算法

霍夫曼算法用于構(gòu)造一棵霍夫曼樹，算法步驟如下：

（1）初始化：由給定的 n 個(gè)權(quán)值構(gòu)造 n 棵只有一個(gè)根節(jié)點(diǎn)的二叉樹，得到一個(gè)二叉樹集合F

（2）選取與合并：從二叉樹集合F中選取根節(jié)點(diǎn)權(quán)值最小的兩棵二叉樹分別作為左右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根節(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值和。

（3）刪除與加入：從F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F。

（4）重復(fù) 2、3 步，當(dāng)集合中只剩下一棵二叉樹時(shí)，這棵二叉樹就是霍夫曼樹。

4. 霍夫曼編碼

在進(jìn)行程序設(shè)計(jì)時(shí)，通常給每一個(gè)字符標(biāo)記一個(gè)單獨(dú)的代碼來(lái)表示一組字符，即編碼。

在進(jìn)行二進(jìn)制編碼時(shí)，假設(shè)所有的代碼都等長(zhǎng)，那么表示 n 個(gè)不同的字符需要位，稱為等長(zhǎng)編碼。

如果每個(gè)字符的使用頻率相等，那么等長(zhǎng)編碼無(wú)疑是空間效率最高的編碼方法，而如果字符出現(xiàn)的頻率不同，則可以讓頻率高的字符采用盡可能短的編碼，頻率低的字符采用盡可能長(zhǎng)的編碼，來(lái)構(gòu)造出一種 不等長(zhǎng)編碼，從而獲得更好的空間效率。

在設(shè)計(jì)不等長(zhǎng)編碼時(shí)，要考慮解碼的唯一性，如果一組編碼中任一編碼都不是其他任何一個(gè)編碼的前綴，那么稱這組編碼為前綴編碼，其保證了編碼被解碼時(shí)的唯一性。

霍夫曼樹可用于構(gòu)造最短的前綴編碼，即霍夫曼編碼（Huffman Code），其構(gòu)造步驟如下：

（1）設(shè)需要編碼的字符集為：，他們?cè)谧址谐霈F(xiàn)的頻率為：。

（2）以作為葉結(jié)點(diǎn)，作為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵霍夫曼樹。

（3）規(guī)定哈夫曼編碼樹的左分支代表 0，右分支代表 1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的路徑組成的 0、1序列即為該葉結(jié)點(diǎn)對(duì)應(yīng)字符的編碼。