這一篇要總結的是樹中的最後一種，即哈夫曼樹，我想從以下幾點對其進行總結：
1，什麼是哈夫曼樹？
2，如何建構哈夫曼樹？
3，哈夫曼編碼？
4，算法實作？
回到頂部
一，什麼是哈夫曼樹
什麼是哈夫曼樹呢？
哈夫曼樹是一種帶權路徑長度最短的二叉樹，也稱為最優二叉樹。下面用一幅圖來說明。
它們的帶權路徑長度分别為：
圖a： WPL=5*2+7*2+2*2+13*2=54
圖b： WPL=5*3+2*3+7*2+13*1=48
可見，圖b的帶權路徑長度較小，我們可以證明圖b就是哈夫曼樹(也稱為最優二叉樹)。
回到頂部
二，如何建構哈夫曼樹
一般可以按下面步驟建構：
1，将所有左，右子樹都為空的作為根節點。
2，在森林中選出兩棵根節點的權值最小的樹作為一棵新樹的左，右子樹，且置新樹的附加根節點的權值為其左，右子樹上根節點的權值之和。注意，左子樹的權值應小于右子樹的權值。
3，從森林中删除這兩棵樹，同時把新樹加入到森林中。
4，重複2，3步驟，直到森林中隻有一棵樹為止，此樹便是哈夫曼樹。
下面是建構哈夫曼樹的圖解過程：
三，哈夫曼編碼
利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子節點都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示”0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個葉子節點對應的字元編碼，即是哈夫曼編碼。
就拿上圖例子來說：
A，B，C，D對應的哈夫曼編碼分别為：111，10，110，0
用圖說明如下：
記住，設計電文總長最短的二進制字首編碼，就是以n個字元出現的頻率作為權構造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。
摘自http://www.cnblogs.com/mcgrady/p/3329825.html#_label0
在電報通訊中，電文是以二進制的0、1序列傳送的。字元集中的字元的使用頻率是不同的（比如e和t的使用較之q和z要頻繁得多），哈夫曼編碼可以使得編碼的總長最短，進而相同的位長可以傳送更多的資訊。
本程式以下面的字元及使用頻率為例：
| 字元 | 權值 |
| a | 0.12 |
| b | 0.40 |
| c | 0.15 |
| d | 0.08 |
| e | 0.25 |
首先建立哈夫曼樹：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| tree[i].ch | a | b | c | d | e | ||||
| tree[i].weight | 0.12 | 0.40 | 0.15 | 0.08 | 0.25 | 0.20 | 0.35 | 0.60 | 1.00 |
| tree[i].parent | 5 | 8 | 6 | 5 | 7 | 6 | 7 | 8 | |
| tree[i].lchild | -1 | -1 | -1 | -1 | -1 | 3 | 2 | 4 | 1 |
| tree[i].rchild | -1 | -1 | -1 | -1 | -1 | 5 | 6 | 7 |
得到哈夫曼樹和哈夫曼編碼如下：
下面是哈夫曼編碼的存儲結構：
| 序号 | bits | ch | start | ||
| 1 | 1 | 1 | 1 | a | 2 |
| 1 | b | 5 | |||
| 2 | 1 | 1 | c | 3 | |
| 3 | 1 | 1 | 1 | d | 2 |
| 4 | 1 | e | 4 |
程式清單如下：
#include<stdio.h>
#define n 5 //葉子數目
#define m (2*n-1) //結點總數
#define maxval 10000.0
#define maxsize 100 //哈夫曼編碼的最大位數
typedef struct
{
char ch;
float weight;
int lchild,rchild,parent;
}hufmtree;
typedef struct
{
char bits[n]; //位串
int start; //編碼在位串中的起始位置
char ch; //字元
}codetype;
void huffman(hufmtree tree[]);//建立哈夫曼樹
void huffmancode(codetype code[],hufmtree tree[]);//根據哈夫曼樹求出哈夫曼編碼
void decode(hufmtree tree[]);//依次讀入電文，根據哈夫曼樹譯碼
void main()
{
printf(" ——哈夫曼編碼——\n");
printf("總共有%d個字元\n",n);
hufmtree tree[m];
codetype code[n];
int i,j;//循環變量
huffman(tree);//建立哈夫曼樹
huffmancode(code,tree);//根據哈夫曼樹求出哈夫曼編碼
printf("【輸出每個字元的哈夫曼編碼】\n");
for(i=0;i<n;i++)
{
printf("%c: ",code[i].ch);
for(j=code[i].start;j<n;j++)
printf("%c ",code[i].bits[j]);
printf("\n");
}
printf("【讀入電文，并進行譯碼】\n");
decode(tree);//依次讀入電文，根據哈夫曼樹譯碼
}
void huffman(hufmtree tree[])//建立哈夫曼樹
{
int i,j,p1,p2;//p1,p2分别記住每次合并時權值最小和次小的兩個根結點的下标
float small1,small2,f;
char c;
for(i=0;i<m;i++) //初始化
{
tree[i].parent=0;
tree[i].lchild=-1;
tree[i].rchild=-1;
tree[i].weight=0.0;
}
printf("【依次讀入前%d個結點的字元及權值(中間用空格隔開)】\n",n);
for(i=0;i<n;i++) //讀入前n個結點的字元及權值
{
printf("輸入第%d個字元為和權值",i+1);
scanf("%c %f",&c,&f);
getchar();
tree[i].ch=c;
tree[i].weight=f;
}
for(i=n;i<m;i++) //進行n-1次合并，産生n-1個新結點
{
p1=0;p2=0;
small1=maxval;small2=maxval; //maxval是float類型的最大值
for(j=0;j<i;j++) //選出兩個權值最小的根結點
if(tree[j].parent==0)
if(tree[j].weight<small1)
{
small2=small1; //改變最小權、次小權及對應的位置
small1=tree[j].weight;
p2=p1;
p1=j;
}
else
if(tree[j].weight<small2)
{
small2=tree[j].weight; //改變次小權及位置
p2=j;
}
tree[p1].parent=i;
tree[p2].parent=i;
tree[i].lchild=p1; //最小權根結點是新結點的左孩子
tree[i].rchild=p2; //次小權根結點是新結點的右孩子
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}//huffman
void huffmancode(codetype code[],hufmtree tree[])//根據哈夫曼樹求出哈夫曼編碼
//codetype code[]為求出的哈夫曼編碼
//hufmtree tree[]為已知的哈夫曼樹
{
int i,c,p;
codetype cd; //緩沖變量
for(i=0;i<n;i++)
{
cd.start=n;
cd.ch=tree[i].ch;
c=i; //從葉結點出發向上回溯
p=tree[i].parent; //tree[p]是tree[i]的雙親
while(p!=0)
{
cd.start--;
if(tree[p].lchild==c)
cd.bits[cd.start]='0'; //tree[i]是左子樹，生成代碼'0'
else
cd.bits[cd.start]='1'; //tree[i]是右子樹，生成代碼'1'
c=p;
p=tree[p].parent;
}
code[i]=cd; //第i+1個字元的編碼存入code[i]
}
}//huffmancode
void decode(hufmtree tree[])//依次讀入電文，根據哈夫曼樹譯碼
{
int i,j=0;
char b[maxsize];
char endflag='2'; //電文結束标志取2
i=m-1; //從根結點開始往下搜尋
printf("輸入發送的編碼(以'2'為結束标志)：");
gets(b);
printf("譯碼後的字元為");
while(b[j]!='2')
{
if(b[j]=='0')
i=tree[i].lchild; //走向左孩子
else
i=tree[i].rchild; //走向右孩子
if(tree[i].lchild==-1) //tree[i]是葉結點
{
printf("%c",tree[i].ch);
i=m-1; //回到根結點
}
j++;
}
printf("\n");
if(tree[i].lchild!=-1&&b[j]!='2') //電文讀完，但尚未到葉子結點
printf("\nERROR\n"); //輸入電文有錯
}//decode
貼出一例運作結果：
摘自http://blog.sina.com.cn/s/blog_686d0fb001012qmh.html