实现霍夫曼编码

class HuffmanNode:
def init(self, char, weight, left, right):
self.weight = weight
self.char = char
self.left = left
self.right = right

class Huffman:
def init(self):
self.root = None
def add_node(self, node):
if self.root is None:
self.root = node
else:
self.root = HuffmanNode(‘’, node.weight + self.root.weight, self.root, node)

def codes(self):  
    def dfs(node, cur):  
        if node is None:  
            return  

print(node.char, node.weight, cur)
dfs(node.left, cur+’0’)
dfs(node.right, cur+’1’)
return dfs(self.root, ‘’)

if name == “main“:
chars = [
(‘f’, 20),
(‘e’, 30),
(‘d’, 60),
(‘c’, 90),
(‘b’, 350),
(‘a’, 450),
]

huffman = Huffman()  
for c in chars:  
    huffman.add_node(HuffmanNode(c[0], c[1], None, None))  

huffman.codes(