# include<stdio.h>
# include<stdlib.h>
struct node
{int m;
struct node* lchild;
struct node* rchild;
};
struct node* init(int w[],int n) /*建立数组存放原始的n棵树，初始化，从大到小排*/
{int i,j,t;
struct node* tree;
tree=(struct node*)malloc((n+1)*sizeof(struct node));
for(i=0;i<n;i++)
{tree[i].m=w[i];
tree[i].lchild=NULL;
tree[i].rchild=NULL;
}
for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++)
if(tree[i].m<tree[j].m)
{t=tree[i].m;
tree[i].m=tree[j].m;
tree[j].m=t;
}}
return(tree);
}
struct node* huffman(int w[],int n)　　/*不断合并权值最小的两棵树，插入原数组，最后只剩一棵数时返回*/
{int i,j;
struct node* r;
struct node* tree;
tree=init(w,n);
while(n>1)
{i=0;
r=(struct node*)malloc(sizeof(struct node));
r->lchild=(tree+n-1);
r->rchild=(tree+n-2);
r->m=(tree+n-1)->m+(tree+n-2)->m;
j=n-2;
while((((tree+i)->m)>(r->m))&&(i<(n-2))) i++;
while(j>i) {*(tree+j)=*(tree+j-1);j--;}
*(tree+j)=*r;
n--;
}
return(tree);
}
printtree(struct node* T) /*先序遍历树*/
{if(T)
{printf("%d ",T->m);
printtree(T->lchild);
printtree(T->rchild);
}
}
main()
{int w[3]={1,5,2}; /*权值*/
struct node* head=NULL;
head=huffman(w,3);
printtree(head);
getch();
}