我有一个构建哈夫曼树的方法如下:
def buildTree(tuples) :
while len(tuples) > 1 :
leastTwo = tuple(tuples[0:2]) # get the 2 to combine
theRest = tuples[2:] # all the others
combFreq = leastTwo[0][0] + leastTwo[1][0] #enter code here the branch points freq
tuples = theRest + [(combFreq,leastTwo)] # add branch point to the end
tuples.sort() # sort it into place
return tuples[0] # Return the single tree inside the list
但是当我为函数提供以下参数时:
[(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')]
我得到的错误是
File "<stdin>", line 7, in buildTree
tuples.sort()
TypeError: '<' not supported between instances of 'tuple' and 'str'
调试时我发现错误在 tuples.sort()
中。
最佳答案
抛出错误是因为您正在以 (priority, (node, node))
形式创建内部节点。对于相同的优先级,Python 然后尝试将来自叶节点的符号(因此 (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')))))
就个人而言,我会改用优先级队列,避免每次都排序。参见 How to implement Priority Queues in Python?
关于python - 类型错误 : '<' not supported between instances of 'tuple' and 'str' ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41913043/