python实现霍夫曼树

霍夫曼树是一种经典的数据结构，用于实现霍夫曼编码，它通过构造一棵特殊的二叉树来实现。在霍夫曼树中，每个叶子节点代表一个字符，每个非叶子节点代表一个合并的节点，它的权值等于其左右子树的权值之和。同时，左子树的权值小于右子树的权值。这样，可以保证权值小的字符在编码中占用更少的位数。

在Python中，可以使用优先队列（也称为堆）来构建霍夫曼树。具体步骤如下：
1. 将每个字符及其出现频率作为一个节点插入到优先队列中。
2. 从队列中取出两个频率最小的节点，合并它们，并将新的节点插入到队列中。
3. 重复步骤2，直到队列中只剩下一个节点，即为霍夫曼树的根节点。

以下是Python实现霍夫曼树的代码示例：

import heapq

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

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

def build_huffman_tree(freq_map):
    heap = []
    for char, freq in freq_map.items():
        node = HuffmanNode(char, freq)
        heapq.heappush(heap, node)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, parent)

    return heap