Huffman Tree哈夫曼树（霍夫曼树、赫夫曼树）权值路径长度WPL计算，binarytree ，Python
计算定义：把构建成功的哈夫曼树的每一个边缘节点（叶子）值乘以该节点到根的路径长度，最后求合。
import random
from binarytree import Node, get_parent
def app():
data = []
# 生成随机测试数据。
for i in range(5):
d = random.randint(1, 50)
data.append(d)
random.shuffle(data)
print(data)
huffman_tree = build_huffman_tree(data)
print('-----')
print('最终的Huffman树')
root = huffman_tree.pop()
print(root)
print('---')
print(data)
print('计算WPL')
wpl(root)
def build_huffman_tree(data):
nodes = []
for i in data:
nodes.append(Node(i))
print('nodes', nodes)
print('开始构建Huffman树')
while True:
nodes = sorted(nodes, key=lambda x: x.value)
# print('nodes', nodes)
if len(nodes) == 1:
# print('仅剩一个节点，建树结束')
break
left = nodes.pop(0)
right = nodes.pop(0)
# print('选取节点', left.value, right.value)
root = Node(left.value + right.value)
root.left = left
root.right = right
nodes.append(root)
return nodes
# 计算带权值路径长度WPL
def wpl(root):
leaves = root.leaves
sum = 0
for l in leaves:
path = count_path(root, l)
print(l.value, '->', root.value, '长度 = ', path)
sum = sum + path * l.value
print('带权值路径长度WPL =', sum)
def count_path(root, node):
root_value = root.value
count = 0
while True:
p = get_parent(root, node)
count = count + 1
if p.value == root_value:
break
else:
node = p
return count
if __name__ == '__main__':
app()
输出：
[18, 35, 40, 3, 9]
nodes [Node(18), Node(35), Node(40), Node(3), Node(9)]
开始构建Huffman树
-----
最终的Huffman树
_105_____________
/ \
40 ____65
/ \
___30 35
/ \
12 18
/ \
3 9
---
[18, 35, 40, 3, 9]
计算WPL
40 -> 105 长度 = 1
35 -> 105 长度 = 2
18 -> 105 长度 = 3
3 -> 105 长度 = 4
9 -> 105 长度 = 4
带权值路径长度WPL = 212
