文章目錄
- 引入哈夫曼樹
- 例
- 引出問題
- 哈夫曼樹的基本概念
- 路徑
- 結點的路徑長度
- 樹的路徑長度
- 權（weight）
- 結點的帶權路徑長度
- 樹的帶權路徑長度
- 例
- 什麼是哈夫曼樹
- 注意
- 哈夫曼樹的構造算法
- 哈夫曼算法（構造哈夫曼樹的方法）
- 例1
- 例2
- 總結
- 哈夫曼構造算法的實作
- 結點類型定義
- 例
- 哈夫曼樹構造算法的實作
- 例
- 哈夫曼編碼
- 字首編碼
- 引出哈夫曼編碼
- 例題
- 兩個問題
- 哈夫曼編碼的存儲表示
- 根據哈夫曼樹求哈夫曼編碼
- 哈夫曼編碼應用舉例
引入哈夫曼樹
例
程式設計：将學生的百分制成績轉換為五分制成績。
<60:E 60-69:D 70-79:C 80-89:B 90-100:A
if(score<60)
grade == 'E';
else if(score<70)
grade == 'D';
else if(score<80)
grade == 'C';
else if(score<90)
grade == 'B';
else
grade == 'A'; 
當樹上帶權值時：
5%的資料需1次比較，15%的資料需2次比較，40%的資料需3次比較，40%的資料需4次比較，是以10000個資料比較的次數為：
10000(1 * 5% + 2 * 15% + 3 * 40% + 4 * 10%) = 31500次
10000(3 * 20% + 2 * 80%) = 22000次
引出問題
能不能找到一種效率最高的判别樹呢？
答：哈夫曼樹（最優二叉樹）
（判斷樹：用于描述分類過程的二叉樹。）
哈夫曼樹的基本概念
路徑
從樹中一個結點到另一個結點之間的分支構成這兩個結點間的路徑。
結點的路徑長度
兩結點間路徑上的分支數。
（a）從A到B, C, D, E, F, G, H, I的路徑長度分别為1, 1, 2, 2, 3, 3, 4, 4。
（b）從A到B, C, D, E, F, G, H, I的路徑長度分别為1, 1, 2, 2, 2, 2, 3, 3。
樹的路徑長度
從樹根到每一個結點的路徑長度之和。記作TL。
TL(a) = 0+1+1+2+2+3+3+4+4=20
TL(b) = 0+1+1+2+2+2+2+3+3=16
結點數目相同的二叉樹中，完全二叉樹是路徑長度最短的二叉樹。
權（weight）
将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。
結點的帶權路徑長度
從根結點到該節點之間的路徑長度與該結點的權的乘積。
樹的帶權路徑長度
樹中所有葉子結點的帶權路徑長度之和。
記作：
其中，wk為權值，lk為結點到根的路徑長度。
例
有4個結點a, b, c, d，權值分别為7, 5, 2, 4，構造以此4個結點為葉子結點的二叉樹：
帶權路徑長度是：
（a）WPL=7x2 + 5x2 + 2x2 + 4x2 = 36
（b）WPL=7x3 + 5x3 + 2x1 + 4x2 = 46
什麼是哈夫曼樹
哈夫曼樹：最優樹，就是帶權路徑長度（WPL）最短的樹。
注意：“帶權路徑長度最短”是在“度相同”的樹中比較而得的結果，是以有最優二叉樹、最優三叉樹之稱等等。
哈夫曼樹：最優二叉樹，就是帶權路徑長度（WPL）最短的二叉樹。
因為構造這種樹的算法是由哈夫曼教授于1952年提出的，是以被稱為哈夫曼樹，相應的算法稱為哈夫曼算法。
注意
滿二叉樹不一定是哈夫曼樹。
哈夫曼樹中權越大的葉子離根越近。
具有相同帶權結點的哈夫曼樹不唯一。
哈夫曼樹的構造算法
哈夫曼樹中權越大的葉子離根越近。
貪心算法：構造哈夫曼樹時首先選擇權值小的葉子結點。
哈夫曼算法（構造哈夫曼樹的方法）
（1）根據n個給定的權值（w1, w2, …, wn）構成n棵二叉樹的森林F = {T1, T2, …, Tn}，其中，Ti隻有一個帶權為wi的根節點。
（構造森林全是根）
（2）在F中選取兩棵根結點的權值最小的樹作為左右子樹，構造一棵新的二叉樹，且設定新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
（選用兩小造新樹）
（3）在F中删除這兩棵樹，同時将新得到的二叉樹加入森林中。
（删除兩小添新人）
（4）重複（2）和（3），直到森林中隻有一棵樹位置，這棵樹即為哈夫曼樹。
（重複2、3剩單根）
例1
有4個結點a, b, c, d，權值分别為7, 5, 2, 4，構造哈夫曼樹。
例2
有5個結點a, b, c, d, e，權值分别為7, 5, 5, 2, 4，構造哈夫曼樹。
總結
哈夫曼樹的結點度為0或2，沒有度為1的結點。
包含n棵樹的森林要經過n-1次合并才能形成哈夫曼樹，共産生n-1個新結點。
包含n個葉子結點的哈夫曼樹中共有2n-1個結點。
在哈夫曼算法中，初始有n棵二叉樹，要經過n-1次合并最終形成哈夫曼樹。
經過n-1次合并産生n-1個新結點，且這n-1個新結點都是具有兩個孩子的分支結點。
可見：哈夫曼樹中共有n+n-1 = 2n-1個結點，且其所有的分支結點的度均不為1。
哈夫曼構造算法的實作
采用順序存儲結構——一維結構數組（HuffmanTree H;）
結點類型定義
typedef struct {
int weight;
int parent, lch, rch;
} HTNode, *HuffmanTree; 哈夫曼樹中共有2n-1個結點，不适用0下标，數組大小為2n。
例如，第1個結點權值為5，即可表示為H[i].weight=5。
例
有n=8，權值為W={7, 19, 2, 6, 32, 3, 21, 10}，構造哈夫曼樹。
哈夫曼樹構造算法的實作
1.初始化HT[1…2n-1]：lch=rch=parent=0；
2.輸入初始n個葉子結點：置HT[1…n]的weight值；
3.進行以下n-1次合并，依次産生n-1個結點HT[i]，i=n+1…2n-1：
（1）在HT[1…i-1]中選兩個未被選過（從parent == 0的結點中選）的weight最小的兩個結點HT[s1]和HT[s2], s1、s2為兩個最小結點下标；
（2）修改HT[s1]和HT[s2]的parent值：HT[s1].parent=i；HT[s2].parent=i；
（3）修改新産生的HT[i]：
① HT[i].weight = HT[s1].weight + HT[s2].weight;
② HT[i].lch = s1;HT[i].rch = s2;
void CreateHuffmanTree(HuffmanTree &HT, int n)
{ //構造哈夫曼樹 HT
if(n<=1) return;
m=2*n-l;
HT=new HTNode[m+l]; //0 号單元未用，是以需要動态配置設定 m+l 個單元， HT[m]表示根結點
for(i=1;i<=m;++i) //将1~m号單元中的雙親、左孩子，右孩子的下标都初始化為0
{HT[i].parent=O; HT[i].lchild=O; HT[i].rchild=O;}
for(i=1;i<=n;++i} //輸人前 n 個單元中葉子結點的權值
cin>>HT[i].weight;
／*－ －－－－ －－－－－ －初始化工作結束， 下面開始建立哈夫曼樹－ － － － －－－－－－ */
for (i=n+1; i<=m; ++i}
{//通過 n-1 次的選擇、删除 、 合并來建立哈夫曼樹
Select (HT, i-1, s1, s2};
//在 HT[k] (1≤k≤i-1) 中選擇兩個其雙親域為0 且權值最小的結點，并傳回它們在 HT 中的序号 s1和 s2
HT[s1].parent=i;HT[s2].parent=i;
//得到新結點 i, 從森林中删除s1, s2, 将s1和s2 的雙親域由 0改為l.
HT[i].lchild=s1;HT[i].rchild=s2; //s1, s2分别作為i的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight; //i的權值為左右孩子權值之和
}//for
} 例
已知 w = (5,29,7,8,14,23,3,11), 利用算法試構造一棵哈夫曼樹， 計算樹的帶權路徑長度， 并給出其構造過程中存儲結構HT的初始狀态和終結狀态。
n= 8, 則 m = 15, 按算法可構造一棵哈夫曼樹， 如圖所示。
樹的帶權路徑長度計算如下：
其存儲結構HT的初始狀态如表 5.2 (a)所示， 其終結狀态如表 5.2 (b)所示。
哈夫曼編碼
在遠端通訊中，要将待傳字元轉換成由二進制的字元串：
若編碼為：A-00; B-01; C-10; D-11
則要傳送的字元為：
若将編碼設計為長度不等的二進制編碼，即讓待傳字元串中出現次數較多的字元采用盡可能短的編碼，則轉換的二進制字元串便可能減少。
字首編碼
關鍵：要設計長度不等的編碼，則必須使任一字元的編碼都不是另一個字元的編碼的字首，這種編碼稱作字首編碼。
引出哈夫曼編碼
問題：什麼樣的字首碼能使得電文總長最短？
——哈夫曼編碼。
方法：
1.統計字元集中每個字元在電文中出現的平均機率（機率越大，要求編碼越短）。
2.利用哈夫曼樹的特點：權越大的葉子離根越近；将每個字元的機率值作為權值，構造哈夫曼樹。則機率越大的結點，路徑越短。
3.在哈夫曼樹的每個分支上标上0或1：
結點的左分支标0，右分支标1。
把從根到每個葉子的路徑上的标号連接配接起來，作為該葉子代表的字元的編碼。
例題
要傳輸的字元集D = {C, A, S, T, ; }
字元出現頻率w = {2, 4, 2, 3, 3 }
例：電文是{CAS;CAT;SAT;AT}
其編碼是：11010111011101000011111000011000，反之，若編碼是“1101000”，則其譯文是“CAT”。
兩個問題
1.為什麼哈夫曼編碼能夠保證是字首編碼？
因為沒有一片樹葉是另一片樹葉的祖先，是以每個葉結點的編碼就不可能是其它葉結點編碼的字首。
2.為什麼哈夫曼編碼能夠保證字元編碼總長最短？
因為哈夫曼樹的帶權路徑長度最短，故字元編碼的總長最短。
· 性質1：哈夫曼編碼是字首編碼。
· 性質2：哈夫曼編碼是最優字首編碼。
哈夫曼編碼的存儲表示
// - - - - -哈夫曼編碼表的存儲表示－－－－－
typedef char **HuffmanCode; // 動态配置設定數組存儲哈夫曼編碼表 根據哈夫曼樹求哈夫曼編碼
算法步驟：
1.配置設定存儲n個字元編碼的編碼表空間HC，長度為n+1；配置設定臨時存儲每個字元編碼的動态數組空間cd，cd[n-1]置為’\0’。
2.逐個求解n個字元的編碼，循環n次，執行以下操作：
（1）設定變量start用于記錄編碼在cd中存放的位置，start初始時指向最後，即編碼結束符位置n-1；
（2）設定變量c用于記錄從葉子結點向上回溯至根結點所經過的結點下标，c初始時為目前待編碼字元的下标i，f用于記錄i的雙親結點的下标；
（3）從葉子結點向上回溯至根結點，求得字元i的編碼，當f沒有到達根結點時，循環執行以下操作：
① 回溯依次start向前指一個位置，即–start；
② 若結點c是f的左孩子，則生成代碼0，否則生成代碼1，生成的代碼0或1儲存在cd[start]中；
③ 繼續向上回溯，改變c和f的值。
（4）根據數組cd的字元串長度為第i個字元編碼配置設定空間HC[i]，然後将數組cd中的編碼複制到HC[i]中。
3.釋放臨時空間cd。
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{ // 從葉子到根逆向求每個字元的哈夫曼編碼， 存儲在編碼表HC中
HC=new char*[n+1]; // 配置設定存儲n個字元編碼的編碼表空間
cd=new char[n]; // 配置設定臨時存放每個字元編碼的動态數組空間
cd[n-1]='\0'; // 編碼結束符
for(i=1;i<=n;++i) // 逐個字元求哈夫曼編碼
{
start=n-1; //start 開始時指向最後， 即編碼結束符位置
c=i; f=HT[i].parent; //f指向結點c的雙親結點
while(f!=O) // 從葉子結點開始向上回溯， 直到根結點
{
--start; //回溯一次start向前指一個位置
if(HT[f].lchild==c) cd[start]='O'; //結點c是f的左孩子， 則生成代碼0
else cd[start]='1'; //結點c是f的右孩子， 則生成代碼1
c=f;f=HT[f].parent; //繼續向上回溯
} //求出第l.個字元的編碼
HC[i]=new char[n-start]; //為第i個字元編碼配置設定空間
strcpy(HC[i],&cd[start]); //将求得的編碼從臨時空間cd複制到HC的目前行中
}
delete cd; //釋放臨時空間
}