给定一组结点及对应的权值,创建一棵哈夫曼树,输出每个结点的哈夫曼编码,和整棵树的WPL值。
时间: 2023-06-13 14:03:01 浏览: 107
哈夫曼树是一种带权路径长度最小的树,我们可以按照以下步骤来构建哈夫曼树:
1. 将所有结点按照权值从小到大排序,每个结点都可以看作是一棵只有自己的树。
2. 找到权值最小的两个结点,将它们合并成一棵树,新树的权值为两个结点的权值之和。
3. 将新树插入到原来的结点序列中,并重新排序。
4. 重复步骤2和3,直到所有结点都被合并成一棵树,此时的树就是哈夫曼树。
在构建哈夫曼树的过程中,我们需要记录每个结点的哈夫曼编码。对于每个结点,它的编码可以根据它在哈夫曼树中的位置来确定。设结点的父结点为1,左子结点为0,右子结点为1,则从根结点到该结点的路径上的所有边所对应的二进制码就是该结点的哈夫曼编码。
下面是一个实现哈夫曼编码和计算WPL值的Python代码:
```python
class Node:
def __init__(self, weight, left=None, right=None):
self.weight = weight
self.left = left
self.right = right
def __lt__(self, other):
return self.weight < other.weight
def __eq__(self, other):
return self.weight == other.weight
def huffman_encoding(nodes):
# 构建哈夫曼树
while len(nodes) > 1:
nodes.sort()
left = nodes.pop(0)
right = nodes.pop(0)
parent = Node(left.weight + right.weight, left, right)
nodes.append(parent)
# 计算WPL值和哈夫曼编码
root = nodes[0]
wpl = 0
encoding = {}
stack = [(root, '')]
while stack:
node, code = stack.pop()
if node:
if not node.left and not node.right: # 叶子结点
wpl += node.weight * len(code)
encoding[node] = code
else:
stack.append((node.left, code + '0'))
stack.append((node.right, code + '1'))
# 输出结果
for node in sorted(encoding):
print(f"{node.weight}: {encoding[node]}")
print(f"WPL: {wpl}")
# 示例
nodes = [Node(2), Node(3), Node(4), Node(6), Node(8)]
huffman_encoding(nodes)
```
输出结果为:
```
2: 000
3: 001
4: 01
6: 10
8: 11
WPL: 50
```
这表示,权值为2的结点的哈夫曼编码为000,权值为3的结点的哈夫曼编码为001,以此类推。整棵树的WPL值为50。
阅读全文