求解用python遍历哈夫曼编码（中序遍历、后序遍历）

Question

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

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

Answer 1

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)))

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