huffman如何构造

有一份电文中使用的字符以及出现的频率如data字典中的内容所示：data={'a':6,'b':2,'c':9,'d':12,'e':8,'f':3,'g':7},编写程序，用Python构造Huffman树（左子根权值<=右子根权值）。要求输出：（1）所构造huffman树的前序、中序遍历序列（2）并求出每个字符的Huffman编码。

详细的代码实现和讲解如下，望采纳

from heapq import heappop, heappush, heapify

def huffman_encoding(data):
    # 将数据转换为二元组列表 [(权值, 字符)]
    heap = [(v, k) for k, v in data.items()]
    # 将列表转换为堆
    heapify(heap)

    while len(heap) > 1:
        # 弹出堆顶元素
        left = heappop(heap)
        right = heappop(heap)
        # 将两个元素合并为一个新的二元组
        # 其中新的二元组的权值是两个元素的权值之和
        # 其中新的二元组的字符是两个元素的字符的元组
        new_node = (left[0] + right[0], (left, right))
        # 将新的二元组放入堆中
        heappush(heap, new_node)

    # 堆中最后剩余的元素就是根节点
    root = heap[0]

    # 前序遍历
    def preorder(node, prefix=''):
        if len(node[1]) == 1:
            print(f"{node[1]}: {prefix}")
            return
        preorder(node[1][0], prefix + '0')
        preorder(node[1][1], prefix + '1')

    # 中序遍历
    def inorder(node, prefix=''):
        if len(node[1]) == 1:
            print(f"{node[1]}: {prefix}")
            return
        inorder(node[1][0], prefix + '0')
        inorder(node[1][1], prefix + '1')

    print("前序遍历：")
    preorder(root)
    print("中序遍历：")
    inorder(root)

# 测试
data = {'a': 6, 'b': 2, 'c': 9, 'd': 12, 'e': 8, 'f': 3, 'g': 7}
huffman_encoding(data)

运行结果如下

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632