??? ??? 哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+
Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
??? ??? 構造哈夫曼樹的算法如下：
??? ??? 1）對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,
Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。
??? ??? 2）在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
??? ??? 3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。
??? ??? 4）重復2）和3），直到集合F中只有一棵二叉樹為止。
??? ??? 例如，對于4個權值為1、3、5、7的節(jié)點構造一棵哈夫曼樹，其構造過程如下圖所示（本人不善畫圖，使用DIA勉強畫出如此之圖）：
??? ??
??? ??? 可以計算得到該哈夫曼樹的路徑長度WPL＝(1+3)*3+2*5+1*7=26。
??? ??? 對于哈夫曼樹，有一個很重要的定理：對于具有n個葉子節(jié)點的哈夫曼樹，共有2*n-1個節(jié)點。
??? ??? 這個定理的解釋如下：對于二叉樹來說，有三種類型節(jié)點，即度數（只算出度）為2的節(jié)點，度數為1的節(jié)點和度數為0的葉節(jié)點。而哈夫曼樹的非葉子節(jié)點是由兩個節(jié)點生成的，因此不能出現度數為1的節(jié)點，而生成的非葉子節(jié)點的個數為葉子節(jié)點個數減一，于此定理就得證了。
??? ??? 這里給出構造哈夫曼樹的算法（算法實現使用C語言而不是java）。出于簡單性考慮，構造的哈夫曼樹不是采用鏈式存儲，而是以數組方式存儲，其中使用數組位置索引標識節(jié)點的鏈接。對于哈夫曼樹中的節(jié)點其數據類型如下：
typedef?struct?QHTNode{
????char?c;??????//存儲的數據，為一個字符
????double?weight;?//節(jié)點權重
????int?parent;//父節(jié)點在數組中的位置索引
????int?lchild;//左孩子在數組中的位置索引
????int?rchild;//右孩子在數組中的位置索引
}HTNode;
??? ??? 構造哈夫曼樹的算法的實現原理如下：對于n個葉子節(jié)點，我們根據上面的定理構造出大小為2*n-1的數組來存放整個哈夫曼樹。這個數組的前n個位置存放的為已知的葉子節(jié)點，后（n-1）個位置存放的為動態(tài)生成的樹內節(jié)點。在算法的大循環(huán)過程中，要做的事情就是根據位置i前面的已知節(jié)點（或者是葉節(jié)點或者是生成的樹內節(jié)點），找出
parent為－1（即節(jié)點尚且是一個子樹的根結點）的節(jié)點中權值最小的兩個節(jié)點，然后根據這兩個節(jié)點構造出位置為i的新的父節(jié)點（也就是一棵新樹的根結點）。程序如下：
void?creatHuffmanTree(HTNode?ht[],int?n){
????int?i,j;
????int?lchild,rchild;
????double?minL,minR;
????for(i=0;i<2*n-1;i++){
????????ht[i].parent?=?ht[i].lchild?=?ht[i].rchild?=?-1;
????}
????for(i=n;i<2*n-1;i++){
????????minL?=?minR?=?MAXNUMBER;
????????lchild?=?rchild?=?-1;
????????for(j=0;j<i;j++){
????????????if(ht[j].parent?==?-1){
????????????????if(ht[j].weight?<?minL){
????????????????????minR?=?minL;
????????????????????minL?=?ht[j].weight;
????????????????????rchild?=?lchild;
????????????????????lchild?=?j;
????????????????}else?if(ht[j].weight?<?minR){
????????????????????minR?=?ht[j].weight;
????????????????????rchild?=?j;
????????????????}
????????????}
????????}
????????ht[lchild].parent?=?ht[rchild].parent?=?i;
????????ht[i].weight?=?minL?+?minR;
????????ht[i].lchild?=?lchild;
????????ht[i].rchild?=?rchild;
????}????
}
??? ??? 哈夫曼樹的一個經典應用就是哈夫曼編碼。在數據通信中，經常需要將傳送的文字轉換成二進制字符串，這個過程就是編碼。哈夫曼編碼是一種變長的編碼方案，其核心就是使頻率越高的碼元（這個詞不知用的是否準確，就是要編碼的對象，可以是字符串等等了）采用越短的編碼。編碼過程就根據不同碼元的頻率（相當于權值）構造出哈夫曼樹，然后求葉子節(jié)點到根節(jié)點的路徑，其中節(jié)點的左孩子路徑標識為0，右孩子路徑標識為1。對于上面的例子，權值為1的節(jié)點編碼為000，權值為3的節(jié)點編碼為001，權值為5的節(jié)點編碼為01，權值為7的節(jié)點編碼為1。
??? ??? 下面的實現采用的方法是從葉子節(jié)點向上遍歷到根結點，其中數據類型
HCode中的
code存儲路徑信息，而start表示路徑信息是從code數組的start位置開始的，結束位置為節(jié)點數n。
typedef?struct?QHCode{
????char*?code;
????int?start;
}Hcode;
void?createHuffmanCode(HTNode?ht[],HCode?hc[],int?n){
????int?i,f,c;
????HCode?father;
????for(i=0;i<n;i++){
????????hc[i].start?=?n;
????????c?=?i;
????????while((f=ht[c].parent)?!=?-1){
????????????if(ht[f].lchild?==?c){
????????????????hc[i].code[hc[i].start--]?=?'0';
????????????}else{
????????????????hc[i].code[hc[i].start--]?=?'1';
????????????}
????????????c?=?f;
????????}
????????hc[i].start++;
????}
}
?
??? ??? 注：有關于數據結構及常用算法的系列文章的代碼將主要采用C語言，主要的原因是作者希望借此機會重新溫習一下C語言。數據結構及算法的學習重要的是思想，實現語言倒是其次。如果有人閱讀此代碼有困難，不妨在理解算法的基礎上使用擅長的語言（比如Java？）實現一下。該文參考了《數據結構習題與解析》一書。