Huffman树的创建

//Author: Guo R.H
//Date:06.12.28
//      USTC

#include
#include

typedef struct
{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HTree;

int Min(HTree HT, int i)
{//返回i个节点中权值最小节点的序号
    int f, j;
    int k = 100;
    for(j=0; j    {
        if(HT[j].weight        {
            k = HT[j].weight;
            f = j;
        }
    }
    HT[f].parent = 1;
    return f;
}
void Select(HTree HT, int i, int *s1, int *s2)
{//找出两个最小的权值
    int t;
    *s1 = Min(HT, i);
    *s2 = Min(HT, i);
    if(*s1 > *s2)
    {
        t = *s1;
        *s1 = *s2;
        *s2 = t;
    }
}
void CreateHTree(HTree *HT, int n, int *w)
{//创建huffman树
    int i, j, m, s1, s2;
    m = 2*n-1;
    *HT = (HTree)malloc(m*sizeof(HTNode));
    for(i=0; i    {
        (*HT+i)->weight = *(w+i);
        (*HT+i)->parent = 0;
        (*HT+i)->lchild = 0;
        (*HT+i)->rchild = 0;        
    }
    for(; i        (*HT+i)->weight = 0;
    for(i=n; i    {
        Select(*HT, i, &s1, &s2);
        (*HT+i)->weight = (*HT+s1)->weight+(*HT+s2)->weight;
        (*HT+i)->parent = 0;
        (*HT+i)->lchild = s1;
        (*HT+i)->rchild = s2;
        (*HT+s1)->parent = i;
        (*HT+s2)->parent = i;        
    }
    for(j=0, i=0; i        printf("%d:  %d %d %d %d\n", j++, (*HT+i)->weight, (*HT+i)->parent, (*HT+i)->lchild, (*HT+i)->rchild);
}

int main()
{
    HTree HT;
    int *w, i, n;
    printf("please input the number of weights: ");
    scanf("%d", &n);
    w = (int *)malloc(n*sizeof(int));
    for(i=0; i        scanf("%d", w+i);
    CreateHTree(&HT, n, w);
    return 0;
}