天海一直在AI 2021-11-17 23:39 采纳率: 100%
浏览 95
已结题

求解用python遍历哈夫曼编码(中序遍历、后序遍历)

已知若干个字符的权重值为=[['a',15],['b',3],['c',14],['d',2],['e',6],['f',9],['g',16],['h',17]]

设计python程序,实现构造哈夫曼树,并采用中根序或后根序遍历方法,获取每个叶子节点的哈夫曼编码。

  • 写回答

1条回答 默认 最新

  • CSDN专家-黄老师 2021-11-18 10:29
    关注
    
    sourceData = [['a', 15], ['b', 3], ['c', 14], ['d', 2], ['e', 6], ['f', 9], ['g', 16], ['h', 17]]
    class BinaryTree:
        def __init__(self, data, weight):
            self.data = data
            self.weight = weight
            self.left = None
            self.right = None
    
    def min2(li):
        result = [BinaryTree(None, float('inf')), BinaryTree(None, float('inf'))]
        li2 = []
        for i in range(len(li)):
            if li[i].weight < result[0].weight:
                if result[1].weight != float('inf'):
                    li2.append(result[1])
                result[0], result[1] = li[i], result[0]
            elif li[i].weight < result[1].weight:
                if result[1].weight != float('inf'):
                    li2.append(result[1])
                result[1] = li[i]
            else:
                li2.append(li[i])
        return result, li2
    
    def makeHuffman(source):
        m2, data = min2(source)
        print(m2[0].data, m2[1].data)
        left = m2[0]
        right = m2[1]
    
        sumLR = left.weight + right.weight
        father = BinaryTree(None, sumLR)
        father.left = left
        father.right = right
        if data == []:
            return father
        data.append(father)
        return makeHuffman(data)
    
    # 中序
    def intermediateTraversal(now, result=[]):
        if now == None:
            return result
        intermediateTraversal(now.left, result)
        result.append(now.data)
        intermediateTraversal(now.right, result)
        return result
    
    # 后序
    def postorderTraversal(now, result=[]):
        if now == None:
            return
        postorderTraversal(now.left, result)
        postorderTraversal(now.right, result)
        result.append(now.data)
        return result
    
    # 创建哈夫曼树
    sourceData = [BinaryTree(x[0], x[1]) for x in sourceData]
    m = makeHuffman(sourceData)
    # 中序
    print(intermediateTraversal(makeHuffman(sourceData)))
    # 后序
    print(postorderTraversal(makeHuffman(sourceData)))
    

    如果对你有帮助,可以点击我这个回答右上方的【采纳】按钮,给我个采纳吗,谢谢

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月26日
  • 已采纳回答 11月18日
  • 创建了问题 11月17日

悬赏问题

  • ¥100 iOS开发关于快捷指令截屏后如何将截屏(或从截屏中提取出的文本)回传给本应用并打开指定页面
  • ¥15 unity连接Sqlserver
  • ¥15 图中这种约束条件lingo该怎么表示出来
  • ¥15 VSCode里的Prettier如何实现等式赋值后的对齐效果?
  • ¥15 流式socket文件传输答疑
  • ¥20 keepalive配置业务服务双机单活的方法。业务服务一定是要双机单活的方式
  • ¥50 关于多次提交POST数据后,无法获取到POST数据参数的问题
  • ¥15 win10,这种情况怎么办
  • ¥15 如何在配置使用Prettier的VSCode中通过Better Align插件来对齐等式?(相关搜索:格式化)
  • ¥100 在连接内网VPN时,如何同时保持互联网连接