抛出错误是因为您正在创建内部节点(priority, (node, node))
形式。对于相同的优先级,Python 然后尝试比较叶节点中的符号(因此 a 中的第二个元素(priority, symbol)
节点元组)与(node, node)
来自内部节点的元组:
>>> inner = (combFreq, leastTwo)
>>> inner
(2, ((1, 'b'), (1, 'd')))
>>> theRest[1]
(2, 'c')
>>> theRest[1] < inner
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'str' and 'tuple'
为了构建哈夫曼树,如果你想对节点数组进行排序,你只需要按优先级排序,忽略其余的元组(符号或子节点):
tuples.sort(key=lambda t: t[0])
通过该修正,您的buildTree()
函数生成一棵树:
>>> buildTree([(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')])
(15, ((6, ((3, 'a'), (3, ((1, 'g'), (2, 'c'))))), (9, ((4, ((2, 'f'), (2, ((1, 'b'), (1, 'd'))))), (5, 'e')))))
就我个人而言,我会使用优先级队列,以避免每次都进行排序。看如何在Python中实现优先级队列?