哈夫曼树 python

哈夫曼树，也称为最优二叉树或最优前缀编码树，是一种特殊的二叉树结构，常用于数据压缩算法如Huffman编码。它的特点是每个节点的权值为其左孩子的权重加其右孩子的权重，构建过程通常是贪心的，从所有待编码的数据统计频率，然后逐步合并频率最低的两个节点，直到只剩下一个节点。

在Python中，你可以通过以下步骤创建并操作哈夫曼树：

1. **创建哈夫曼树**:
- 首先，需要一个字典存储字符及其频率。
- 使用`heapq`模块中的`heapify`和`heappushpop`等函数实现优先队列，模拟构建过程。

import heapq

def create_huffman_tree(freqs):
    heap = [[weight, [char, '']] for char, weight in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = [left[0] + right[0], left[1][0] + "|" + right[1][0]]
        heapq.heappush(heap, merged)
    return heap[0][1]

# 示例用法
freqs = {'A': 5, 'B': 9, 'C': 4}
huffman_tree = create_huffman_tree(freqs)

2. **编码**:
- 根据构建出的哈夫曼树，对于每个字符，沿着树向下遍历，遇到非叶子节点就向右分支，最后得到的编码作为结果。

3. **解码**:
- 可以用类似的方法，但反过来遍历树，遇到'|'则分割路径继续，直到达到叶子节点。