Huffman 编码实现：Python 代码及注释

三、实验代码与注释

# 定义 HuffmanNode 类，用于构建 Huffman 树
class HuffmanNode:
    def __init__(self, weight, value=None):
        self.weight = weight  # 节点权重，即信源符号的概率
        self.value = value  # 节点存储的值，即信源符号本身
        self.left = None  # 左子节点
        self.right = None  # 右子节点
        self.code = ''  # 存储该节点对应的编码

# 定义 HuffmanTree 类，用于构建 Huffman 树并生成编码
class HuffmanTree:
    def __init__(self, weights):
        self.weights = weights  # 存储信源符号及其概率
        self.root = None  # Huffman 树的根节点
        self.codes = {}  # 存储每个信源符号的编码

    # 构建 Huffman 树
    def build_tree(self):
        nodes = [HuffmanNode(weight[1], weight[0]) for weight in self.weights]  # 初始化节点列表
        while len(nodes) > 1:  # 当节点数目大于1时，继续构建 Huffman 树
            nodes.sort(key=lambda x: x.weight)  # 按权重从小到大排序
            left = nodes.pop(0)  # 取出权重最小的节点作为左子节点
            right = nodes.pop(0)  # 取出权重次小的节点作为右子节点
            new_node = HuffmanNode(left.weight + right.weight)  # 新节点的权重为左右子节点的权重之和
            new_node.left = left  # 将左子节点作为新节点的左子节点
            new_node.right = right  # 将右子节点作为新节点的右子节点
            nodes.append(new_node)  # 将新节点加入节点列表中
        self.root = nodes[0]  # 最后剩下的节点即为根节点

    # 生成编码
    def generate_code(self, node, code):
        if not node:  # 如果节点为空，则返回
            return
        if node.value:  # 如果节点存储了信源符号，则将该符号的编码存储到字典中
            self.codes[node.value] = code
            node.code = code
        self.generate_code(node.left, code + '0')  # 递归调用，生成左子节点的编码
        self.generate_code(node.right, code + '1')  # 递归调用，生成右子节点的编码

    # 打印生成的编码
    def print_code(self):
        print('Symbol	Weight	Code')
        for weight in self.weights:
            symbol = weight[0]
            w = weight[1]
            code = self.codes[symbol]
            print(f'{symbol}	{w}	{code}')

# 测试代码
if __name__ == '__main__':
    char_weights = [('a1', 4), ('a2', 2), ('a3', 2), ('a4', 1), ('a5', 1)]
    tree = HuffmanTree(char_weights)
    tree.build_tree()
    tree.generate_code(tree.root, '')
    tree.print_code()

注：以上代码中，用到了递归调用的方法来生成编码。递归调用的过程类似于深度优先搜索，先从根节点开始，沿着左子节点一直走到叶子节点，然后返回上一级节点，走右子节点，继续沿左子节点走到叶子节点，如此往复，直到遍历完整棵树。在递归调用的过程中，需要传递一个参数 code，用来记录当前节点所对应的编码。对于每个叶子节点，将其对应的信源符号及其编码存储到字典中，并将编码赋值给节点的 code 属性。最终，通过遍历字典，将信源符号、概率和编码输出到屏幕上。