typedef struct{
int wiget;
int lchild,rchild,parent;
int data;
}HNode,*HTree;
void select(HTree &H,int i,int &s1,int &s2){
int tmp,min1,min2=0;
int j;
for(j=1;j<=i;j++)
{
if(H[i].parent==0)
{
min1=i;
break;
}
}
for(j=1;j<=i;j++)
{
if(H[i].parent==0&&i!=min1)
{
min2=i;
break;
}
}
if(H[min2].wiget<H[min1].wiget)
{
tmp=min1;
min1=min2;
min2=tmp;
}
for(j=1;j<=i;j++){
if(H[i].parent==0)
{
if(H[i].wiget<=H[min2].wiget&&i!=min1&&i!=min2)
{
min2=i;
if(H[min2].wiget<H[min1].wiget)
{
tmp=min1;
min1=min2;
min2=tmp;
}
}
}
}
return 0;
}
int init_hufuman_tree(HTree &H,int n,int *w){
int m=2n+1,i,s1,s2;
if(n<=1) return 1;
if(!H=(HTree)malloc((m+1)sizeof(HNode))) return 1;
for(i=1;i<=n;i++,w++) H[i]=(*w,0,0,0,0);
for(i=n+1;i<=m;i++) H[i]=(0,0,0,0,0);
for(i=n+1;i<=m;i++){
select(H,i-1,&s1,&s2);
H[s1].parent=i;H[s2].parent=i;
H[i].wiget=H[s1].wiget+H[s2].wiget;
H[i].lchild=s1;H[i].rchild=s2;
}
return 0;
}
int get_Hucode(HTree &H,int n){
int j,i,c,f,start;
char *cd=NULL;
char **Hcode=(char**)malloc((n+1)sizeof(char*));
if(!Hcode)return 1;
Hcode[]=NULL;
if(!cd=(char*)malloc((n+1)*sizeof(char)))return 1;
cd[n]=‘/0‘;
start=n-1;
for(i=1;i<=n;i++)
{
for(c=i,f=H[c].parent;f!=0;c=f,f=H[f].parent){
if(H[f].lchild==c) {cd[start]=‘0‘;start--;}
else{cd[start]=‘1‘;start--}
}
char *code=(char*)malloc((n-start)sizeof(char));
if(!code) return 1;
strcpy(code,&char[start]);
start=n-1;
Hcode[i]=code;
}
free(cd);
return 0;
}
}
数据结构之哈夫曼树
原文：http://blog.csdn.net/hjgblog/article/details/38168167
