定义二元树节点类

class Node: def init(self, symbol=None, weight=0): self.symbol = symbol # 节点表示的符号 self.weight = weight # 节点表示的符号的权重 self.left = None # 左子节点 self.right = None # 右子节点 self.code = '' # 节点对应的编码

定义Huffman编码类

class HuffmanCoding: def init(self, char_weights): self.char_weights = char_weights # 符号及其对应的权重 self.char_list = [] # 符号列表 self.code_dict = {} # 编码字典 self.root = None # Huffman树根节点

# 构建Huffman树
def build_tree(self):
    nodes = []
    for char_weight in self.char_weights:
        node = Node(symbol=char_weight[0], weight=char_weight[1])
        nodes.append(node)
        self.char_list.append(char_weight[0])
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.weight)
        left_node = nodes.pop(0)
        right_node = nodes.pop(0)
        new_node = Node(weight=left_node.weight + right_node.weight)
        new_node.left = left_node
        new_node.right = right_node
        nodes.append(new_node)
    self.root = nodes[0]

# 遍历Huffman树，生成编码字典
def traverse_tree(self, node, code):
    if node is None:
        return
    node.code = code
    if node.symbol is not None:
        self.code_dict[node.symbol] = node.code
    self.traverse_tree(node.left, code+'0')
    self.traverse_tree(node.right, code+'1')

# 获取每个符号的Huffman编码
def get_code(self):
    self.build_tree()
    self.traverse_tree(self.root, '')

# 输出每个符号的Huffman编码
def print_code(self):
    for char in self.char_list:
        print(char, self.code_dict[char])

定义符号及其对应的权重

char_weights = [('a1', 4), ('a2', 2), ('a3', 2), ('a4', 1), ('a5', 1)]

创建Huffman编码对象

huffman_coding = HuffmanCoding(char_weights)

获取每个符号的Huffman编码

huffman_coding.get_code()

输出每个符号的Huffman编码

huffman_coding.print_code(