实现哈夫曼树和哈夫曼编码

哈夫曼树（Huffman Tree）是一种带权路径长度最短的树，也称为最优二叉树。哈夫曼编码（Huffman Coding）是一种可变字长编码方法，通过将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，从而达到压缩数据的目的。

实现哈夫曼树和哈夫曼编码的步骤如下：

1. 统计每个字符出现的频率，并将它们作为权值构建森林（每个字符看成一棵只有一个节点的树）。

2. 从森林中选取两棵根节点权值最小的树合并成一棵新树，新树的根节点权值为两棵树的根节点权值之和。

3. 将新树插入森林中，并删除原来的两棵树。

4. 重复步骤2和3，直到森林中只剩下一棵树，即为哈夫曼树。

5. 对于哈夫曼树中的每个叶子节点，从根节点开始记录路径上的0和1，0表示向左，1表示向右，得到该节点的哈夫曼编码。

下面是 Python 代码实现：

class HuffmanTreeNode:
    def __init__(self, val, weight):
        self.val = val
        self.weight = weight
        self.left = None
        self.right = None

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

class HuffmanTree:
    def __init__(self, text):
        self.text = text
        self.freq = self.count_freq()
        self.root = self.build_tree()
        self.codes = self.build_codes()

    def count_freq(self):
        freq = {}
        for char in self.text:
            freq[char] = freq.get(char, 0) + 1
        return freq

    def build_tree(self):
        heap = []
        for char, freq in self.freq.items():
            node = HuffmanTreeNode(char, freq)
            heapq.heappush(heap, node)

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

        return heap[0]

    def build_codes(self):
        codes = {}
        def dfs(node, path):
            if node:
                if not node.left and not node.right:
                    codes[node.val] = path
                dfs(node.left, path + "0")
                dfs(node.right, path + "1")
        dfs(self.root, "")
        return codes

    def encode(self):
        return "".join(self.codes[char] for char in self.text)

    def decode(self, code):
        result = []
        node = self.root
        for bit in code:
            if bit == "0":
                node = node.left
            else:
                node = node.right

            if not node.left and not node.right:
                result.append(node.val)
                node = self.root

        return "".join(result)

text = "hello world"
tree = HuffmanTree(text)
encoded = tree.encode()
decoded = tree.decode(encoded)
print(encoded)  # 100111110000110000100100010011101101110
print(decoded)  # hello world

在上述代码中，我们使用了 heapq 模块来实现小根堆。首先，我们统计了每个字符出现的频率，并将它们作为权值构建森林。然后，我们使用小根堆来合并森林中权值最小的两棵树，得到一棵新树。重复这个过程，直到森林中只剩下一棵树，即为哈夫曼树。最后，我们遍历哈夫曼树，记录每个叶子节点的哈夫曼编码，并使用编码来压缩数据。对于解码，我们从根节点开始遍历哈夫曼树，根据每个编码的0和1决定向左还是向右，直到到达叶子节点，得到对应的字符。