python写一个哈夫曼树

在Python中，我们可以使用堆（heapq模块）和字典数据结构来实现哈夫曼树（Huffman Tree），这是一种用于数据压缩的二叉树。以下是简单的步骤：

首先，我们需要创建一个节点类（Node），包含字符、频率和左、右子节点：

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

    def __lt__(self, other):  # 比较节点频率用于堆排序
        return self.freq < other.freq

接着，我们编写一个函数来构建哈夫曼树：

import heapq

def build_huffman_tree(freqs):
    heap = [Node(char, freq) for char, freq in freqs.items()]
    heapq.heapify(heap)

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

    return heap[0]  # 返回根节点即哈夫曼树的最小带权路径长度树

# 示例使用
freqs = {'A': 5, 'B': 7, 'C': 3}
huff_tree = build_huffman_tree(freqs)

最后，你可以通过遍历哈夫曼树生成对应的编码规则，但这里仅实现了构建过程。