生成哈夫曼树python

哈夫曼树，也称为最优二叉树，是一种特殊的带权路径长度最短的二叉树，常用于数据压缩算法如Huffman编码。在Python中，你可以使用内置的数据结构和一些基本的算法来构建哈夫曼树。以下是创建一个简单哈夫曼树的基本步骤：

from collections import defaultdict
import heapq

# 定义节点类
class Node:
    def __init__(self, weight):
        self.weight = weight
        self.left = None
        self.right = None

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

# 构建优先队列
def build_huffman_tree(freqs):
    heap = [Node(weight) for weight in freqs]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(left.weight + right.weight, left, right)
        heapq.heappush(heap, merged)

    return heap[0]

# 示例：频率字典，比如 {'A': 5, 'B': 10, 'C': 15}
freqs = {'A': 5, 'B': 10, 'C': 15}

huffman_tree = build_huffman_tree(freqs)

# 接下来你可以打印出哈夫曼树的结构，或者按照哈夫曼树的规则生成编码

在这个例子中，`freqs`是一个字典，表示字符及其出现的频率。`build_huffman_tree`函数会返回一个新的根节点，它就是构造出的哈夫曼树。每个节点的左孩子代表频率较小的那个分支，右孩子代表较大的那个分支。