设一组权值集合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。

相关问题

设给定一个权值集合 W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的 带权路径长度 WPL。

哈夫曼树的构造过程如下：

1. 将所有权值按照从小到大的顺序排列，得到：(3，5，7，9，11)。
2. 取出权值最小的两个节点3和5，将它们合并成一个新节点，权值为8。此时得到的节点集合为(7，8，9，11)。
3. 取出权值最小的两个节点7和8，将它们合并成一个新节点，权值为15。此时得到的节点集合为(9，11，15)。
4. 取出权值最小的两个节点9和11，将它们合并成一个新节点，权值为20。此时得到的节点集合为(15，20)。
5. 最后将权值为15和20的节点合并成一个根节点，得到哈夫曼树。

哈夫曼树如下图所示：

      35
     /  \
    15  20
   /  \     
  7    8
 / \
3   5

根据哈夫曼树的定义，每个叶子节点都对应一个权值，而每个非叶子节点都对应一个权值之和。因此，我们可以通过遍历哈夫曼树来计算带权路径长度WPL。

在上面的哈夫曼树中，有5个叶子节点，分别对应权值3，5，7，9，11。它们的深度分别为2，2，1，1，1。因此，带权路径长度WPL为：

WPL = 2*3 + 2*5 + 1*7 + 1*9 + 1*11 = 6 + 10 + 7 + 9 + 11 = 43

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

设一组权值集合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。