天海一直在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 工创大赛太阳能电动车项目零基础要学什么
  • ¥20 limma多组间分析最终p值只有一个
  • ¥15 nopCommerce开发问题
  • ¥15 torch.multiprocessing.spawn.ProcessExitedException: process 1 terminated with signal SIGKILL
  • ¥15 QuartusⅡ15.0编译项目后,output_files中的.jdi、.sld、.sof不更新怎么解决
  • ¥15 pycharm输出和导师的一样,但是标红
  • ¥15 想问问富文本拿到的html怎么转成docx的
  • ¥15 我看了您的文章,遇到了个问题。
  • ¥15 GitHubssh虚拟机连接不上
  • ¥15 装完kali之后下载Google输入法 重启电脑后出现以下状况 且退不出去 桌面消失 反复重启没用