数据结构实验四 哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。在哈夫曼树中，每个叶子节点都有一个权值，而非叶子节点没有权值。哈夫曼树的构造过程是通过贪心算法实现的，即每次选择权值最小的两个节点合并成一个新节点，直到最后只剩下一个节点为止。哈夫曼树的应用非常广泛，其中最常见的应用是数据压缩。

以下是构造哈夫曼树和哈夫曼编码的步骤：
1. 统计每个字符出现的频率，并将它们作为叶子节点的权值。
2. 将所有的叶子节点按照权值从小到大排序。
3. 选择权值最小的两个节点合并成一个新节点，新节点的权值为这两个节点的权值之和。
4. 将新节点插入到原来的节点序列中，并重新按照权值从小到大排序。
5. 重复步骤3和步骤4，直到只剩下一个节点为止，这个节点就是哈夫曼树的根节点。
6. 对于每个叶子节点，从它到根节点的路径上标记0或1，得到每个字符的哈夫曼编码。

以下是Python实现哈夫曼树和哈夫曼编码的代码：

import heapq
from collections import defaultdict

def huffman_encoding(data):
    # 统计每个字符出现的频率
    freq = defaultdict(int)
    for c in data:
        freq[c] += 1

    # 将每个字符作为一个叶子节点，并将它们加入到优先队列中
    heap = [[weight, [char, ""]] for char, weight in 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:])

    # 得到每个字符的哈夫曼编码
    huffman_code = dict(heapq.heappop(heap)[1:])
    return huffman_code

def huffman_decoding(data, huffman_code):
    # 将哈夫曼编码转换为反向字典
    reverse_code = {v: k for k, v in huffman_code.items()}

    # 解码数据
    current_code = ""
    decoded_data = ""
    for bit in data:
        current_code += bit
        if current_code in reverse_code:
            decoded_data += reverse_code[current_code]
            current_code = ""
    return decoded_data