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