哈夫曼树的定义与构造

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。在哈夫曼树中，每个叶子节点都有一个权值，而非叶子节点的权值为其左右子树权值之和。哈夫曼树的构造过程是将权值从小到大排序，然后每次取出权值最小的两个节点，将它们合并成一个新节点，新节点的权值为这两个节点的权值之和，然后将新节点插入到原来的序列中，重复这个过程直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

以下是Python实现哈夫曼树的代码示例：

import heapq
from collections import defaultdict

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

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

def huffman_encoding(data):
    freq_dict = defaultdict(int)
    for char in data:
        freq_dict[char] += 1

    heap = [Node(key, value) for key, value in freq_dict.items()]
    heapq.heapify(heap)

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

    root = heap[0]
    encoding_dict = {}
    _traverse_huffman_tree(root, "", encoding_dict)

    encoded_data = "".join([encoding_dict[char] for char in data])
    return encoded_data, root

def huffman_decoding(data, root):
    decoded_data = ""
    current_node = root
    for char in data:
        if char == "0":
            current_node = current_node.left
        else:
            current_node = current_node.right

        if current_node.left is None and current_node.right is None:
            decoded_data += current_node.value
            current_node = root

    return decoded_data

def _traverse_huffman_tree(node, code, encoding_dict):
    if node is None:
        return

    if node.value is not None:
        encoding_dict[node.value] = code

    _traverse_huffman_tree(node.left, code + "0", encoding_dict)
    _traverse_huffman_tree(node.right, code + "1", encoding_dict)