17-创建哈夫曼树并输出哈夫曼编码
创建哈夫曼树并输出哈夫曼编码
问题描述
为一组权值分别为2、4、7、15的节点序列创建一棵哈夫曼树，然后输出相应叶子节点的哈夫曼编码。
【分析】
为了便于设计，可利用一个二维数组实现创建哈夫曼树的算法。因为需要保存字符的权值、双亲节点的位置、左子节点的位置和右子节点的位置，所以需要将数组设计成n行4列。因此，哈夫曼树的类型定义如下。
typedef struct /*哈夫曼树类型定义*/
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; /*存放哈夫曼编码*/【算法实现】
定义一个类型为HuffmanCode的数组HT，用来存放每一个叶子节点的哈夫曼编码。将每一个叶子节点的双亲节点域、左子节点域和右子节点域初始化为0。如果有n个叶子节点，则非叶子节点有n−1个，所以总节点数是（2n−1）。同时也要将剩下的（n−1）个双亲节点域初始化为0，这主要是为了方便查找权值最小的节点。
依次选择两个权值最小的节点，分别作为左子节点和右子节点，修改它们的双亲节点域，使它们指向同一个双亲节点，同时修改双亲节点的权值，使其等于左、右两个子节点权值的和，并修改双亲节点的左、右子节点域，使其分别指向左、右子节点。重复执行这种操作（n−1）次，即求出（n−1）个非叶子节点的权值。这样就得到了一棵哈夫曼树。
通过求得的哈夫曼树，得到每一个叶子节点的哈夫曼编码。从某一个叶子节点开始，通过该叶子节点的双亲节点域，找到叶子节点的双亲，然后通过双亲节点的左子节点域和右子节点域判断该叶子节点是其双亲节点的左子节点还是右子节点。如果该叶子节点是左子节点，则编码为“0”；否则，编码为“1”。按照这种方法，直到找到根节点，即可以求出叶子节点的哈夫曼编码。
第7章\实例7-12.cpp
/********************************************
*实例说明：创建哈夫曼树并输出哈夫曼编码
*********************************************/
typedef struct //哈夫曼树类型定义
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; //存放哈夫曼编码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<iostream.h>
#define infinity 10000 //定义一个较大的值
int Min(HuffmanTree t,int n);
void Select(HuffmanTree *t,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
cout<<"请输入叶子节点的个数: ";
cin>>n;
w=(int*)malloc(n*sizeof(int)); //为n个节点的权值分配内存空间
for(i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的权值:";
cin>>w[i];
}
HuffmanCoding(&HT,&HC,w,n);
for(i=1;i<=n;i++)
{
cout<<"权值为"<<w[i-1]<<"的哈夫曼编码:";
cout<<HC[i]<<endl;
}
//释放内存空间
for(i=1;i<=n;i++)
free(HC[i]);
free(HC);
free(HT);
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
//构造哈夫曼树HT，哈夫曼编码存放在HC中，w为n个字符的权值
{
int m,i,s1,s2,start;
unsigned int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=*HT+1,i=1;i<=n;i++,p++,w++) //初始化n个叶子节点
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;i++,p++) //将（n-1）个非叶子节点的双亲节点初始化为0
(*p).parent=0;
for(i=n+1;i<=m;++i) //构造哈夫曼树
{
Select(HT,i-1,&s1,&s2); //查找哈夫曼树中权值最小的两个节点
(*HT)[s1].parent=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
//从叶子节点到根节点求每个字符的哈夫曼编码
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char)); //为哈夫曼编码动态分配空间
cd[n-1]='\0';
//求n个叶子节点的哈夫曼编码
for(i=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]);
}
free(cd);
}
int Min(HuffmanTree t,int n)
//返回哈夫曼树中n个节点中权值最小的节点序号
{
int i,flag;
int f=infinity; //f为一个较大的值
for(i=1;i<=n;i++)
if(t[i].weight<f&&t[i].parent==0)
f=t[i].weight；
flag=i;
t[flag].parent=1;
return flag;
}
void Select(HuffmanTree *t,int n,int *s1,int *s2)
//在n个节点中选择两个权值最小的节点，其中s1最小，s2次小
{
int x;
*s1=Min(*t,n);
*s2=Min(*t,n);
if((*t)[*s1].weight>(*t)[*s2].weight) //如果s1的权值大于s2的权值，则将两者交换，
//使s1最小，s2次小
{
x=*s1;
*s1=*s2;
*s2=x;
}
}运行结果如图7.36所示。
生成的哈夫曼树如图7.37所示，权值为2、4、7和15的叶子节点的哈夫曼编码分别是000、001、01与1。
在算法的实现过程中，数组HT在初始时的状态及哈夫曼树生成后的状态变化情况如图7.38（a）与（b）所示。
