void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT,并求出n个字符的赫夫曼编码HC
{
int i,start,c,f,m,w;
int p1,p2;
char *cd,z;
if(n<=1){
return;
}
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i) //初始化n个叶子结点
{
printf("请输入第%d字符信息和权值:",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
{
continue;
}
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='0';
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建立赫夫曼树
{
Select(HT,i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}
HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //给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';
}
else
{
cd[--start]='1';
}
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void display( hfmtree &HT)
{
hfmtree stack[100],p;
int level[100],top,n,i;
if(HT!=NULL)
{
cout<<"用凹入表表示二叉树:"<<endl;
top=1;
stack[top]=HT;
level[top]=3;
while(top>0)
{
p=stack[top];
n=level[top];
for(i=1;i<=n;i++)
cout<<" ";
cout<<p->ch;
top--;
if(p->rchild!=NULL)
{
top++;
stack[top] =p->rchild;
level[top]=n+3;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top]=n+3;
}
}
}
}