给定一组权值{7,9,5,6,10,1,13,15,4,8}，构造一棵赫夫曼树，并计算带权路径长度WPL

好的，根据构造哈夫曼树的步骤，我们可以先将这些权值从小到大排序，得到{1,4,5,6,7,8,9,10,13,15}。

然后，我们选取权值最小的两个节点1和4，构造出一棵新的二叉树，其中左子树为权值为1的节点，右子树为权值为4的节点。这棵新树的根节点的权值为5，表示左右两棵子树的权值之和。

接着，我们将这棵新树作为一个整体，与权值为5的节点合并。这样我们得到一棵新的二叉树，其根节点的权值为10，表示左右两棵子树的权值之和。

以此类推，直到所有节点都被合并成一棵树。最后得到的哈夫曼树如下所示：

        70
     /      \
    29      41
   /  \    /  \
  13  16  18  23
 / \   |   |   |
6   7  8   10  13

计算带权路径长度的方法为：将每个叶子节点的权值乘以其到根节点的路径长度，再将所有结果相加。因此，WPL为：

WPL = 6*2 + 7*2 + 8*2 + 10*2 + 13*2 + 13*2 + 16*1 + 18*1 + 23*1 + 29*1 = 201

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

相关问题

设给定权值2，3，4，7，8，9，试构造一棵赫夫曼树，并求其加权路径长度wpl

首先，我们需要先将给定的权值按照从小到大的顺序排序，得到 2，3，4，7，8，9。

接下来，我们需要构造一棵哈夫曼树，步骤如下：

1. 将所有权值作为叶子节点，按照权值从小到大的顺序排列。

2. 从权值最小的两个叶子节点中选出权值最小的两个节点作为左右子节点，构建一棵新的二叉树，根节点的权值为左右子节点的权值之和。

3. 将构建的新二叉树插入到原来的序列中，保持序列有序。

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

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

       33
      /  \
     /    \
    13    20
   / \    / \
  5   8  9   11

其中，数字表示节点的权值，树的根节点是33，加权路径长度wpl为：

wpl = 2*5 + 3*3 + 4*3 + 7*2 + 8*2 + 9*2 = 64

因此，给定权值2，3，4，7，8，9的哈夫曼树的加权路径长度为64。

设给定权值{2，3，4，7，8，9}，试构造一棵赫夫曼树，并求其加权路径长度WPL.

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

1.将给定的权值从小到大排序，得到{2, 3, 4, 7, 8, 9}。

2.从中选取权值最小的两个数字，即2和3，构造一棵二叉树，其根节点的权值为2+3=5。该二叉树的左子树为权值为2的叶子节点，右子树为权值为3的叶子节点。

3.将刚才构造的二叉树从权值列表中删除，将该二叉树的根节点，即权值为5的节点插入权值列表中。

4.重复步骤2和步骤3，直到权值列表中只剩下一个节点，这个节点即为整棵赫夫曼树的根节点。

根据上述步骤，可以得到下面这棵赫夫曼树：

        38
       /  \
     17    21
     / \   / \
    8   9  10 11
   / \
  3   5

其中，根节点的权值为WPL=38。

注：WPL指的是赫夫曼树中所有叶子节点的权值乘以其到根节点的路径长度之和。