哈夫曼树(最优二叉树)

介绍

​ 利用一个字符串中符号的出现频率(即出现概率)作为输入，并差生编码这个字符串的一个前缀码作为输出，在这些符号的所有可能的二叉前缀码中，这个编码使用最少的位。

构造

1、根据给定的n个权值，构造n棵只有一个结点的二叉树，n个权值分别为这些树根结点的全。设森林F是由这n棵树构成的集合；(原始森林)

2、在F中选取两棵根的权值最小的树作为左、右子树，构造一棵新二叉树，置新二叉树的权值=左、右子树根结点权值之和；(每次新增一个结点)

3、从F中删除这两棵树，并将新树加入F；(每次少一棵树)

4、重复2、3，直到F中只含一棵树为止。(重复n-1次)

具体构造图示：链接

算法实现

定义结点类型

typedef struct
{
    int weight,parent,lchild,rchild;
}HTNode;

构造算法

void CreatHuffmanTree(HTNode *ht,int n)
{
    if(n<=1)return;
    int i,j,l,r,min_1,min_2;
    //初始化
    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++)
	{
		min_1=min_2=9999999;
		l=r=-1;
        //找到权值最小的两个结点
		for(j=0;j<i;j++)
		{
			if(ht[j].parent==-1)
			{
				if(ht[j].weight<min_1)
				{
					min_2=min_1;
					r=l;
					min_1=ht[j].weight;
					l=j;
				}
				else if(ht[j].weight<min_2)
				{
					min_2=ht[j].weight;
					r=j;
				}
			}
		}
		ht[i].weight=ht[l].weight+ht[r].weight;
		ht[l].parent=ht[r].parent=i;
		ht[i].lchild=l;
		ht[i].rchild=r;
	}
}

结论