10. 由权值为 15,3,5,10 的四个叶结点构成的哈夫曼树的带权路径长度为（ ）。 A.46 B.59 C.66 D.88

构造哈夫曼树的过程如下：

1. 将四个叶结点看成树，权值分别为 15、3、5、10。此时共有四棵树。

2. 取出权值最小的两棵树，进行合并，得到一棵新树，根的权值为两棵树的权值之和。这里选择 3 和 5，合并后得到一棵权值为 8 的新树，共有三棵树。

3. 取出权值最小的两棵树，进行合并，得到一棵新树，根的权值为两棵树的权值之和。这里选择 8 和 10，合并后得到一棵权值为 18 的新树，共有两棵树。

4. 取出权值最小的两棵树，进行合并，得到一棵新树，根的权值为两棵树的权值之和。这里选择 15 和 18，合并后得到一棵权值为 33 的新树，共有一棵树。

哈夫曼树构造完毕。带权路径长度为 $15\times 1+3\times 2+5\times 2+10\times 2+8\times 3+18\times 3+33\times 3=59$，因此选项 $\textbf{(B)}$ 正确。

相关问题

由分别带权为3.9.6.2.5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为(

生成哈夫曼树的步骤如下：
1. 将权值从小到大排列，得到 2,3,5,6,9。
2. 取出权值最小的两个节点，将它们合并成一个新节点，新节点的权值为两个节点的权值之和，并将新节点放回权值序列中。
3. 重复步骤 2，直到所有节点都被合并为一个根节点，得到哈夫曼树。

按照上述步骤，我们可以得到以下哈夫曼树：

       25
      /  \
     /    \
    11    14
   /  \   
  /    \  
 5      6  
/ \    
2   3   

根据哈夫曼树的定义，带权路径长度（WPL）是每个叶子节点的权值乘以到根节点的路径长度之和。因此，这棵哈夫曼树的带权路径长度为：

WPL = 2*5 + 3*5 + 5*4 + 6*4 + 9*3 = 73

因此，它的带权路径长度为73。

由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为

56。

解释：

首先将四个叶子结点按照权值从小到大排序，得到2、5、7、9。

然后将权值最小的两个结点2和5合并，得到一个新的结点7，其权值为2+5=7。

接着将权值最小的两个结点7和7合并，得到一个新的结点14，其权值为7+7=14。

最后将权值最小的两个结点9和14合并，得到根节点，其权值为9+14=23。

根据哈夫曼树的定义，带权路径长度为每个叶子结点的权值乘以该结点到根节点的路径长度之和，因此：

2的路径长度为3，带权路径长度为2*3=6；

5的路径长度为2，带权路径长度为5*2=10；

7的路径长度为1，带权路径长度为7*1=7；

9的路径长度为2，带权路径长度为9*2=18。

将四个叶子结点的带权路径长度相加，得到56，即该哈夫曼树的带权路径长度为56。