设一组权值集合W=(14, 3, 14, 1, 6, 8, 16, 18)，要求根据这些权值集合构造棵哈夫曼树， 规定每个结点左孩子小于等于右孩子，则这棵哈夫曼树的带权路径长度为_ (1)_ 。这棵哈夫曼树上权值最小的叶子到树根的长度是_ (2) (注意: 用阿拉伯数字表示)

(1) 哈夫曼树的带权路径长度为：$14\times1+3\times2+14\times2+1\times3+6\times3+8\times3+16\times3+18\times3=153$。

(2) 权值最小的叶子节点为权值为1的节点，它到树根的路径为：左孩子-右孩子-左孩子-右孩子-右孩子，共5个边，所以长度为5。

相关问题

设一组权值集合W=（3，2，6，9，5），要求根据这些权值集合构造一棵哈夫曼树，则这颗哈夫曼树的带权路经长度为

根据哈夫曼树的构造方法，先将权值集合按照从小到大的顺序排序，然后依次选取权值最小的两个节点合并，生成一个新的节点，其权值为两个节点的权值之和，直到最后只剩下一个节点，即为哈夫曼树的根节点。

在此过程中，每个节点都会被遍历到，且每个节点都会与其父节点连接一条边，因此可以计算出每个节点到根节点的路径长度，再将每个节点的路径长度乘以其权值，累加所有节点的路径长度乘以权值，即可得到哈夫曼树的带权路径长度（WPL）。

例如，对于给定的权值集合W=（3，2，6，9，5），按照从小到大的顺序排序后得到（2，3，5，6，9），则哈夫曼树的构造过程如下图所示：


根据节点的权值和路径长度，可以计算出每个节点的路径长度乘以权值，得到如下表格：

|节点|权值|路径长度|路径长度乘以权值|
|---|---|---|---|
|a|2|2|4|
|b|3|2|6|
|c|5|2|10|
|d|6|3|18|
|e|9|3|27|

累加所有节点的路径长度乘以权值，得到：

WPL = 4 + 6 + 10 + 18 + 27 = 65

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

10设一 组权值集 合W=(3,2,6,9,5),要求根据这些权值集合构造一棵哈夫 曼树，则这棵哈夫曼树的带权路径长度为多少

首先，我们需要将权值集合按照从小到大的顺序进行排序，得到 W=(2,3,5,6,9)。

接着，我们需要构造哈夫曼树。具体的构造方法是：

1. 从 W 中取出权值最小的两个元素，将它们作为左右子树构造一个新的二叉树，并将它们的权值之和作为该二叉树的根节点的权值。
2. 将新构造的二叉树的根节点的权值插入到 W 中，并将原来的两个权值最小的元素从 W 中删除。
3. 重复步骤 1 和步骤 2，直到 W 中只剩下一个元素为止，这个元素就是哈夫曼树的根节点。

我们按照上述方法构造哈夫曼树，可以得到如下的结果：

         30
       /    \
      11     19
     /  \   /  \
    5   6  9    10

其中，数字表示每个节点的权值。

最后，我们需要计算哈夫曼树的带权路径长度（WPL）。计算方法是：将每个叶子节点的深度乘以它的权值，然后将所有叶子节点的结果相加。

根据上面的哈夫曼树，可以得到每个叶子节点的深度和权值如下：

      2*5=10
      2*6=12
      2*9=18
      3*3=9
      3*2=6

将它们相加，得到 WPL=10+12+18+9+6=55。

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