用代码实现哈夫曼问题

由于哈夫曼编码和解码都需要建立哈夫曼树，因此我先提供一个建立哈夫曼树的代码，再分别给出编码和解码的实现。

建立哈夫曼树：

class TreeNode:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None

def build_huffman_tree(freq_dict):
    """
    建立哈夫曼树
    :param freq_dict: 字符频率字典，key为字符，value为出现频率
    :return: 哈夫曼树的根节点
    """
    nodes = [TreeNode(char) for char in freq_dict.keys()]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.value)
        left_node = nodes.pop(0)
        right_node = nodes.pop(0)
        new_node = TreeNode(left_node.value + right_node.value)
        new_node.left = left_node
        new_node.right = right_node
        nodes.append(new_node)
    return nodes[0]

编码：

def huffman_encoding(text):
    """
    哈夫曼编码
    :param text: 待编码的文本
    :return: 编码后的二进制字符串和哈夫曼树的根节点
    """
    freq_dict = {}
    for char in text:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    if len(freq_dict) == 1:
        char = list(freq_dict.keys())[0]
        return '0' * freq_dict[char], None
    root = build_huffman_tree(freq_dict)
    code_dict = {}
    def dfs(node, code):
        if node:
            if not node.left and not node.right:
                code_dict[node.value] = code
            dfs(node.left, code + '0')
            dfs(node.right, code + '1')
    dfs(root, '')
    encoded_text = ''.join(code_dict[char] for char in text)
    return encoded_text, root

解码：

def huffman_decoding(encoded_text, root):
    """
    哈夫曼解码
    :param encoded_text: 编码后的二进制字符串
    :param root: 哈夫曼树的根节点
    :return: 解码后的文本
    """
    if not root:
        return ''
    node = root
    decoded_text = ''
    for bit in encoded_text:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if not node.left and not node.right:
            decoded_text += node.value
            node = root
    return decoded_text