目录
哈夫曼树的结构
typedef struct{
char data; //哈夫曼树存储的字符
int weight; //权值
int parent; //结点的双亲
int lchild; //结点的左孩子
int rchild; //结点的右孩子
}HNodeType;
哈夫曼树的口诀
建立哈夫曼树的方法：
（1）构造森林全是根
（2）合并两小建新树
（3）删除两小添新树
（4）重复(2)(3)剩单根
哈夫曼树的建立
void HuffmanTree(HNodeType HuffNode[],int n){
int i,j,x1,x2,m1,m2; //i,j用于循环；x1,x2用于保存两个权值最小结点的下标；m1,m2用于保存两个权值最小的权值
for(i=0;i<2*n-1;i++){ //初始化置所有结点的双亲，左右孩子的下标为-1
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<n-1;i++){ //由于前面n个结点的权值已经知道，我们只需要循环得到后面n-1个权值即可，一共循环n-1次
m1=m2=100; //初始化置m1,m2都为最大
x1=x2=0; //初始化置x1,x2都为下标0
for(j=0;j<n+i;j++){ //在n+i个里面找最小的两个（n个是原有的，i个是每次新加入的树）
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){ //寻找两个最小的值（当有权值小于最小值时，执行）
m2=m1; //m2保存次小的权值
x2=x1; //x2保存次小权值的下标
m1=HuffNode[j].weight; //m1保存最小的权值
x1=j; //x1保存最小权值的下标
}else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1){ //当权值都大于最小值，我们找它是否小于次小值
m2=HuffNode[j].weight; //小于次小值就把它给m2
x2=j; //下标保存次小值
}
}
HuffNode[x1].parent=n+i; //最小值和次小值的双亲下标是n+i
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; //第n+i个元素是x1,x2的双亲，它的权值等于两者相加
HuffNode[n+i].lchild=x1; //第n+i个元素的左孩子为x1，右孩子为x2
HuffNode[n+i].rchild=x2;
HuffNode[n+i].data='0'; //将双亲的字符赋为'0'
}
for(i=0;i<2*n-1;i++){
printf("%c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild);
}
}