哈夫曼树

#include <stdio.h>
#include <stdlib.h>
#define max 1e9
typedef struct hnode{
    int weight;
    int lchild;
    int rchild;
    int parent;
    char s[1000];
}huffNode;
void select(huffNode huffmanTree[ ], int k, int *s1, int *s2);
//从huffmanTree数组的0到up-1中找出father为-1的且权重最小的结点赋给s1,s2,（为了保证答案唯一，请让s1的结点编号小于s2）
void CreateHuffTree(huffNode huffmanTree[ ], int W[ ], int N );
//创建哈夫曼树，W为权重数组，N为叶子结点个数
void code(huffNode huffmanTree[],int N){
    int i;
    for(i=N-1;i>=0;i--){
        char Code[1000];
        int start=0;
        int c=i;//记录下当前结点
        int j=huffmanTree[i].parent;//记录当前叶子结点的父结点
        while(j!=-1){//遍历到根结点
            if(huffmanTree[j].lchild==c)
            Code[start++]='0';
            else Code[start++]='1';
            c=j;
            j=huffmanTree[j].parent;
        }
        int q;
        for(q=1;q<=start;q++)
        huffmanTree[i].s[q-1]=Code[start-q];
    }

}
void printcode(huffNode huffmantree[],int N){
    int i,j;
    for(i=0;i<N;i++){
        printf("%d code:%s\n",huffmantree[i].weight,huffmantree[i].s);
    }
}
int main(){

    huffNode *ht;

    int i,N,*W;
    scanf("%d", &N);

    W = (int*)malloc (N * sizeof(int));
    ht=(huffNode *)malloc((2*N-1)*sizeof(huffNode));

    for(i = 0; i < N; i++)
        scanf("%d", &W[i]); //4

    CreateHuffTree(ht,W,N);//1 2 3 4
     printf("    weight   parent   lchild    rchild\n");
    for (i = 0; i < 2 * N - 1; i++) {
        printf("%d     %d      %d        %d        %d\n",i,ht[i].weight, ht[i].parent, ht[i].lchild, ht[i].rchild);
    }
    code(ht,N);
    printf("\nhuffman code:\n");
    printcode(ht,N);
    free(W);
    free(ht);
    return 0;
}
void CreateHuffTree(huffNode huffmanTree[ ], int W[ ], int N ) {
       int i,i1,i2,k;
       for (i = 0; i < N; i++) {   //叶子结点初始化
            huffmanTree[i].parent = -1;
            huffmanTree[i].lchild = -1;
            huffmanTree[i].rchild = -1;
            huffmanTree[i].weight = W[i];
       }
       for (k = N; k < 2*N-1; k++) {
            select(huffmanTree,k, &i1, &i2);
            huffmanTree[k].weight = huffmanTree[i1].weight+huffmanTree[i2].weight;
            huffmanTree[k].lchild = i1; huffmanTree[k].rchild = i2;
            huffmanTree[k].parent=-1;
            huffmanTree[i1].parent = k; huffmanTree[i2].parent = k;
    }
}
void select(huffNode huffmanTree[ ], int k, int *s1, int *s2)
{
    int i;
    int n,m;
    n=m=max;
    for(i=0;i<k;i++){
        if(huffmanTree[i].parent==-1)//未选中的结点
        if(huffmanTree[i].weight<n){
            n=huffmanTree[i].weight;
            *s1=i;
        }
    }
    for(i=0;i<k;i++){
        if(huffmanTree[i].parent==-1)
        if(huffmanTree[i].weight<m&&i!=*s1){
            m=huffmanTree[i].weight;
            *s2=i;
        }
    }
}// 从huffmanTree数组的0到up-1中找出father为-1的且权重最小的结点赋给s1,s2