求哈夫曼树的带权路径长度

1、求哈夫曼树的带权路径长 题目描述： 哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。 输入： 输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2=n=1000）。 输出： 输出权值。 样例输入： 5 1 2 2 5 9 样例输出： 37 来源： 2010年北京邮电大学计算机研究生机试真题 题目解析：由于这是一道机试题目，不可能让你在短短的时间内构造一颗二叉树然后再求解，而且查阅一般的资料（算法导论等）,都很少有构造最优二叉树(也即是哈

2、夫曼树)的方法。因此只能根据构造哈夫曼树的原理来计算这个带权路径长度值。 首先，有必要了解一下哈夫曼树的一些基本概念: 1、 路径长度 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。 图1 从根节点到D节点的路径长度为4 1、 树的路径长度 路径长度就是从树根到每一结点的路径长度之和。 图2 树的路径长度为1+1+2+2+3+3+4+4=20 1、 哈夫曼树: 带权路径长度WPL（Weighted Path Length）最小的二叉树，也称为最优二又树. 例: 上图的WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315 先

3、了解通过刚才的步骤，我们可以得出构造哈夫曼树的算法描述。 1、根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn， 其中每棵二叉树Ti;中只有一个带权为wi的根结点，其左右子树均为空。 2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的.二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和， 中。F中删除这两棵树，同时将新得到的二义树加入F、在3 只含一棵树为止。这棵树便是哈夫曼树.3和F步骤，直到 24重复结合例题说明一下这个算法 3 哈夫曼树的构造过程示意图 图 图4 最终结果 那么可以由上面的哈夫曼树计算出最小带权路径长度 WPL = 1

4、*9 + 2*5 + 3*2 + 4*1 + 4*2 =37 另外还可以有另外一个方法，结合算法描述仔细观察发现最小带权路径长度为非叶子结点的和 ，即 WPL= 19 + 10 +5 +3=37 至于算法的正确性，一下子也想不到什么好的办法来证明，不过应该是可以逻辑推导过来的。 那么要实现这段程序，由上面的算法描述图我们已经知道差不多了，主要分为三步： 直到数组中只有一个数则退出一、排序, 二、最小两个数加起来，即为非叶子节点，累加到累加器中 三、把最小两个数加起来作为一个新的值保存在数组中，去掉最小两个值，跳回第一步 copyview plain cpp 1. #include #include 2. int cmp(const void *a,const void *b) 3. 4. return *(int *)a-*(int5. *)b; 6. int main(void7. ) 8. int9. n,W1001; 10. while(scanf(層,&n)!=EOF) 11. 12. for(int i=1;i=n;i+) 13. scanf(層,&Wi); 14. int Result=0; 15. for(int i=2;i=n;i+) 16. 17. qsort(W+i-1,n-i+2,sizeof(W0),cmp); 18. Resu