1、背景知識
1、路徑和路徑長度
在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。
2、結點的權及帶權路徑長度
若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
3、樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。
4、哈夫曼樹
若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
2、哈夫曼算法
為了構造權值集合為{w1, w2, …, wn}的哈夫曼樹，哈夫曼提出了一個構造算法，這個算法就是哈夫曼算法。基本思路如下：
(1)根據給定的n個權值{w1, w2, …, wn}，構造具有n棵擴充二叉樹的森林F = {T1, T2, T3, …, Tn}，其中每棵擴充二叉樹Ti隻有一個帶權值wi的根結點，其左右子樹均為空。
(2)重複以下步驟，直到F中隻剩下一棵樹為止。
①在F中選取兩棵根結點的權值最小的子樹分别作為左右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左右子樹上根結點權值之和。
②在F中删去這兩棵二叉樹。
③把新的二叉樹加入F。
最後得到的就是哈夫曼樹。
下圖是哈夫曼樹構造的圖解過程：
注：從哈夫曼算法可知，實際上構造出來的哈夫曼樹可以不止一棵。
3、哈夫曼樹的結點表示
這裡用C++中的結構類型描述哈夫曼樹中的結點
template<typename T>
struct HTNode
{
T data; //結點值
double weight; //權值
int parent; //雙親結點
int rchild, lchild; //左右孩子結點
};
此處将lchild、rchild、parent依舊稱為”指針”，他們實際上是三個整形訓示器，分别訓示結點在數組中的下标。因為C++語言數組的下界是0，故用-1來表示空指針。設定 parent 域有兩個作用，其一是便于查找某個結點的雙親，其二是可通過判斷parent的值是否為-1來區分根結點和非根結點。
4、算法實作
哈夫曼算法的初始狀态是一個初始森林，共有n課二叉樹。同時每一次的合并，都會産生一個新結點，合并 n - 1 次共産生 n - 1 個新結點，他們都是具有兩個孩子的分支結點。是以最終求得的哈夫曼樹共有2n-1個結點。是以可以用大小為2n-1的一維數組來存放哈夫曼樹中的結點，其存儲結構如下：
const int N = ; //葉子的最多數目
const int M = * N - ; //樹中結點的總數
template <typename T>
class huffmantree
{
public:
huffmantree(HTNode<T> ht[], int n);
~huffmantree();
private:
HTNode<T> HT[M + 1];
};
用ht[]數組存放哈夫曼樹，對于具有 n 個葉子結點的哈夫曼樹，總共有 2n - 1 個結點。其算法的基本思路是，n 個葉子結點（存放在 ht[0] ~ ht[n - 1] 中）隻有data和weight域值，先将所有 2n - 1個結點的parent、rchild、lchild域置初值為 -1 。處理每個非葉子結點ht[i](存放在 ht[n] ~ ht[2n - 2]中)如下：從 ht[0] ~ ht[i - 2] 中找出根結點（即其parent域為-1）最小的兩個結點ht[lnode]和ht[rnode]，将他們作為 ht[i]的左右子樹，ht[lnode]和ht[rnode]的雙親結點置為ht[i]，并且ht[i].weight = ht[lnode].weight + ht[rnode].weight。如此操作直到所有2n - 1 個非葉子結點處理完畢。具體算法如下：
template<typename T>
huffmantree::huffmantree(HTNode<T> ht[], int n) {
int i, k, lnode, rnode;
int min1, min2;
for (i = ; i < 2 * n - 1; ++i)
ht[i].parent = ht[i].lchild = ht[i].rchild = -;
for (i = n; i < 2 * n - 1; ++i) { //構造哈夫曼樹
min1 = min2 = ;
lnode = rnode = -;
for (k = ; k <= i - 1; ++k) {
if (ht[k].parent == -) { //隻在尚未構造二叉樹的結點中查找
if (ht[k].weight < min1) {
min2 = min1;
rnode = lnode;
min1 = ht[k].weight;
lnode = k;
} else if (ht[k].weight < min2) {
min2 = ht[k].weight;
rnode = k;
}
}
}
ht[lnode].parent = ht[rnode].parent = i;
ht[i].weight = ht[lnode].weight + ht[rnode].weight;
ht[i].lchild = lnode;
ht[i].rchild = rnode;
}
for (i = ; i < 2 * n - 1; ++i) {
HT[i].data = ht[i].data;
HT[i].weight = ht[i].weight;
HT[i].parent = ht[i].parent;
HT[i].rchild = ht[i].rchild;
HT[i].lchild = ht[i].lchild;
}
}
5、哈夫曼編碼
哈夫曼樹最經典的應用是在通信領域。經哈夫曼編碼的資訊消除了備援資料，極大地提高了通信信道的傳輸效率。
1、介紹
哈夫曼編碼是根據每個符号出現的頻率，将其存儲的定長編碼轉換成變長編碼。為出現機率較高的字元指定較短的碼字，而為出現機率較低的字元指定較長的碼字，可以明顯提高傳輸的平均性能。
表：哈夫曼編碼
| 符号 | 機率 | 定長編碼 | 變長編碼 |
|---|---|---|---|
| a | 0.12 | 000 | 1111 |
| b | 0.40 | 001 | |
| c | 0.15 | 010 | 110 |
| d | 0.08 | 011 | 1110 |
| e | 0.25 | 100 | 10 |
表中的兩種二進制編碼可以用二叉樹表示，如圖，其中，二叉樹的葉結點标記字元，由根結點沿着二叉樹路徑下行，左分支标記為0，右分支标記為1，則每條從根結點到葉結點的路徑唯一表示了該葉結點的二進制編碼。
圖：兩種編碼方案的二叉樹示意圖
平均編碼長度最小的編碼稱為最優編碼。哈夫曼樹的權重路徑長度就是相應編碼的平均編碼長度。我們稱這樣得到的編碼為哈夫曼編碼。根據前面介紹的哈夫曼樹的性質，我們知道哈夫曼編碼是最優的二進制編碼。
2、讨論實作哈夫曼編碼的算法
實作哈夫曼編碼的算法可以分為兩個部分：
（1）構造哈夫曼樹，此算法在前面已給出。
（2）在哈夫曼樹上求葉結點的編碼。
求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉結點開始，沿葉結點的雙親鍊域回退到根結點，每回退一步，就走過了哈夫曼樹的一個分支，進而得到一位哈夫曼編碼值，由于一個字元的哈夫曼編碼是從根結點到相應葉結點所經過的路徑上各分支所組成的”0”、”1”序列，是以先得到的分支代碼為所求的編碼的低位碼，後得到的分支代碼為所求編碼的高位碼，可以設定數組HuffmanCode用來存放各個字元的哈夫曼資訊。
3、代碼實作
//接着上面的哈夫曼樹類定義
struct HCode
{
char cd[n]; //n為層數減一
int start; //cd[start] ~ cd[n]存放目前結點的哈夫曼碼
};
template <typename T>
void huffmantree<T>::CreateHCode(HCode hcd[], int n) {
int i, f, c;
HCode hc;
for (i = ; i < n; ++i) { //根據哈夫曼樹求哈夫曼編碼
hc.start = n;
c = i;
f = HT[i].parent;
while (f != -) { //循環直到樹根結點
if (HT[f].lchild == c) //處理左孩子結點
hc.cd[hc.start--] = '0';
else
hc.cd[hc.start--] = '1'; //處理右孩子結點
c = f;
f = HT[f].parent;
}
hc.start++; //start指向哈夫曼編碼的最開始字元
hcd[i] = hc;
}
}