哈夫曼树及编译码
哈夫曼树，又称二叉树，是一类带权路径长度最短的树。所谓路径长度，就是节点到树根之间的路径长度与节点权值的乘积。
哈夫曼本人曾在MIT的信息论研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而哈夫曼选择了后者，原因很简单，因为解决一大作业可能比期未考试更容易通过。Robert Fano教授也是信息论的先驱，学过信息论的都知道有Fano不等式，Shannon-Fano编码。当时这个大作业，Fano也解决不了，哈夫曼并不知道，于是自己尝试，最终产生了哈夫曼编码，其性能比Shannon-Fano编码更好。这个故事说明，大师级人物未能解决的问题，我们不一定解决不了，因为我们的思想比较开阔，能从不同的角度看问题。还有就是turbo码的产生也印证了这个道理。但是任何成功都离不开坚持不懈的努力。这段小故事就当你我共勉。
哈夫曼树
哈夫曼树的构造由下图可清楚明了：（总的来说就是每次将两个最小的节点合并）
用上述算法来对图12.16中的叶子结点集合构造哈夫曼树的初始状态如图12.18(a)所示，第一次合并状态如图12.18(b)所示，结果状态如图12.18(c)所示。在算法中，每次合并时都是将具有较小权值的结点置为合并后结点的左孩子，而具有较大权值的结点置为合并后结点的右孩子。
具体实现如下：
/**********************************************************\
函数功能：构造哈夫曼树
输入： 头结点、权重、元素值
输出： 无
\**********************************************************/
void HuffmanTree(huffmantree *tree,double *weight,int *data)
{
int i,j;
for(i=0;i<m;i++)//初始化
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0.0;
tree[i].data=0;
}
for(i=0;i<n;i++)
{
tree[i].weight=weight[i];//给每个节点赋权值和内容
tree[i].data=data[i];
}
for(i=n;i<m;i++)
{
int p1=0;
int p2=0;
float small1,small2;
small1=small2=10000;//初始化为一个很大的值
for(j=0;j<=i-1;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;//将两个节点合并为一个节点
}
}
通过从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
因为形成哈夫曼树的每一次合并操作都将对应一次代码分配，因此n个叶子结点的最大编码长度不会超过n–1，所以可为每个叶子结点分配一个长度为n的编码数组。
基本思想是：从叶子tree[i]出发，利用双亲地址找到双亲结点tree[p]，再利用tree[p]的lchild和rchild指针域判断tree[i]是tree[p]的左孩子还是右孩子，然后决定分配代码是“0”还是“1”, 然后以tree[p]为出发点继续向上回溯，直到根结点为止。
具体算法实现如下：
/**************************************************\
函数功能：进行哈夫曼编码
输入： 用于存储编码的数组code、哈夫曼树
输出： 无
\**************************************************/
void HuffmanCode(codetype *code,huffmantree *tree)
{
int i,c,p;
codetype cd;//缓冲变量
for(i=0;i<n;i++)
{
cd.start=n;//从叶子节点开始回溯
c=i;
p=tree[c].parent;
cd.data=tree[c].data;
while(p!=0)
{
cd.start--;
if(tree[p].lchild==c)//左节点则编为0，右节点则编为1
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
c=p;
p=tree[c].parent;
}
code[i]=cd;
code[i].start=cd.start;
}
}
哈夫曼译码：
哈夫曼树译码是指由给定的代码求出代码所表示的结点值，它是哈夫曼树编码的逆过程。
译码的基本思想是：从根结点出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。
具体译码算法如下：
/***************************************************\
函数功能：哈夫曼译码
输入： 存储编码的数组、哈夫曼树
输出： 无
\***************************************************/
void HuffmanDecode(codetype *code,huffmantree *tree)
{
int i=m-1;
printf("\n译码结果为：\n");
for(int j=0;j<n;j++)
{
for(int k=code[j].start;k<n;k++)//循环n次，对n个码进行译码
{
if(code[j].bits[k]==0)
i=tree[i].lchild;
else
i=tree[i].rchild;
if(tree[i].lchild==0)
{
printf("%d ",code[i].data);
i=m-1;
}
}
}
}
完整实例如下：假设有6个节点，权值分别为0.4、0.3、0.1、0.1、0.08、0.02，元素值分别为2、1、3、4、6、5.则哈夫曼树的构造过程和编码如下:
具体的代码实现如下：
#include<stdio.h>
#define n 6 //叶子数目
#define m (2*n-1)//节点总数
#define maxsize 10
typedef int datatype;
typedef struct
{
double weight;
datatype data;
int lchild,rchild,parent;
}huffmantree;
typedef struct
{
int bits[n];
int start;
int data;
}codetype;
void HuffmanTree(huffmantree *tree,double *weight,int *data);
void HuffmanCode(codetype *code,huffmantree *tree);
void HuffmanDecode(codetype *code,huffmantree *tree);
void main()
{
double weight[]={0.4,0.3,0.1,0.1,0.02,0.08};
int data[]={2,1,3,4,5,6};
huffmantree head[m];
codetype code[n];
HuffmanTree(head,weight,data);
HuffmanCode(code,head);
for(int i=0;i<m;i++)
printf("%d ",head[i].parent);//对应的父节点
printf("\n编码结果为：\n");
for(int i=0;i<n;i++)
{
for(int j=code[i].start;j<n;j++)
printf("%d ",code[i].bits[j]);
printf("\n");
}
HuffmanDecode(code,head);
}
/**********************************************************\
函数功能：构造哈夫曼树
输入： 头结点、权重、元素值
输出： 无
\**********************************************************/
void HuffmanTree(huffmantree *tree,double *weight,int *data)
{
int i,j;
for(i=0;i<m;i++)//初始化
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0.0;
tree[i].data=0;
}
for(i=0;i<n;i++)
{
tree[i].weight=weight[i];//给每个节点赋权值和内容
tree[i].data=data[i];
}
for(i=n;i<m;i++)
{
int p1=0;
int p2=0;
float small1,small2;
small1=small2=10000;//初始化为一个很大的值
for(j=0;j<=i-1;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;//将两个节点合并为一个节点
}
}
/**************************************************\
函数功能：进行哈夫曼编码
输入： 用于存储编码的数组code、哈夫曼树
输出： 无
\**************************************************/
void HuffmanCode(codetype *code,huffmantree *tree)
{
int i,c,p;
codetype cd;//缓冲变量
for(i=0;i<n;i++)
{
cd.start=n;//从叶子节点开始回溯
c=i;
p=tree[c].parent;
cd.data=tree[c].data;
while(p!=0)
{
cd.start--;
if(tree[p].lchild==c)//左节点则编为0，右节点则编为1
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
c=p;
p=tree[c].parent;
}
code[i]=cd;
code[i].start=cd.start;
}
}
/***************************************************\
函数功能：哈夫曼译码
输入： 存储编码的数组、哈夫曼树
输出： 无
\***************************************************/
void HuffmanDecode(codetype *code,huffmantree *tree)
{
int i=m-1;
printf("\n译码结果为：\n");
for(int j=0;j<n;j++)
{
for(int k=code[j].start;k<n;k++)//循环n次，对n个码进行译码
{
if(code[j].bits[k]==0)
i=tree[i].lchild;
else
i=tree[i].rchild;
if(tree[i].lchild==0)
{
printf("%d ",code[i].data);
i=m-1;
}
}
}
}
注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明
原文：http://blog.csdn.net/tengweitw/article/details/9838343
作者：nineheadedbird
