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

《求哈夫曼树的带权路径长度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、刚才的步骤，我们可以得出构造哈夫曼树的算法描述。1、根据给定的n个权值{w[1],w[2],…,w[n]}构成n棵二叉树的集合F={T[1],T[2],…T[n]}，  其中每棵二叉树T[i];中只有一个带权为w[i]的根结点，其左右子树均为空。2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的.二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和，3、在F中删除这两棵树，同时将新得到的二义树加入F中。4重复2和3步骤，直到F只含一棵树为止。这棵树便是哈夫曼树.结合例题说明一下这个算法图3哈夫曼树的构造过程示意图图4最终结果那么可

4、以由上面的哈夫曼树计算出最小带权路径长度WPL=1*9+2*5+3*2+4*1+4*2=37 另外还可以有另外一个方法，结合算法描述仔细观察发现最小带权路径长度为非叶子结点的和，即WPL=19+10+5+3=37至于算法的正确性，一下子也想不到什么好的办法来证明，不过应该是可以逻辑推导过来的。那么要实现这段程序，由上面的算法描述图我们已经知道差不多了，主要分为三步：一、排序,直到数组中只有一个数则退出二、最小两个数加起来，即为非叶子节点，累加到累加器中三、把最小两个数加起来作为一个新的值保存在数组中，去掉最小两个值，跳回第一步[cpp] viewplain

5、 copy1.#include  2.#include  3.int cmp(const void *a,const void *b)  4.{  5.    return *(int *)a-*(int *)b;  6.}  7.int main(void)  8.{  9.    int n,W[1001];  10.    while(scanf("%d",&n)!=EOF)  11.    {  12.        for(int i=1;i<=n;i++)  13.            scanf("%d

6、",&W[i]);  14.        int Result=0;  15.        for(int i=2;i<=n;i++)  16.        {  17.            qsort(W+i-1,n-i+2,sizeof(W[0]),cmp);  18.            Result+=W[i]+W[i-1];  19.            W[i]=W[i]+W[i-1];  20.        }  21.        printf("%d",Result);  22.    }  23.    return

7、 0;  24.}