哈夫曼树构造及带权路径长度计算

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

解答：

(1) 187

(2) 4

解题步骤：

排序: 将权值集合 W 按从小到大排序：1, 3, 6, 8, 14, 14, 16, 18。
构建哈夫曼树:
- 取出权值最小的两个结点 (1, 3) 作为左右孩子，构建一棵新树，根节点权值为 4 (1+3)。
- 将新的根节点 (权值4) 放回权值集合，并保持有序：4, 6, 8, 14, 14, 16, 18。
- 重复以上步骤，直到处理完所有权值，得到最终的哈夫曼树。
计算带权路径长度:
- 带权路径长度 (WPL) = 所有叶子节点的权值 * 其到根节点的路径长度之和。
- 根据构建的哈夫曼树，计算 WPL = 14 + 34 + 63 + 83 + 142 + 142 + 162 + 182 = 187。
计算权值最小叶子节点到根节点的路径长度:
- 观察构建的哈夫曼树，权值最小的叶子节点 (权值1) 到根节点的路径长度为 4。

代码实现 (Python):

import heapq

def huffman_tree(weights):
  heapq.heapify(weights)
  while len(weights) > 1:
    left = heapq.heappop(weights)
    right = heapq.heappop(weights)
    heapq.heappush(weights, left + right)
  return weights[0]

weights = [14, 3, 14, 1, 6, 8, 16, 18]
wpl = huffman_tree(weights)
print(f'哈夫曼树的带权路径长度为：{wpl}')

总结:

本题考察了哈夫曼树的构造以及带权路径长度的计算。哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩、编码等领域。