对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。

好的，根据您提供的权值 W=(5,2,9,11,8,3,7)，我们可以构造哈夫曼树如下：

            45
        /        \
       /          \
      20           25
     /  \         /  \
    9    11      8    17
   / \          / \
  4   5        3   5

树的带权路径长度为 5*3 + 2*4 + 9*2 + 11*2 + 8*2 + 3*3 + 7*3 = 141。

相关问题

对给定的一组权值W=(1,2,3,7,20,3,2,4,8,10),试构造相应的哈夫曼树，并计算它的带权路径长度

好的，我会根据您的要求回答您的问题。

对于给定的权值W=(1,2,3,7,20,3,2,4,8,10)，可以按照以下步骤构造相应的哈夫曼树：

1. 将权值从小到大进行排序，得到W'=(1,2,2,3,3,4,7,8,10,20)。

2. 取出W'中权值最小的两个节点1和2，构造出新节点(1,2)，其权值为1+2=3。

3. 将(1,2)节点插入W'中，并删除原来的1和2节点，得到W''=(3,2,3,4,7,8,10,20)。

4. 重复步骤2和3，直到W''中只剩下一个节点，即哈夫曼树的根节点为止。

最后构造出的哈夫曼树如下所示：

58
/ \
/ \
/ \
/ \
/ \
/ \
33 25
/ \ / \
12 21 10 15
/\ /\
3 9 8 13

哈夫曼树的带权路径长度为58，即每个叶子节点权值与根节点的距离之积的总和。

带权路径长度的计算方法如下：

节点 权值 距离 权值*距离
3 1 3 3
9 2 2 4
8 2 2 4
13 3 1 3
10 7 1 7
15 20 1 20
25 3 2 6
33 4 2 8
58 10 1 10
总和 58

因此，哈夫曼树的带权路径长度为58。

2、给定一组权值：3，3，7，7，11，13，17，试构造一棵哈夫曼树，并计算出带权路径长度。

首先将权值从小到大排列，得到3，3，7，7，11，13，17。

然后将相邻的两个权值合并成一个节点，权值为它们的和，得到6，14，18，11，13，17。此时，又将相邻的两个节点合并，得到20，29，11，13，17。最后，将20和29合并，得到49，构成了一棵哈夫曼树。

根据哈夫曼树的定义，带权路径长度是每个叶子节点的权值乘以它到根节点的路径长度之和，再将所有叶子节点的结果相加。因此，可以计算出带权路径长度为：

3*3 + 3*3 + 7*2 + 7*2 + 11*2 + 13*2 + 17*2 = 109

因此，构造的哈夫曼树的带权路径长度为109。