由权值分别为 9、2、5、7、4的5个叶子结点构造一棵哈夫曼树，则该树的带权路径长度是多少

首先，我们需要构造哈夫曼树。哈夫曼树的构造过程是：每次从权值最小的两个叶子结点中选取一个作为左子树，另一个作为右子树，然后将它们的权值相加作为它们的父节点的权值，重复这个过程直到所有的叶子结点都被合并成一个根节点。

按照这个过程，我们可以得到如下的哈夫曼树：

       27
     /    \
    11     16
   /  \   /  \
  4    5  7   9

其中，根节点的权值是所有叶子结点权值之和，即 9+2+5+7+4=27。另外，每一个非叶子节点的权值是其左右子树权值之和。

接下来，我们需要计算带权路径长度。带权路径长度是指所有叶子结点深度乘以其权值之和，也就是：

4*1 + 5*2 + 7*2 + 9*2 + 9*3 = 4 + 10 + 14 + 18 + 27 = 73

因此，该哈夫曼树的带权路径长度是 73。

相关问题

有七个带权结点，其权值分别为7,13,8,2,9,10，14，试以它们为叶子结点构造一棵哈夫曼树（要求满足左孩子权值不超过右孩子权值的原则)。请画出该哈夫曼树，并计算其带权路径长度WPL. 给出计算过程

为了构造哈夫曼树，我们首先需要对这七个节点按照权值升序排列，然后应用贪心策略：每次选择两个权值最小的节点合并，并将它们的新权值作为新节点的权值，其中新节点的左子节点是较小的那个，右子节点是较大的那个。直到只剩下一个节点为止，这就是哈夫曼树的根节点。

按照你提供的权值从小到大排序：
1. 2
2. 7
3. 8
4. 9
5. 10
6. 13
7. 14

我们可以逐步合并：

1. 第一轮：(7, 2) -> (9, 1) （9是新权值，1作为左孩子的权重）
2. 第二轮：(9, 1) 和 (8, 0) -> (17, 1) （17是新权值，1作为左孩子的权重）
3. 第三轮：(17, 1) 和 (9, 1) -> (26, 2) （26是新权值，2作为左孩子的权重）
4. 第四轮：(26, 2) 和 (13, 0) -> (40, 2) （40是新权值，2作为左孩子的权重）
5. 第五轮：(40, 2) 和 (10, 0) -> (50, 3) （50是新权值，3作为左孩子的权重）
6. 第六轮：(50, 3) 和 (14, 0) -> (64, 3) （64是新权值，3作为左孩子的权重）

最终结果是：

        64
       / \
      50   14
     / \   / \
    40  10  13
   / \   \
  26   17   8

带权路径长度 WPL（Weighted Path Length）可以通过计算从根到每个叶节点的所有边的权值之和得出。由于哈夫曼树是对称的，每一条从叶子到根的路径的权值都等于对应的另一条从根到叶子的路径的权值。所以，WPL = 2 * (2 + 1 + 1 + 1 + 3 + 3 + 3) = 2 * 14 = 28。

由权值分别为3，6，8，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

哈夫曼树是一种带权路径长度最短的树，可以通过贪心算法构造。具体步骤如下：

1. 将所有节点按权值从小到大排序。
2. 取出权值最小的两个节点，构建一棵新的二叉树，其中较小的节点为左子树，较大的节点为右子树，并将新树的根节点的权值设为左右子树权值之和。
3. 将新树插入到排序后的节点序列中，并更新权值排序序列。
4. 重复步骤 2 和 3，直到序列中只剩下一棵哈夫曼树。

根据上述步骤，可以得到如下的哈夫曼树：

      24
     /  \
    10   14
   /  \   
  4    6 
 / \
3   1

其中，叶子节点的权值分别为 3、6、8、2、5，带权路径长度为每个叶子节点的权值乘以到根节点的路径长度之和，即：

3*3 + 6*2 + 8*2 + 2*3 + 5*3 = 3 + 12 + 16 + 6 + 15 = 52

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