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

求解用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)))
    

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

    评论
    解决 1 无用
    打赏 举报

相关推荐 更多相似问题