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

定义节点类

class Node(object): def init(self, weight): self.weight = weight self.parent = None self.left_child = None self.right_child = None

创建节点列表

nodes = [Node(weight) for symbol, weight in char_weights]

构造哈夫曼树

while len(nodes) > 1: # 按照节点的权值大小排序 nodes = sorted(nodes, key=lambda node: node.weight)

# 取出最小的两个节点
left_child = nodes.pop(0)
right_child = nodes.pop(0)

# 创建新的父节点，权值为两个子节点的权值之和
parent = Node(left_child.weight + right_child.weight)

# 将新的父节点作为两个子节点的父节点
left_child.parent = parent
right_child.parent = parent

parent.left_child = left_child
parent.right_child = right_child

# 将新的父节点加入节点列表中
nodes.append(parent)

从叶节点向上遍历，生成哈夫曼编码

for node in sorted(nodes, key=lambda node: node.weight): symbol = [symbol for symbol, weight in char_weights if weight == node.weight][0] code = '' parent = node.parent

while parent:
    if parent.left_child == node:
        code = '0' + code
    else:
        code = '1' + code

    node = parent
    parent = parent.parent

print('{symbol}: {code}'.format(symbol=symbol, code=code)