一个哈夫曼树程序

以下是一个Python实现的哈夫曼树程序：

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

def build_huffman_tree(freq_dict):
    nodes = [Node(freq, char) for char, freq in freq_dict.items()]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)
    return nodes[0]

def traverse_huffman_tree(root, code_dict, code=''):
    if root.char:
        code_dict[root.char] = code
    if root.left:
        traverse_huffman_tree(root.left, code_dict, code + '0')
    if root.right:
        traverse_huffman_tree(root.right, code_dict, code + '1')

def encode_string(string, code_dict):
    encoded = ''
    for char in string:
        encoded += code_dict[char]
    return encoded

def decode_string(encoded, root):
    decoded = ''
    node = root
    for bit in encoded:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if node.char:
            decoded += node.char
            node = root
    return decoded

if __name__ == '__main__':
    freq_dict = {'a': 5, 'b': 3, 'c': 2, 'd': 1, 'e': 1}
    root = build_huffman_tree(freq_dict)
    code_dict = {}
    traverse_huffman_tree(root, code_dict)
    encoded = encode_string('abcde', code_dict)
    decoded = decode_string(encoded, root)
    print('Encoded:', encoded)
    print('Decoded:', decoded)

该程序首先定义了一个Node类来表示哈夫曼树中的节点，包括频率、字符、左子节点和右子节点。build_huffman_tree函数根据字符频率字典构建哈夫曼树。traverse_huffman_tree函数遍历哈夫曼树并生成字符编码字典。encode_string函数根据字符编码字典将字符串编码。decode_string函数根据哈夫曼树和编码字符串将字符串解码。

最后，程序使用示例字符频率字典构建哈夫曼树，并输出编码和解码结果