有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造一棵赫夫曼树，并计算其WPL。

构造赫夫曼树的步骤如下：

1. 将带权结点按权值从小到大排序，得到{2, 4, 5, 7, 8, 16, 30}。

2. 取出权值最小的两个结点，将它们合并成一个新的结点，新结点的权值为这两个结点的权值之和。这里是2和4，合并后得到一个新结点6。

3. 将新结点6插入到原来的序列中，得到{5, 6, 7, 8, 16, 30}。

4. 重复步骤2和3，直到序列中只剩下一个结点，这个结点就是赫夫曼树的根节点。

按照上述步骤，构造出的赫夫曼树如下图所示：

          72
         /  \
       30   42
           /  \
         16   26
            /   \
          11    15
          / \   / \
         5   6  7  8
        / \
       2   3

计算WPL的方法是将每个叶子结点的权值乘以它到根节点的距离，再将所有叶子结点的结果相加。因此，这棵赫夫曼树的WPL为：

2×5 + 3×5 + 5×4 + 6×4 + 7×3 + 8×3 + 11×2 + 15×2 + 16×2 + 30×1 = 288

因此，这棵赫夫曼树的WPL为288。

相关问题

有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造一棵赫夫曼树

赫夫曼树的构建过程如下：

1. 将结点按照权值从小到大排序，得到 2，4，5，7，8，16，30。
2. 从中选取权值最小的两个结点 2 和 4，构造一棵二叉树，其根节点的权值为 2 + 4 = 6，将这棵树看作一个结点，权值为 6。
3. 将上一步构造的结点和权值为 5 的结点组成新的二叉树，其根节点的权值为 5 + 6 = 11，将这棵树看作一个结点，权值为 11。
4. 将上一步构造的结点和权值为 7 的结点组成新的二叉树，其根节点的权值为 7 + 11 = 18，将这棵树看作一个结点，权值为 18。
5. 将上一步构造的结点和权值为 8 的结点组成新的二叉树，其根节点的权值为 8 + 18 = 26，将这棵树看作一个结点，权值为 26。
6. 将上一步构造的结点和权值为 16 的结点组成新的二叉树，其根节点的权值为 16 + 26 = 42，将这棵树看作一个结点，权值为 42。
7. 将上一步构造的结点和权值为 30 的结点组成新的二叉树，其根节点的权值为 30 + 42 = 72，将这棵树看作一个结点，权值为 72。
8. 构造完成，得到一棵赫夫曼树，其根节点的权值为 72。树的形态如下所示：

      72
     /  \
    42  30
   /  \
  18  16
 /  \
7   11
  /   \
 5    6
      / \
     2   4

有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，画出哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。

首先将带权值的叶子节点按照权值从小到大排序，得到以下序列：

3，2，6，7，8，10，14

接着，每次选择权值最小的两个节点，合并成一个新节点，权值为它们的和，直到最后只剩下一个节点为止。在合并过程中，新节点的左节点为权值较小的节点，右节点为权值较大的节点。

按照上述合并方式，可以得到以下哈夫曼树：

            50
           /  \
         18   32
        /     /  \
       8    14   18
      / \     |    |
     3  5    6    8

带权路径长度为：$3\times2+2\times3+6\times2+7\times2+8\times2+10\times2+14\times2=124$

高度为：4

双分支结点数为：6