huffman树编码

void select(HTnode *HT,int n,int *s1,int *s2){
    int i,min;
    min=INF;
    for(i=1;i<n;i++)if(HT[i].weight<min&&HT[i].parent==0){
        *s1=i;
        min=HT[i].weight;
    }
    min=INF;
    for(i=1;i<n;i++)if(i!=*s1&&HT[i].weight<min&&HT[i].parent==0){
        *s2=i;
        min=HT[i].weight;
    }
    if(*s1>*s2)swap(*s1,*s2);
}

void HuffmanCoding(HTnode *HT,char HC[][N],int w[],int n){
    int m=n*2-1;
    int i,j,k,s1,s2;
    int c,f;
    HT=(HTnode*)malloc((m+1)*sizeof(HTnode));
    for(i=1;i<=n;i++)HT[i].weight=w[i-1],HT[i].parent=HT[i].l=HT[i].r=0;
    for(i=n+1;i<=m;i++)HT[i].weight=HT[i].parent=HT[i].l=HT[i].r=0;    
    for(i=n+1;i<=m;i++){
        select(HT,i,&s1,&s2);
        HT[i].l=s1,HT[i].r=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        HT[s1].parent=HT[s2].parent=i;
    }    
    char t[N];
    for(i=1;i<=n;i++){
        k=0;
        t[i]=NULL;
        for(c=i,f=HT[c].parent;f!=0;c=f,f=HT[f].parent){
            if(HT[f].l==c)t[k++]=‘0‘;
            else t[k++]=‘1‘;
        }
        t[k]=‘\0‘;
        reverse(t,t+k);
        strcpy(HC[i],t);
    }
}