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

客官°小女子只卖身不卖艺 2023-10-01 09:11 1阅读 0赞

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]