哈夫曼（Huffman）編碼是上個世紀五十年代由哈夫曼教授研製開發的， 它借助了資料結構當中的樹型結構， 在哈夫曼演算法的支援下構造出一棵最優二叉樹， 我們把這類樹命名為哈夫曼樹。 因此， 準確地說， 哈夫曼編碼是在哈夫曼樹的基礎之上構造出來的一種編碼形式， 主要用於資料編碼壓縮， 在多媒體技術、編解碼技術、通信技術等領域有著非常廣泛的應用。
1 通信中的編碼問題通信中的資訊傳輸， 一般都需要進行編碼， 接收方收到後， 按照編碼的逆過程， 再將資訊還原為原來的形式。
最常用的傳播通道是二元通道，
例如， 將傳送的文字轉換成二進位的字串， 用0， 1碼的不同排列來表示字元。 假設需傳送的報文為“AFTER DATA EAR ARE ART AREA”， 這裡用到的字元集為“A， E， R， T， F， D”， 各字母出現的次數為{8， 4， 5， 3， 1， 1}。 現要求為這些字母設計編碼。 要區別6個字母， 最簡單的二進位編碼方式是等長編碼， 固定採用3位元二進位， 可分別用000、001、010、011、100、101對“A， E， R， T， F， D”進行編碼發送， 當對方接收報文時再按照三位元一分進行解碼。 顯然編碼的長度取決報文中不同字元的個數。 若報文中可能出現26個不同字元， 則固定編碼長度為5。 然而， 傳送報文時總是希望總長度盡可能短。 在實際應用中， 各個字元的出現頻度或使用次數是不相同的， 如A、B、C的使用頻率遠遠高於X、Y、Z， 自然會想到設計編碼時，
1951年， 哈夫曼和他在MIT資訊理論的同學需要選擇是完成學期報告還是期末考試。 導師Robert M. Fano給他們的學期報告的題目是， 尋找最有效的二進位編碼。 由於無法證明哪個已有編碼是最有效的， 哈夫曼放棄對已有編碼的研究， 轉向新的探索， 最終發現了基於有序頻率二叉樹編碼的想法， 並很快證明了這個方法是最有效的。 由於這個演算法， 學生終於青出於藍， 超過了他那曾經和資訊理論創立者香農共同研究過類似編碼的導師。 哈夫曼使用自底向上的方法構建二叉樹， 避免了次優演算法Shannon-Fano編碼的最大弊端──自頂向下構建樹。
1952年， Huffman在Proceedings of the I.R.E上發表了“A Method for the Construction of Minimum-Redundancy Codes"（一種構建極小冗餘編碼的方法）一文來闡述這個編碼演算法。
哈夫曼樹， 也就是最優二叉樹， 是帶權路徑長度最小的二叉樹， 經常應用於資料壓縮。
設某二叉樹有m個葉子結點， 每個葉子結點分別賦予一個權值， 用wi表示（i表示第i個結點）， li表示第i個結點的路徑長度。 那麼該二叉樹的帶權路徑長度WPL（Weight Path Length）定義為：
如下面的二叉樹就是兩棵葉子結點賦了權值的二叉樹。
計算上面左圖的二叉樹的帶權路徑長度：
葉子結點權值W={2,8,6,3}
對應結點的路徑長度L={2,3,3,1}
WPL ＝ {2,8,6,3} * {2,3,3,1} =49
如果二權樹的圖形相同， 只是某些葉子結點相互調換權值， 二叉樹的帶權路徑長度會相同通常也會不同：
上面右圖的二叉樹的帶權路徑長度：
葉子結點權值W={8,2,3,6}
對應結點的路徑長度L={2,3,3,1}
WPL ＝ {8,2,3,6} * {2,3,3,1} =37
當然， 同樣的帶權值四個葉子節點{2,8,6,3}， 可以構造不同的樹， 對應的各葉子結點的路徑長度肯定也會不同， 所以二叉樹的帶權路徑長度也會不同。
那現在的問題是， 對於給定的一組權值， 如何構造二叉樹， 使得帶權路徑長度最小？
2.1 將給定的權值按照從小到大的順序排列(w1,w2,…,wn)，
2.2 把森林F中根結點權值最小的兩棵二叉樹T1,T2作為左、右葉子結點合併為一棵新的二叉樹T， 令T的根結點的權值為T1,T2兩個結點的權值之和， 然後將T按照其根結點權值大小加入到森林F中， 同時從F中刪除T1,T2這兩棵二叉樹；
2.3 重複上述2.2步驟， 直到構造出一棵二叉樹為止。
權值四個葉子節點{2,8,6,3}構造的思路可圖示如下：
上圖的二叉樹的帶權路徑長度：
葉子結點權值W={8,6,2,3}
對應結點的路徑長度L={1,2,3,3}
WPL ＝ {8,6,2,3} * {1,2,3,3} =35
按上述思路構造的二叉樹就是哈夫曼樹，根據給定的一組權值，其帶權路徑長度最小。
給定n個帶權值的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
3 哈夫曼編碼利用哈夫曼樹對資料進行二進位編碼稱為哈夫曼編碼。
假設要對字串"this is a test"進行編碼，(t, h, i, s, a, e, 空格)就組成了一個字元集D，各字元重複的頻率組成一組權值W(3, 1, 2, 3, 1, 1, 3)，以該組權值構造一棵哈夫曼樹。從根節點到葉節點di的路徑上，每經過一條左樹枝，取二進位值0，每經過一條右樹枝，取二進位1，於是從根結點到葉結點di的路徑上得到由二進位0和1構成的二進位序列即為字元di對應的哈夫曼編碼。
字元集的哈夫曼編碼為：
字元dithisae空白字元頻率wi3123113編碼10000000011100001000101可以看出，重複頻率越高的字元，其哈夫曼編碼越短。相反，出現次數越少的字元，其編碼越長。這樣就從整體上保證了報文的長度最短。
因為哈夫曼編碼是不等長編碼，即不同字元的編碼長度可能不同，所以必須保證任何一個字元的編碼都不是另一個字元編碼的首碼，這樣當編碼寫到一起時才能正確區分每個字元的編碼，這樣的編碼稱為首碼編碼。由於哈夫曼編碼是基於哈夫曼樹生成的，而代表每個字元的結點都是哈夫葉子結點，不可能出現在從根結點到另一個字元的路徑上，從而保證了哈夫曼編碼一定是首碼編碼。這樣也就避免了解碼過程中的二叉性問題。
哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。
哈夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。
4 哈夫曼編碼是如何來實現資料的壓縮和解壓縮的呢?眾所周知，在電腦當中，資料的存儲和加工都是以位元組作為基本單位的，一個西文字元要通過一個位元組來表達，而一個漢字就要用兩個位元組，我們把這種每一個字元都通過相同的位元組數來表達的編碼形式稱為定長編碼。以西文為例，例如我們要在電腦當中存儲這樣的一句話:I am a teacher。就需要15個位元組，也就是120個二進位位元的資料來實現。與這種定長編碼不同的是，哈夫曼編碼是一種變長編碼。它根據字元出現的概率來構造平均長度最短的編碼。換句話說如果一個字元在一段文檔當中出現的次數多，它的編碼就相應的短，如果一個字元在一段文檔當中出現的次數少，它的編碼就相應的長。當編碼中，各碼字的長度嚴格按照對應符號出現的概率大小進行逆序排列時，則編碼的平均長度是最小的。這就是哈夫曼編碼實現資料壓縮的基本原理。要想得到一段資料的哈夫曼編碼，需要用到三個步驟:第一步:掃描需編碼的資料，統計原資料中各字元出現的概率。第二步:利用得到的概率值創建哈夫曼樹。第三步:對哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
因為定長編碼已經用相同的位元數這個條件保證了任一個字元的編碼都不會成為其它編碼的首碼，所以這種情況只會出現在變長編碼當中，要想避免這種情況，我們就必須用一個條件來制約定長編碼，這個條件就是要想成為壓縮編碼，變長編碼就必須是首碼編碼。什麼是首碼編碼呢?所謂的首碼編碼就是任何一個字元的編碼都不能是另一個字元編碼的首碼。
那麼哈夫曼編碼是否是首碼編碼呢?觀察a、b、c、d構成的編碼樹，可以發現b之所以成為c的首碼，是因為在這棵樹上，b成為了c的父結點，從在哈夫曼樹當中，原文檔中的資料字元全都分佈在這棵哈夫曼樹的葉子位置，從而保證了哈夫曼編碼當中的任何一個字元的編碼都不能是另一個字元編碼的首碼。也就是說哈夫曼編碼是一種首碼編碼，也就保證瞭解壓縮過程當中解碼的準確性。哈夫曼編碼的解壓縮過程也相對簡單，就是將編碼嚴格按照哈夫曼樹進行翻譯就可以了，例如遇到000，就可以順著哈夫曼樹找到I，遇到101就可以順著哈夫曼樹找到空格，以此類推，我們就可以很順利的找到原來所有的字元。哈夫曼編碼是一種一致性編碼，有著非常廣泛的應用，例如在JPEG文件中，就應用了哈夫曼編碼來實現最後一步的壓縮;在數位電視大力發展的今天，哈夫曼編碼成為了視訊訊號的主要壓縮方式。應當說，哈夫曼編碼出現，結束了熵編碼不能實現最短編碼的歷史，也使哈夫曼編碼成為一種非常重要的無損編碼。
哈夫曼方法的最大缺點就是它需要對原始資料進行兩遍掃描:第一遍統計原始資料中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹並將樹的有關資訊保存起來，便於解壓時使用;第二遍則根據前面得到的哈夫曼樹對原始資料進行編碼，並將編碼資訊存儲起來。這樣如果用於網路通信中，將會引起較大的延時；對於檔案壓縮這樣的應用場合，額外的磁片訪間將會降低該演算法的資料壓縮速度。
為使不等長編碼為首碼編碼(即要求一個字元的編碼不能是另一個字元編碼的首碼)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹。為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，於是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進位的首碼編碼，既滿足首碼編碼的條件，又保證報文編碼總長最短。
在圖像壓縮時，霍夫曼編碼的基本方法是先對圖像資料掃描一遍，計算出各種圖元出現的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼後的圖像資料記錄的是每個圖元的碼字，而碼字與實際圖元值的對應關係記錄在碼表中。
5 一個哈夫曼樹的實例
運行效果：
運行效果：
附原碼1：
#include
#include
using namespace std;
//哈夫曼樹的存儲表示
typedef struct
{
int weight; // 權值
int parent, lChild, rChild; // 雙親及左右孩子的下標
}HTNode, *HuffmanTree;
// 選擇權值最小的兩顆樹
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
s1 = s2 = 0;
int i;
for(i = 1; i < n; ++ i){
if(0 == hT[i].parent){
if(0 == s1){
s1 = i;
}
else{
s2 = i;
break;
}
}
}
if(hT[s1].weight > hT[s2].weight){
int t = s1;
s1 = s2;
s2 = t;
}
for(i += 1; i < n; ++ i){
if(0 == hT[i].parent){
if(hT[i].weight < hT[s1].weight){
s2 = s1;
s1 = i;
}else if(hT[i].weight < hT[s2].weight){
s2 = i;
}
}
}
}
// 構造有n個權值（葉子節點）的哈夫曼樹
void CreateHufmanTree(HuffmanTree &hT)
{
int n, m;
cout << "輸入需要構造哈夫曼樹的葉子結點數量，如4："< cin >> n; m = 2*n - 1; hT = new HTNode[m + 1]; // 0號節點不使用 for(int i = 1; i <= m; ++ i){ hT[i].parent = hT[i].lChild = hT[i].rChild = 0; } cout << "輸入權值，如8 6 2 3:" < for(int j = 1; j <= n; ++ j){ cin >> hT[j].weight; // 輸入權值 } hT[0].weight = m; // 用0號節點保存節點數量 /****** 初始化完畢, 創建哈夫曼樹 ******/ for(int k = n + 1; k <= m; ++ k){ int s1, s2; SelectMin(hT, k, s1, s2); hT[s1].parent = hT[s2].parent = k; hT[k].lChild = s1; hT[k].rChild = s2; // 作為新節點的孩子 hT[k].weight = hT[s1].weight + hT[s2].weight; // 新節點為左右孩子節點權值之和 } } int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth) { if(hT[i].lChild == 0 && hT[i].rChild == 0){ return hT[i].weight * deepth; } else{ return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1); } } // 計算WPL（帶權路徑長度） int HuffmanTreeWPL(HuffmanTree hT) { return HuffmanTreeWPL_(hT, hT[0].weight, 0); } // 輸出哈夫曼樹各節點的狀態 void Print(HuffmanTree hT) { cout << "index weight parent lChild rChild" << endl; cout << left; // 左對齊輸出 for(int i = 1, m = hT[0].weight; i <= m; ++ i){ cout << setw(5) << i << " "; cout << setw(6) << hT[i].weight << " "; cout << setw(6) << hT[i].parent << " "; cout << setw(6) << hT[i].lChild << " "; cout << setw(6) << hT[i].rChild << endl; } } // 銷毀哈夫曼樹 void DestoryHuffmanTree(HuffmanTree &hT) { delete[] hT; hT = NULL; } int main() { HuffmanTree hT; CreateHufmanTree(hT); Print(hT); cout << "WPL = " << HuffmanTreeWPL(hT) << endl; DestoryHuffmanTree(hT); system("pause"); return 0; } 附原碼2： #include #include #include #include using namespace std; typedef struct node{ char ch; //存儲該節點表示的字元，只有葉子節點用的到 int val; //記錄該節點的權值 struct node *self,*left,*right; //三個指標，分別用於記錄自己的位址，左孩子的地址和右孩子的地址 friend bool operator <(const node &a,const node &b) //運算子重載，定義優先佇列的比較結構 { return a.val>b.val; //這裡是權值小的優先出佇列 } }node; priority_queue char res[30]; //用於記錄哈夫曼編碼 void dfs(node *root,int level) //列印字元和對應的哈夫曼編碼 { if(root->left==root->right) //葉子節點的左孩子地址一定等於右孩子地址，且一定都為NULL;葉子節點記錄有字元 { if(level==0) //“AAAAA”這種只有一字元的情況 { res[0]='0'; level++; } res[level]='
上圖的二叉樹的帶權路徑長度： 葉子結點權值W={8,6,2,3} 對應結點的路徑長度L={1,2,3,3} WPL ＝ {8,6,2,3} * {1,2,3,3} =35 按上述思路構造的二叉樹就是哈夫曼樹，根據給定的一組權值，其帶權路徑長度最小。 給定n個帶權值的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。 利用哈夫曼樹對資料進行二進位編碼稱為哈夫曼編碼。 假設要對字串"this is a test"進行編碼，(t, h, i, s, a, e, 空格)就組成了一個字元集D，各字元重複的頻率組成一組權值W(3, 1, 2, 3, 1, 1, 3)，以該組權值構造一棵哈夫曼樹。從根節點到葉節點di的路徑上，每經過一條左樹枝，取二進位值0，每經過一條右樹枝，取二進位1，於是從根結點到葉結點di的路徑上得到由二進位0和1構成的二進位序列即為字元di對應的哈夫曼編碼。 字元集的哈夫曼編碼為： 可以看出，重複頻率越高的字元，其哈夫曼編碼越短。相反，出現次數越少的字元，其編碼越長。這樣就從整體上保證了報文的長度最短。 因為哈夫曼編碼是不等長編碼，即不同字元的編碼長度可能不同，所以必須保證任何一個字元的編碼都不是另一個字元編碼的首碼，這樣當編碼寫到一起時才能正確區分每個字元的編碼，這樣的編碼稱為首碼編碼。由於哈夫曼編碼是基於哈夫曼樹生成的，而代表每個字元的結點都是哈夫葉子結點，不可能出現在從根結點到另一個字元的路徑上，從而保證了哈夫曼編碼一定是首碼編碼。這樣也就避免了解碼過程中的二叉性問題。 哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。 哈夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。 眾所周知，在電腦當中，資料的存儲和加工都是以位元組作為基本單位的，一個西文字元要通過一個位元組來表達，而一個漢字就要用兩個位元組，我們把這種每一個字元都通過相同的位元組數來表達的編碼形式稱為定長編碼。以西文為例，例如我們要在電腦當中存儲這樣的一句話:I am a teacher。就需要15個位元組，也就是120個二進位位元的資料來實現。與這種定長編碼不同的是，哈夫曼編碼是一種變長編碼。它根據字元出現的概率來構造平均長度最短的編碼。換句話說如果一個字元在一段文檔當中出現的次數多，它的編碼就相應的短，如果一個字元在一段文檔當中出現的次數少，它的編碼就相應的長。當編碼中，各碼字的長度嚴格按照對應符號出現的概率大小進行逆序排列時，則編碼的平均長度是最小的。這就是哈夫曼編碼實現資料壓縮的基本原理。要想得到一段資料的哈夫曼編碼，需要用到三個步驟:第一步:掃描需編碼的資料，統計原資料中各字元出現的概率。第二步:利用得到的概率值創建哈夫曼樹。第三步:對哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 因為定長編碼已經用相同的位元數這個條件保證了任一個字元的編碼都不會成為其它編碼的首碼，所以這種情況只會出現在變長編碼當中，要想避免這種情況，我們就必須用一個條件來制約定長編碼，這個條件就是要想成為壓縮編碼，變長編碼就必須是首碼編碼。什麼是首碼編碼呢?所謂的首碼編碼就是任何一個字元的編碼都不能是另一個字元編碼的首碼。 那麼哈夫曼編碼是否是首碼編碼呢?觀察a、b、c、d構成的編碼樹，可以發現b之所以成為c的首碼，是因為在這棵樹上，b成為了c的父結點，從在哈夫曼樹當中，原文檔中的資料字元全都分佈在這棵哈夫曼樹的葉子位置，從而保證了哈夫曼編碼當中的任何一個字元的編碼都不能是另一個字元編碼的首碼。也就是說哈夫曼編碼是一種首碼編碼，也就保證瞭解壓縮過程當中解碼的準確性。哈夫曼編碼的解壓縮過程也相對簡單，就是將編碼嚴格按照哈夫曼樹進行翻譯就可以了，例如遇到000，就可以順著哈夫曼樹找到I，遇到101就可以順著哈夫曼樹找到空格，以此類推，我們就可以很順利的找到原來所有的字元。哈夫曼編碼是一種一致性編碼，有著非常廣泛的應用，例如在JPEG文件中，就應用了哈夫曼編碼來實現最後一步的壓縮;在數位電視大力發展的今天，哈夫曼編碼成為了視訊訊號的主要壓縮方式。應當說，哈夫曼編碼出現，結束了熵編碼不能實現最短編碼的歷史，也使哈夫曼編碼成為一種非常重要的無損編碼。 哈夫曼方法的最大缺點就是它需要對原始資料進行兩遍掃描:第一遍統計原始資料中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹並將樹的有關資訊保存起來，便於解壓時使用;第二遍則根據前面得到的哈夫曼樹對原始資料進行編碼，並將編碼資訊存儲起來。這樣如果用於網路通信中，將會引起較大的延時；對於檔案壓縮這樣的應用場合，額外的磁片訪間將會降低該演算法的資料壓縮速度。 為使不等長編碼為首碼編碼(即要求一個字元的編碼不能是另一個字元編碼的首碼)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹。為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，於是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進位的首碼編碼，既滿足首碼編碼的條件，又保證報文編碼總長最短。 在圖像壓縮時，霍夫曼編碼的基本方法是先對圖像資料掃描一遍，計算出各種圖元出現的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼後的圖像資料記錄的是每個圖元的碼字，而碼字與實際圖元值的對應關係記錄在碼表中。 運行效果： 運行效果： 附原碼1： #include #include using namespace std; //哈夫曼樹的存儲表示 typedef struct { int weight; // 權值 int parent, lChild, rChild; // 雙親及左右孩子的下標 }HTNode, *HuffmanTree; // 選擇權值最小的兩顆樹 void SelectMin(HuffmanTree hT, int n, int &s1, int &s2) { s1 = s2 = 0; int i; for(i = 1; i < n; ++ i){ if(0 == hT[i].parent){ if(0 == s1){ s1 = i; } else{ s2 = i; break; } } } if(hT[s1].weight > hT[s2].weight){ int t = s1; s1 = s2; s2 = t; } for(i += 1; i < n; ++ i){ if(0 == hT[i].parent){ if(hT[i].weight < hT[s1].weight){ s2 = s1; s1 = i; }else if(hT[i].weight < hT[s2].weight){ s2 = i; } } } } // 構造有n個權值（葉子節點）的哈夫曼樹 void CreateHufmanTree(HuffmanTree &hT) { int n, m; cout << "輸入需要構造哈夫曼樹的葉子結點數量，如4："< cin >> n; m = 2*n - 1; hT = new HTNode[m + 1]; // 0號節點不使用 for(int i = 1; i <= m; ++ i){ hT[i].parent = hT[i].lChild = hT[i].rChild = 0; } cout << "輸入權值，如8 6 2 3:" < for(int j = 1; j <= n; ++ j){ cin >> hT[j].weight; // 輸入權值 } hT[0].weight = m; // 用0號節點保存節點數量 /****** 初始化完畢, 創建哈夫曼樹 ******/ for(int k = n + 1; k <= m; ++ k){ int s1, s2; SelectMin(hT, k, s1, s2); hT[s1].parent = hT[s2].parent = k; hT[k].lChild = s1; hT[k].rChild = s2; // 作為新節點的孩子 hT[k].weight = hT[s1].weight + hT[s2].weight; // 新節點為左右孩子節點權值之和 } } int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth) { if(hT[i].lChild == 0 && hT[i].rChild == 0){ return hT[i].weight * deepth; } else{ return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1); } } // 計算WPL（帶權路徑長度） int HuffmanTreeWPL(HuffmanTree hT) { return HuffmanTreeWPL_(hT, hT[0].weight, 0); } // 輸出哈夫曼樹各節點的狀態 void Print(HuffmanTree hT) { cout << "index weight parent lChild rChild" << endl; cout << left; // 左對齊輸出 for(int i = 1, m = hT[0].weight; i <= m; ++ i){ cout << setw(5) << i << " "; cout << setw(6) << hT[i].weight << " "; cout << setw(6) << hT[i].parent << " "; cout << setw(6) << hT[i].lChild << " "; cout << setw(6) << hT[i].rChild << endl; } } // 銷毀哈夫曼樹 void DestoryHuffmanTree(HuffmanTree &hT) { delete[] hT; hT = NULL; } int main() { HuffmanTree hT; CreateHufmanTree(hT); Print(hT); cout << "WPL = " << HuffmanTreeWPL(hT) << endl; DestoryHuffmanTree(hT); system("pause"); return 0; } 附原碼2： #include #include #include #include using namespace std; typedef struct node{ char ch; //存儲該節點表示的字元，只有葉子節點用的到 int val; //記錄該節點的權值 struct node *self,*left,*right; //三個指標，分別用於記錄自己的位址，左孩子的地址和右孩子的地址 friend bool operator <(const node &a,const node &b) //運算子重載，定義優先佇列的比較結構 { return a.val>b.val; //這裡是權值小的優先出佇列 } }node; priority_queue char res[30]; //用於記錄哈夫曼編碼 void dfs(node *root,int level) //列印字元和對應的哈夫曼編碼 { if(root->left==root->right) //葉子節點的左孩子地址一定等於右孩子地址，且一定都為NULL;葉子節點記錄有字元 { if(level==0) //“AAAAA”這種只有一字元的情況 { res[0]='0'; level++; } res[level]='