Huffman Tree哈夫曼树权值路径长度WPL计算，binarytree ，Python

红太狼 2023-10-01 09:26 48阅读 0赞

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