构建Huffman树：
1.将给定的n个权值看作n棵只有结点无左右孩子的二叉树，组合成一个集合HT。
2.从集合HT中选出2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这两棵二叉树的权值之和。
3.将步骤2中选出的二叉树从集合HT中删去，同时将步骤2中新的二叉树加入到集合HT中。
4.重复步骤2和步骤3，直到集合HT中只含有一棵树，这棵树就是Huffman树。
伪代码：
typedefstruct//定义结构体
{
intweight;//保存权值
intparent, lchild, rchild;//保存父节点、左右孩子的节点值
}HuffmanNode, *HuffmanTree;
typedefchar**HuffmanCode;//用来存储哈夫曼编码
procHuffmanCoding(HuffmanTree &HT,int*w,intn)//编码函数定义
if(n <= 1)then Error();
m := 2 * n - 1;//n nodes create huffman tree need 2n-1 nodes
HT:= (HuffmanNode*)malloc((m +1) *sizeof(HuffmanNode));//HT存放Huffman tree的所有节点，申请m+1个位置
memset(HT, 0, (m + 1)*sizeof(HuffmanNode));//对所有节点初始化为0
//setthe n nodes
fori from 1 to n
HT[i].weight := *w++;//初始化各节点的权值
//createHuffman tree
fori from n + 1 to m//从HT的第n+1个位置开始
select(HT, i - 1, s1,s2);//选择剩余节点中权值较小的s1和s2
HT[s1].parent := i;//s1,s2的父节点都是当前结点
HT[s2].parent := i;
HT[i].lchild := s1;
HT[i].rchild := s2;
HT[i].weight :=HT[s1].weight + HT[s2].weight;
end{for}
HC := (HuffmanCode)malloc((n + 1) *sizeof(char*));
char*cd = (char*)malloc(n *sizeof(char));//申请n个位置，最后一位存放结束符
cd[n - 1] ='\0';
fori from 1 to n
start = n - 1;
for(c= i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
if(HT[f].lchild == c)
cd[--start] ='0';//cd从后往前依次存放
else
cd[--start] ='1';
end{for}
HC[i] = (char*)malloc((n - start) *sizeof(char));
strcpy(HC[i],&cd[start]);
end{for}
end{proc}
源码：
#include
#include
#include
usingnamespacestd;
/*哈夫曼树的存储结构，它是二叉树*/
typedefstruct
{
intweight;//保存权值
intparent, lchild, rchild;//保存父节点、左右孩子的节点值
}HuffmanNode, *HuffmanTree;
typedefchar**HuffmanCode;//用来存储哈夫曼编码
voidHuffmanCoding(HuffmanTree &HT,int*w,intn);//Huffman编码函数
voidselect(HuffmanTree HT,intn,int&s1,int&s2);//选择书中节点值较小的两个节点
voidError(char*message);//显示错误信息
intmain(intargc,char* argv[])
{
inti,n;
int*w;
HuffmanCode HC;
HuffmanTree HT;
cout<<"Enter the size of the code:";
cin>>n;
w=(int*)malloc(n*sizeof(int));
cout<<"Enter the weight of the code:";
for(i=0;i
cin>>w[i];
cout<<"The Huffmancode is:"<
HuffmanCoding(HT, w, n);
system("pause");
}
voidHuffmanCoding(HuffmanTree &HT,int*w,intn)
{
if(n <= 1)
Error("code is small");
intm = 2 * n - 1;//n nodes create huffman tree need2n-1 nodes
HT = (HuffmanNode*)malloc((m +1) *sizeof(HuffmanNode));//Huffman tree的所有节点
ints1, s2;//record the two mini weights nodes
memset(HT, 0, (m + 1)*sizeof(HuffmanNode));//对所有节点初始化为0
//setthe n nodes
for(inti = 1; i <= n; i++)
{
HT[i].weight = *w++;//初始化各节点权值
}
//创建Huffmantree
for(inti = n + 1; i <= m; ++i)
{
//选择剩余节点中权值较小的s1和s2
select(HT, i - 1, s1,s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight+ HT[s2].weight;
}
HuffmanCode HC;
intstart, c, f;
HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));
char*cd = (char*)malloc(n *sizeof(char));
cd[n - 1] ='\0';
for(inti = 1; i <= n; ++i)
{
start = n - 1;
for(c= i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
if(HT[f].lchild == c)
cd[--start] ='0';
else
cd[--start] ='1';
HC[i] = (char*)malloc((n - start) *sizeof(char));
strcpy(HC[i],&cd[start]);
}
for(inti = 1; i <= n; i++)
{
cout<
}
free(cd);
free(HC);
free(HT);
}
voidError(char*message)
{
fprintf(stderr,"Error: %s(5s will exit)",message);
cout<<"\n";
Sleep(5000);
exit(1);
}
voidselect(HuffmanTree HT,intn,int&s1,int&s2)
{
s1 = 1;
s2 = 1;
intmin= 99999;
inti;
//选择未被使用的第一个节点，
for(i = 1; i <= n; ++i)
{
if(HT[i].parent == 0)
{
min = HT[i].weight;
break;
}
}
//findthe mini s1
for(intp =1; p <= n; ++p)
{
if(0== HT[p].parent && min >= HT[p].weight)
{
s1 = p;
min = HT[p].weight;
}
}
//findthe s2
min = 99999;
for(intq =1; q <= n; ++q)
{
if(0== HT[q].parent && min >= HT[q].weight )
{
if(q == s1)
continue;
s2 = q;
min = HT[q].weight;
}
}
}
运行结果示例：
网友评论