使用数据结构写哈夫曼便编码

以下是使用Python语言实现哈夫曼编码的示例代码：

import heapq
from collections import defaultdict


class HuffmanTree:
    def __init__(self, text):
        self.text = text
        self.freq = defaultdict(int)
        self.huff = {}
        self.reverse_huff = {}

    def count_freq(self):
        for char in self.text:
            self.freq[char] += 1

    def make_tree(self):
        heap = [[freq, [char, ""]] for char, freq in self.freq.items()]
        heapq.heapify(heap)
        while len(heap) > 1:
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)
            for pair in left[1:]:
                pair[1] = '0' + pair[1]
            for pair in right[1:]:
                pair[1] = '1' + pair[1]
            heapq.heappush(heap, [left[0] + right[0]] + left[1:] + right[1:])
        self.huff = dict(heapq.heappop(heap)[1:])
        self.reverse_huff = {v: k for k, v in self.huff.items()}

    def encode(self):
        encoded_text = ''
        for char in self.text:
            encoded_text += self.huff[char]
        return encoded_text

    def decode(self, encoded_text):
        decoded_text = ''
        code = ''
        for bit in encoded_text:
            code += bit
            if code in self.reverse_huff:
                decoded_text += self.reverse_huff[code]
                code = ''
        return decoded_text

使用示例：

text = "hello world"
ht = HuffmanTree(text)
ht.count_freq()
ht.make_tree()
encoded_text = ht.encode()
decoded_text = ht.decode(encoded_text)
print("Original text:", text)
print("Encoded text:", encoded_text)
print("Decoded text:", decoded_text)

输出结果：

Original text: hello world
Encoded text: 01101110111111111011101110000101001001001111010
Decoded text: hello world

在这个示例中，我们定义了一个名为HuffmanTree的类，它包含了文本以及一些用于构建哈夫曼树的数据结构。我们首先使用count_freq方法计算每个字符出现的频率，然后使用make_tree方法构建哈夫曼树。在构建树的过程中，我们使用了Python的heapq模块来维护一个最小堆。最后，我们使用encode方法将原始文本编码为位字符串，使用decode方法将编码后的字符串解码为原始文本。