查人人中国名人网教案活动反思怎么写:哈夫曼树的建立、编解码
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/24 13:41:32
要求：建立函数输入二叉树，并图形化输出其赫夫曼树
上缴资料中请写明 存储结构 基本算法（可使用程序流程图） 输入输出 源程序 测试数据和结果 算法的时间复杂度
谢谢！～
typedef struct{
int weight;
int flag;
int parent;
int leftchild;
int rightchild;
} haffnode;
typedef struct
{
int bit[MAXN];
int start;
int weight;
}code;
void haffman(int weight[],int n,haffnode hafftree[])
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)hafftree[i].weight=weight[i];
else hafftree[i].weight=0;
hafftree[i].parent=-1;
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{
m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{
m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;
}
}