7-1【必做】 构造哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，可以用来实现哈夫曼编码，常用于数据压缩等领域。构造哈夫曼树的方法是将所有权值看作节点，每次选择权值最小的两个节点构成一个新节点，新节点的权值为这两个节点的权值之和，直到所有节点都被合并为一个节点为止。

以下是构造哈夫曼树的具体步骤：

1. 将所有的权值看作节点，放入一个最小堆中。
2. 从最小堆中取出两个权值最小的节点，构造一个新节点，权值为这两个节点的权值之和。
3. 将新节点插入最小堆中。
4. 重复步骤2和3，直到堆中只有一个节点为止，这个节点就是哈夫曼树的根节点。

下面是使用 Python 实现构造哈夫曼树的示例代码：

import heapq

class Node:
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.weight < other.weight

def build_huffman_tree(weights):
    nodes = [Node(w) for w in weights]
    heapq.heapify(nodes)
    while len(nodes) > 1:
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        parent = Node(left.weight + right.weight, left, right)
        heapq.heappush(nodes, parent)
    return nodes[0]

其中，Node 类表示哈夫曼树的节点，包含权值和左右子节点；build_huffman_tree 函数接受一个列表，返回构建好的哈夫曼树的根节点。在函数内部，首先将每个权值看作一个节点，并放入一个最小堆中。然后，每次从最小堆中取出两个节点，构建一个新节点，并将新节点插入最小堆中，直到最小堆只剩一个节点，这个节点就是哈夫曼树的根节点，返回即可。