Huffman Tree，哈夫曼树（又被称为霍夫曼树、赫夫曼树），是一种基于贪心算法思想构建的二叉树，贪心算法寻求在建树过程中局部最优，最终迭代达到全局最优，从中可以看出，Huffman树的构建也体现了动态规划思想。Huffman Tree的贪心算法思想，寻找一种二叉树，使得WPL带路权的最小二叉树，因此，哈夫曼树也称为最优二叉树。
现在基于binarytree，用Python构建哈夫曼树：
import random
from binarytree import Node
def app():
data = []
# 生成随机测试数据。
for i in range(5):
data.append(random.randint(1, 50))
random.shuffle(data)
print(data)
huffman_tree = build_huffman_tree(data)
print('-----')
print('最终的Huffman树')
print(huffman_tree.pop())
print('---')
print(data)
def build_huffman_tree(data):
nodes = []
for i in data:
nodes.append(Node(i))
print('nodes', nodes)
print('开始构建Huffman树')
while True:
print('-')
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
if __name__ == '__main__':
app()
测试几轮算法日志输出：
[22, 26, 29, 10, 24]
nodes [Node(22), Node(26), Node(29), Node(10), Node(24)]
开始构建Huffman树
-
nodes [Node(10), Node(22), Node(24), Node(26), Node(29)]
选取节点 10 22
-
nodes [Node(24), Node(26), Node(29), Node(32)]
选取节点 24 26
-
nodes [Node(29), Node(32), Node(50)]
选取节点 29 32
-
nodes [Node(50), Node(61)]
选取节点 50 61
-
nodes [Node(111)]
仅剩一个节点，建树结束
-----
最终的Huffman树
____111___
/ \
_50 _61___
/ \ / \
24 26 29 _32
/ \
10 22
---
[22, 26, 29, 10, 24]
[21, 38, 18, 27, 5]
nodes [Node(21), Node(38), Node(18), Node(27), Node(5)]
开始构建Huffman树
-
nodes [Node(5), Node(18), Node(21), Node(27), Node(38)]
选取节点 5 18
-
nodes [Node(21), Node(23), Node(27), Node(38)]
选取节点 21 23
-
nodes [Node(27), Node(38), Node(44)]
选取节点 27 38
-
nodes [Node(44), Node(65)]
选取节点 44 65
-
nodes [Node(109)]
仅剩一个节点，建树结束
-----
最终的Huffman树
_________109___
/ \
_44__ _65
/ \ / \
21 23 27 38
/ \
5 18
---
[21, 38, 18, 27, 5]
[15, 2, 13, 31, 44]
nodes [Node(15), Node(2), Node(13), Node(31), Node(44)]
开始构建Huffman树
-
nodes [Node(2), Node(13), Node(15), Node(31), Node(44)]
选取节点 2 13
-
nodes [Node(15), Node(15), Node(31), Node(44)]
选取节点 15 15
-
nodes [Node(30), Node(31), Node(44)]
选取节点 30 31
-
nodes [Node(44), Node(61)]
选取节点 44 61
-
nodes [Node(105)]
仅剩一个节点，建树结束
-----
最终的Huffman树
_105______________
/ \
44 _________61
/ \
_30__ 31
/ \
15 15
/ \
2 13
---
[15, 2, 13, 31, 44]
