哈夫曼编码python代码

哈夫曼编码是一种用于数据压缩的自适应二进制前缀编码算法，它通过构建一棵最优的二叉树来进行编码。在Python中，我们可以使用字典和堆数据结构来实现哈夫曼编码。这里是一个简单的例子：

import heapq

# 定义一个节点类
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

# 创建一个空堆
heap = []

# 输入字符及其频率
data = {'A': 50, 'B': 10, 'C': 20, 'D': 40}

# 将字符和频率插入堆
for char, freq in data.items():
    node = Node(char, freq)
    heapq.heappush(heap, node)

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)

# 根节点就是哈夫曼树的根，获取其路径
huff_tree_root = heap[0]
huffman_codes = {}
def traverse(node, code=''):
    if node.char is not None:
        huffman_codes[node.char] = code
    else:
        traverse(node.left, code + '0')
        traverse(node.right, code + '1')

traverse(huff_tree_root)

在这个代码中，我们首先创建了一个空的堆，然后将每个字符及其频率作为节点放入堆中。接着，我们不断从堆中取出两个频率最高的节点合并它们，直到只剩下一个节点为止。最后，我们遍历这棵哈夫曼树，记录下每个字符对应的编码。