天海一直在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日

悬赏问题

  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形