哈夫曼树，我这样构造对不对，如果对，还有另外的一种形式吗？

哈夫曼树，我这样构造对不对，如果对，还有另外的一种形式吗？

八个权值是 5 29 7 8 14 23 3 11

(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)
(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
    取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3) 将新结点N8放入有序序列,保持从小到大排序:
    7 8 N8 11 14 23 29  [注意,新结点N8排在原结点8的后面]
(4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
    结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5) 将新结点N15放入有序序列,保持从小到大排序:
    N8 11 14 N15 23 29
(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
    N8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
    14 N15 N19 23 29
(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
    结点14的数值较小,作为左分支,N15就作为右分支.
(9) 将新结点N29放入有序序列,保持从小到大排序:
    N19 23 29 N29  [注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
    N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
    29 N29 N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
    结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
    N42 N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
    数值较小的N42作为左分支,N58就作为右分支.
    最后得到"哈夫曼树":

              N100
           /       
          N42      N58
         /        /  
        N19  23   29  N29
       /            /  
      N8  11       14   N15
     /                /  
    3    5            7    8

带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29: 10
权值23: 01
权值14: 110
权值11: 001
权值8 : 1111
权值7 : 1110
权值5 : 0001
权值3 : 0000


//C语言测试程序:

//输入叶子结点的总个数: 8
//连续输入8个权值: 5 29 7 8 14 23 3 11
//Weight=5   Code=0001
//Weight=29  Code=10
//Weight=7   Code=1110
//Weight=8   Code=1111
//Weight=14  Code=110
//Weight=23  Code=01
//Weight=3   Code=0000
//Weight=11  Code=001
//huffman's WPL is: 271

#include 
#include 

#define MaxValue 10000  //初始设定的权值最大值
#define MaxBit 10       //初始设定的最大编码位数
#define MaxN 10         //初始设定的最大结点个数
struct HuffNode         //哈夫曼树的结点结构
{
    int weight;//权值
    int flag;//标记
    int parent;//双亲结点下标
    int leftChild;//左孩子下标
    int rightChild;//右孩子下标
};
struct Code//存放哈夫曼编码的数据元素结构
{
    int bit[MaxBit];//数组
    int start;//编码的起始下标
    int weight;//字符的权值
};

//建立叶结点个数为n权值为weight的哈夫曼树huffTree
void Huffman(int weight[], int n, struct HuffNode huffTree[])
{
    int i,j, m1, m2, x1, x2;
    //哈夫曼树huffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
    for (i = 0; i<2 * n - 1; i++)
    {
        if (i        {
            huffTree[i].weight = weight[i];
        }
        else
        {
            huffTree[i].weight = 0;
        }
        huffTree[i].parent = 0;
        huffTree[i].flag = 0;
        huffTree[i].leftChild = -1;
        huffTree[i].rightChild = -1;
    }
    //构造哈夫曼树huffTree的n-1个非叶结点
    for (i = 0; i    {
        m1 = m2 = MaxValue;//Maxvalue=10000;(就是一个相当大的数)
        x1 = x2 = 0;//x1、x2是用来保存最小的两个值在数组对应的下标

        for (j = 0; j        {
            if (huffTree[j].weight            {
                m2 = m1;
                x2 = x1;
                m1 = huffTree[j].weight;
                x1 = j;
            }
            else if(huffTree[j].weight            {
                m2 = huffTree[j].weight;
                x2 = j;
            }
        }
        //将找出的两棵权值最小的子树合并为一棵子树
        huffTree[x1].parent = n + i;
        huffTree[x2].parent = n + i;
        huffTree[x1].flag = 1;
        huffTree[x2].flag = 1;
        huffTree[n + i].weight = huffTree[x1].weight + huffTree[x2].weight;
        huffTree[n + i].leftChild = x1;
        huffTree[n + i].rightChild = x2;
    }
}
//由n个结点的哈夫曼树huffTree构造哈夫曼编码huffCode
void HuffmanCode(struct HuffNode huffTree[], int n, struct Code huffCode[])
{
    struct Code *cd=(struct Code *)malloc(sizeof(struct Code));
    int child, parent;
    int i,j;
    //求n个叶结点的哈夫曼编码
    for (i = 0; i    {
        cd->start = 0;  //从0开始计数
        cd->weight = huffTree[i].weight; //取得编码对应权值的字符
        child = i;
        parent = huffTree[child].parent;
        //由叶结点向上直到根结点
        while (parent != 0)
        {
            if (huffTree[parent].leftChild == child)
            {
                cd->bit[cd->start] = 0; //左孩子结点编码0
            }
            else
            {
                cd->bit[cd->start] = 1; //右孩子结点编码1
            }
            cd->start++; //编码自增
            child = parent;
            parent = huffTree[child].parent;
        }
        //重新修改编码，从根结点开始计数
        for (j = cd->start - 1; j >= 0; j--)
        {
            huffCode[i].bit[cd->start - j - 1] = cd->bit[j];
        }
        huffCode[i].start = cd->start;
        huffCode[i].weight = cd->weight;//保存编码对应的权值
    }
}
int main()
{
    int i, j;
    int m = 0;
    int n = 0;
    int weight[20];

    printf("输入叶子结点的总个数: ");
    scanf("%d",&n);
    printf("连续输入%d个权值: ",n);
    for(i=0;i    {
        scanf("%d",&weight[i]);
    }
struct HuffNode *myHuffTree=(struct HuffNode *)malloc((2*n-1)*sizeof(struct HuffNode));
struct Code *myHuffCode=(struct Code *)malloc(n*sizeof(struct Code));
    if (n>MaxN)
    {
        printf("
定义的n越界，修改MaxN!
");
        exit(0);
    }
    Huffman(weight, n, myHuffTree);
    HuffmanCode(myHuffTree, n, myHuffCode);
    //输出每个叶结点的哈夫曼编码
    for (i = 0; i    {
        printf("Weight=%-4dCode=",myHuffCode[i].weight);
        for (j = 0; j        {
            printf("%d",myHuffCode[i].bit[j]);
        }        m = m + myHuffCode[i].weight*myHuffCode[i].start;

        printf("
");
    }
    printf("huffman's WPL is: %d
",m);

getchar();

    return 0;
}

对，还有很多种，不过能写出来一种就行了