哈夫曼树的构造python
时间: 2023-10-13 08:26:52 浏览: 29
下面是一个使用Python实现哈夫曼树的示例:
```python
class Node(object):
def __init__(self, left=None, right=None):
self.left = left
self.right = right
def children(self):
return (self.left, self.right)
def huffman_code_tree(node, left=True, binString=''):
if type(node) is str:
return {node: binString}
(l, r) = node.children()
code = {}
code.update(huffman_code_tree(l, True, binString + '0'))
code.update(huffman_code_tree(r, False, binString + '1'))
return code
def main():
str = "this is an example for huffman encoding"
freq = {}
for c in str:
if c in freq:
freq[c] += 1
else:
freq[c] = 1
freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)
nodes = freq
while len(nodes) > 1:
(key1, c1) = nodes[-1]
(key2, c2) = nodes[-2]
nodes = nodes[:-2]
node = Node(key1, key2)
nodes.append((node, c1 + c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
huffmanCode = huffman_code_tree(nodes[0][0])
print(" Char | Huffman code ")
print("-----|------------")
for (char, frequency) in freq:
print(" %-4r |%12s" % (char, huffmanCode[char]))
if __name__ == '__main__':
main()
```
在这个示例中,我们首先对输入字符串中的字符进行计数,然后按照出现频率对它们进行排序。接下来,我们使用这些字符和它们的频率来构建哈夫曼树。最后,我们使用构建的哈夫曼树来生成每个字符的哈夫曼编码,并将其打印出来。