哈夫曼树求带权路径代码
时间: 2024-04-28 17:17:05 浏览: 11
哈夫曼树是一种用于数据压缩的树形结构,它通过将出现频率较高的字符用较短的编码表示,从而实现数据的高效压缩。下面是求带权路径长度的哈夫曼树的代码实现:
```python
class Node:
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.left = None
self.right = None
def huffman_tree(weights):
nodes = [Node(weight, value) for weight, value in weights]
while len(nodes) > 1:
nodes.sort(key=lambda x: x.weight)
left = nodes.pop(0)
right = nodes.pop(0)
parent = Node(left.weight + right.weight, None)
parent.left = left
parent.right = right
nodes.append(parent)
return nodes
def get_codes(root, prefix="", codes={}):
if root:
if not root.left and not root.right:
codes[root.value] = prefix
get_codes(root.left, prefix + "0", codes)
get_codes(root.right, prefix + "1", codes)
return codes
# 示例用法
weights = [(5, 'A'), (9, 'B'), (12, 'C'), (13, 'D'), (16, 'E'), (45, 'F')]
root = huffman_tree(weights)
codes = get_codes(root)
for value, code in codes.items():
print(f"{value}: {code}")
```
上述代码中,我们首先定义了一个`Node`类来表示哈夫曼树的节点,每个节点包含权重和值,并且有左子节点和右子节点。然后,我们使用给定的权重列表构建哈夫曼树。在构建过程中,我们不断选择权重最小的两个节点,合并它们成为一个新的父节点,并将父节点放回节点列表中,直到只剩下一个根节点。
接下来,我们定义了一个`get_codes`函数来递归地获取每个字符的编码。在遍历过程中,我们使用前缀字符串来表示路径,左子节点对应编码为"0",右子节点对应编码为"1"。当遍历到叶子节点时,将叶子节点的值和对应的编码存入字典中。
最后,我们给出了一个示例用法,通过给定的权重列表构建哈夫曼树,并获取每个字符的编码。你可以根据自己的需求修改权重列表来进行测试。