哈弗曼树(3)

#include<stdio.h>
#define max 100
#define n 5
typedef struct No{
double weight;
int lchild,rchild,parent;
} hufmNode;
hufmNode tree[n];
void creathufm()
{
int i,j,p1,p2;
double min1,min2;
for(i=0;i<n*2-1;i++){//初始化
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].parent=0;
tree[i].weight=0;
}
for(i=0;i<n;i++) //父节点的位置
scanf("%lf",&tree[i].weight);
for(i=n;i<2*n-1;i++){//找出子节点最小的两个
min1=min2=max;
p1=p2=0;
for(j=0;j<i;j++)
if(tree[j].parent==0)//选没有父亲的节点
if(min1>tree[j].weight){
p2=p1;
min2=min1;
p1=j;
min1=tree[j].weight;
}
else if(tree[j].weight>min2){
p2=j;
min2=tree[j].weight;
}
tree[j].lchild=p1+1;//分别写入左右孩子,和父亲
tree[j].rchild=p2+1;
tree[p1].parent=i+1;
tree[p2].parent=i+1;
tree[j].weight=tree[p1].weight+tree[p2].weight;
}
for(i=0;i<2*n-1;i++)
printf("%.2lf ",tree[i].weight);
}
main()
{
creathufm();
return 0;
}

发表评论