构建Huffman哈夫曼最优二叉树，binarytree，Python-蒲公英云

构建Huffman哈夫曼最优二叉树，binarytree，Python

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]