60分看个 简单的算法

C/C++ code

void Haffman(int weight[], int n, HaffNode haffTree[])　　//建立叶结点个数为n权值为weight的哈夫曼树haffTree　　{　　int j, m1, m2, x1, x2;　　//哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点　　for(int i = 0; i < 2 * n - 1 ; i++)　　{　　if(i < n)　　haffTree[i].weight = weight[i];　　else haffTree[i].weight = 0;　　haffTree[i].parent = 0;　　haffTree[i].flag = 0;　　haffTree[i].leftChild = -1;　　haffTree[i].rightChild = -1;　　}　　//构造哈夫曼树haffTree的n-1个非叶结点　　for(int i = 0;i < n-1;i++)                   //为什么说这里是创建n-1个非叶节点，不是n个叶子节点啊???             　　{　　m1 = m2 = MaxValue;　　x1 = x2 = 0;　　for(j = 0; j < n+i;j++)                       //这里的for循环的次数是怎么计算出来的，haffTree数组是n个，为什么可以使用下标到n+i啊????　　{　　if (haffTree[j].weight < m1 && haffTree[j].flag == 0)　　{　　m2 = m1;　　x2 = x1;　　m1 = haffTree[j].weight;　　x1 = j;　　}　　else　　if(haffTree[j].weight < m2 && haffTree[j].flag == 0)　　{　　m2 = haffTree[j].weight;　　x2 = j;　　}　　}　　//将找出的两棵权值最小的子树合并为一棵子树　　haffTree[x1].parent = n+i;　　haffTree[x2].parent = n+i;　　haffTree[x1].flag = 1;　　haffTree[x2].flag = 1;　　haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight;　　haffTree[n+i].leftChild = x1;　　haffTree[n+i].rightChild = x2;　　}　　}

问题已经在代码中表示出来了，



[解决办法]
//为什么说这里是创建n-1个非叶节点，不是n个叶子节点啊???
答：哈弗曼编码生成的树是一棵特别的树：每个节点要么拥有2个子节点，要么是叶子节点。而二叉树有一个性质：叶子节点个数n0,只有一个子节点的个数n1,拥有两个子节点的个数为n2。公式：n0+n1+n2 = n1 + 2* n2 +1
化简后就是n0 = n2+1 那么 n2 = n0 -1