Python实现Huffman编码：构建、打印和编码Huffman树

下面是用Python实现Huffman树的代码：

import heapq
from collections import defaultdict

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

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

def build_huffman_tree(freq_table):
    heap = []
    for symbol, freq in freq_table.items():
        heapq.heappush(heap, Node(freq, symbol))

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

    return heap[0]

def print_huffman_tree(node, code=''):
    if node.symbol:
        print(f'Symbol: {node.symbol}, Code: {code}')
    else:
        print_huffman_tree(node.left, code + '0')
        print_huffman_tree(node.right, code + '1')

def encode_string(root, string):
    code_table = {}

    def traverse(node, code):
        if node.symbol:
            code_table[node.symbol] = code
        else:
            traverse(node.left, code + '0')
            traverse(node.right, code + '1')

    traverse(root, '')
    encoded_string = ''.join(code_table[symbol] for symbol in string)
    return encoded_string, code_table

# Example usage:
freq_table = defaultdict(int)
string = 'hello world'
for char in string:
    freq_table[char] += 1

huffman_tree = build_huffman_tree(freq_table)
print_huffman_tree(huffman_tree)

encoded_string, code_table = encode_string(huffman_tree, string)
print('Encoded string:', encoded_string)
print('Code table:', code_table)

该代码首先定义了一个Node类来表示Huffman树的节点。然后，build_huffman_tree()函数根据频率表构建Huffman树。print_huffman_tree()函数用于打印Huffman树的结构，并对每个叶子节点打印编码。encode_string()函数用于将字符串编码为Huffman编码，并返回编码后的字符串和编码表。

在示例中，我们使用字符串'hello world'构建了一个频率表，并构造了Huffman树。然后，我们打印了Huffman树的结构，并对每个叶子节点打印了编码。最后，我们将字符串编码为Huffman编码，并打印编码后的字符串和编码表。