void HuffmanCoding(int *w,int n)
{
    //w存放n个字符的权值（均>0),构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
    if(n<=1)return;
    HTNode *HT;
    char *HC;    
    HTNode *p;
    int  m,f,s1,s2,count=0,sum=0,j=0;
    m=2*n-1;
    HT=(HTNode*)malloc((m+1)*sizeof(HTNode));
    p=HT;//
    (*p).Node(0,0,0,0);//
    p++;//这书上没有写
    for(int i=1;i<=n;i++,++p,++w){(*p).Node(*w,0,0,0);};
    for(;i<=m;++i,++p){(*p).Node(0,0,0,0);};
    for(i=n+1;i<=m;i++)
    {
        Select(HT,i-1,s1,s2);
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        HT[s1].parent=HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
    }
    //从叶子到根逆向求出每个字符的赫夫曼编码
    //我的想法是把所有左孩子为零的结点（叶子），赫夫曼编码逆序列出
    printf("从叶子到根逆向求出每个字符的赫夫曼编码");
    HC=(char*)malloc((n+1)*sizeof(char));
    for(i=1;i<=n;i++)
    {
        if(HT[i].lchild==0)
        {
            f=i;
            j=HT[f].parent;
            printf("\n");
            while(HT[f].parent!=0)
            {
                if(HT[j].lchild==f)
                {
                    printf("0 ");
                }
                if(HT[j].rchild==f)
                {
                    printf("1 ");
                }
                f=j;
                j=HT[f].parent;
            }
        }

    }
    printf("\nHT的终态为：\n");
    for(i=1;i<=m; i++)
    {
        printf("\n%d  ",i);
        HT[i].print();
        printf("\n");
    }
    printf("\nHT的结点终态及结点的路径长度为：\n");
    printf("NO. weight parent lchild rchild 结点的路径长度");
    for(i=1;i<=m; i++)
    {
        count=0;
        if(HT[i].lchild==0)
        {
            f=i;
            while(HT[f].parent!=0)
            {
                count++;
                f=HT[f].parent;
            }
            printf("\n%d  ",i);
            HT[i].print();
            printf("%d ",HT[i].weight*count);
            sum+=HT[i].weight*count;
        }
    }
    //树的带权路径长度为
    printf("\n\n");
    printf("\n树的带权路径长度为:%d",sum);
    printf("\n\n");
}
void main()
{
    int a[8]={5,29,7,8,14,23,3,11};
    int n=8;
    HuffmanCoding(a,n);
}

这个算法的//从叶子到根逆向求出每个字符的赫夫曼编码部分不是用书上的算法做，我的程序和6。12算法在从叶子到根逆向求出每个字符的赫夫曼编码上写的都不好，更好的是6。13算法所描述的（高效且站用空间少），强烈建议有时间的朋友，//从叶子到根逆向求出每个字符的赫夫曼编码用6。13算法来实现下，让我们共同进步。

mark

寒