以{2,5,8,10,14,25,36}构造赫夫曼树(最优二叉树),并求带权路径长度WPL。

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

1. 将给定的数字按照权值从小到大排序，即{2,5,8,10,14,25,36}。

2. 从权值最小的两个数字开始构造一个新节点，新节点的权值为这两个数字的权值之和。将这个新节点插入到原来的数列中，同时删除这两个数字，得到{10,14,25,36,7}。

3. 重复步骤2，直到只剩下一个节点，即构造完整个赫夫曼树。

构造出来的赫夫曼树如下图所示：

      100
     /   \
    36   64
        /   \
      28    36
     /  \  
    14  14
   /  \
  5    9
 / \
2   3

树的根节点的权值即为所求的带权路径长度WPL，即100。

相关问题

给定一组权值{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。