Huffman编码 数据结构实验 代码

Huffman编码是一种用于数据压缩的无损数据编码算法，它通过对字符出现频率高的编码长度更短，频率低的编码长度较长的方式来实现压缩。在数据结构实验中，学生可能会用到二叉树（尤其是堆或优先队列）的概念，构建Huffman树。

一个简单的Huffman编码实现代码（Python示例）可能包含以下步骤：

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

def build_huffman_tree(freq_list):
    # 创建节点列表并将频率作为权重放入堆
    nodes = [Node(c, f) for c, f in freq_list]
    heapq.heapify(nodes)

    while len(nodes) > 1:
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        combined = Node(None, left.freq + right.freq)
        combined.left, combined.right = left, right
        heapq.heappush(nodes, combined)

    return nodes[0]  # 返回根节点，即Huffman树的树顶

def huffman_code(root):
    code_dict = {}
    traverse(root, "", code_dict)
    return code_dict

def traverse(node, current_code, code_dict):
    if node is not None:
        if node.char is not None:
            code_dict[node.char] = current_code
        traverse(node.left, current_code + "0", code_dict)
        traverse(node.right, current_code + "1", code_dict)

# 示例用法
freq_list = [('A', 8), ('B', 1), ('C', 2), ('D', 4)]
huff_tree_root = build_huffman_tree(freq_list)
encoded_chars = huffman_code(huff_tree_root)

在这个代码中，`build_huffman_tree`函数构建了Huffman树，`huffman_code`生成每个字符对应的Huffman编码，`traverse`则是一个递归辅助函数。