创建huffman树的python实现

下面是一个简单的Huffman树的Python实现：

import heapq

class HuffmanNode:
    def __init__(self, value, frequency):
        self.value = value
        self.frequency = frequency
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.frequency < other.frequency

def build_huffman_tree(data):
    # 统计字符频率
    frequency_map = {}
    for char in data:
        if char in frequency_map:
            frequency_map[char] += 1
        else:
            frequency_map[char] = 1
    
    # 构建Huffman树
    heap = []
    for char, freq in frequency_map.items():
        node = HuffmanNode(char, freq)
        heapq.heappush(heap, node)
    
    while len(heap) > 1:
        left_child = heapq.heappop(heap)
        right_child = heapq.heappop(heap)
        
        parent = HuffmanNode(None, left_child.frequency + right_child.frequency)
        parent.left = left_child
        parent.right = right_child
        
        heapq.heappush(heap, parent)
    
    return heap[0]

def build_huffman_code(node, code, huffman_map):
    if node is None:
        return
    
    if node.value is not None:
        huffman_map[node.value] = code
        return
    
    build_huffman_code(node.left, code + '0', huffman_map)
    build_huffman_code(node.right, code + '1', huffman_map)

def encode(data, huffman_map):
    encoded_data = ''
    for char in data:
        encoded_data += huffman_map[char]
    
    return encoded_data

def decode(encoded_data, huffman_tree):
    decoded_data = ''
    current_node = huffman_tree
    
    for bit in encoded_data:
        if bit == '0':
            current_node = current_node.left
        else:
            current_node = current_node.right
        
        if current_node.value is not None:
            decoded_data += current_node.value
            current_node = huffman_tree
    
    return decoded_data

# 测试例子
data = 'aabbbccddd'
huffman_tree = build_huffman_tree(data)
huffman_map = {}
build_huffman_code(huffman_tree, '', huffman_map)
encoded_data = encode(data, huffman_map)
decoded_data = decode(encoded_data, huffman_tree)

print('Encoded data:', encoded_data)
print('Decoded data:', decoded_data)

这个实现首先统计输入数据中每个字符的频率，然后根据频率构建Huffman树。然后，根据Huffman树构建编码表，用于编码输入数据。最后，使用Huffman树对编码数据进行解码，得到原始数据