数据结构——哈夫曼树

1.哈夫曼树的基本概念

哈夫曼树（Huffman Tree）是一种用于数据压缩的二叉树结构，最著名的应用是在哈夫曼编码中。哈夫曼编码是一种无损压缩算法，通过这种算法可以有效地压缩数据。哈夫曼树的基本思想是根据字符出现的频率来构建树，使得频率较高的字符在编码时使用较短的编码，频率较低的字符使用较长的编码，从而达到压缩的目的。

2.如何构造哈夫曼树

2.1基本原理

• 从所有节点中选择两个权值最小的节点，将它们合并成一个新的节点，新节点的权值是这两个节点权值的和。
• 将新节点加入到节点集合中，然后从集合中移除刚才合并的两个节点。
• 重复上述步骤，直到集合中只剩下一个节点，这个节点就是哈夫曼树的根节点。1
  其中的关键就是：那几个数随着最小两个相加而改变，再取最小的两个，当有两个比顶上那个小的时候，就要另外开一棵树了。

2.2举例子

将5，29，7，8，14，23，3，11构造为一颗哈夫曼树
将其中最小的两个取出，分别是3，5，和为8，序列中剩下，8，29，7，8，14，23，11
因为序列中没有比8更小的，所以另开一颗树，选出7，8，和为15，因为7，8比3，5大，所以新树在右边序列中还剩下8，11，14，15，23，29
接下来看左边，将8和11匹配，和为19，序列中剩下14，15，19，23，29
再来看右边，序列中最小的是14.取出和15匹配，和为29，序列中剩下19，23，29，29
再看左边，选出19，23，和为42，序列中剩下29，29，42
右边，取出29和29，和为58，序列中剩下，42，58，和为100。

import heapq

# 定义哈夫曼树节点类
class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char  # 节点代表的字符
        self.freq = freq  # 字符的频率
        self.left = None  # 左子节点
        self.right = None  # 右子节点

    # 定义比较操作，用于heapq模块，确保优先队列中最小的节点排在前面
    def __lt__(self, other):
        return self.freq < other.freq

# 递归函数，用于计算节点的带权路径长度
def calculate_wpl(node, depth=0):
    if node is None:
        return 0
    if node.left is None and node.right is None:  # 如果是叶子节点
        return node.freq * depth  # 返回该节点的频率乘以其深度
    return calculate_wpl(node.left, depth + 1) + calculate_wpl(node.right, depth + 1)  # 递归计算左右子树的WPL

# 构建哈夫曼树的函数
def build_huffman_tree(frequencies):
    priority_queue = [HuffmanNode(char, freq) for char, freq in frequencies.items()]  # 初始化优先队列
    heapq.heapify(priority_queue)  # 将列表转换为堆
    
    while len(priority_queue) > 1:  # 当堆中有多于一个节点时
        left = heapq.heappop(priority_queue)  # 弹出两个权值最小的节点
        right = heapq.heappop(priority_queue)
        
        merged = HuffmanNode(None, left.freq + right.freq)  # 创建一个新节点，其频率为两个节点之和
        merged.left = left  # 设置左子节点
        merged.right = right  # 设置右子节点
        
        heapq.heappush(priority_queue, merged)  # 将新节点放回堆中
    
    return priority_queue[0]  # 返回堆中最后一个节点，即哈夫曼树的根节点

# 递归函数，用于打印哈夫曼编码
def print_huffman_codes(node, prefix="", code_book={}):
    if node is not None:
        if node.char is not None:  # 如果是叶子节点，记录编码
            code_book[node.char] = prefix
        print_huffman_codes(node.left, prefix + "0", code_book)  # 递归左子树，编码添加'0'
        print_huffman_codes(node.right, prefix + "1", code_book)  # 递归右子树，编码添加'1'
    return code_book  # 返回包含所有字符及其编码的字典

# 示例使用
frequencies = {'A': 5, 'B': 29, 'C': 7, 'D': 8, 'E': 14, 'F': 23, 'G': 3, 'H': 11}
root = build_huffman_tree(frequencies)  # 构建哈夫曼树
huffman_codes = print_huffman_codes(root)  # 打印哈夫曼编码

# 计算WPL
wpl = calculate_wpl(root)
print("Huffman Codes:", huffman_codes)
print("WPL:", wpl)