TypeError：'tuple' 和 'str' 实例之间不支持 '<'

小能豆

TypeError：'tuple' 和 'str' 实例之间不支持 '<'

py

我有一个构建哈夫曼树的方法，如下所示：

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

阅读 19

2024-11-12

小能豆

抛出该错误是因为您正在以(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')))))

2024-11-12

小能豆

问题是，当函数构造树时，树中元素的结构tuples会变得不一致。最初，tuples是一个元组列表，每个元组包含一个频率和一个字符，例如(1, 'b')。但是，一旦开始组合节点，就会添加不同形式的元组——包含频率和嵌套元组的元组，例如(3, ((1, 'b'), (2, 'c')))。

当tuples.sort()调用时，Python 遇到结构不同的元组而无法进行比较，从而导致TypeError。

解决方案

为了解决这个问题，我们需要确保中的所有元素都tuples具有相同的形式，以使排序操作正常工作。我们可以通过确保每个项目都是形式为的元组来实现这一点，(frequency, subtree)其中subtree可以是字符或另一个元组。这样，排序将始终基于第一个元素（即频率）进行比较。

修改后的函数如下：

def buildTree(tuples):
    while len(tuples) > 1:
        # Sort based only on the frequency (the first element of each tuple)
        tuples = sorted(tuples, key=lambda x: x[0])

        # Get the two elements with the smallest frequencies
        leastTwo = tuples[0:2]
        theRest = tuples[2:]

        # Combine the two smallest elements to create a new subtree
        combFreq = leastTwo[0][0] + leastTwo[1][0]
        newNode = (combFreq, leastTwo)  # New combined node

        # Add the new node to the list and repeat
        tuples = theRest + [newNode]

    return tuples[0]  # Return the final tree

# Test with your input
tree = buildTree([(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')])
print(tree)

变更说明

使用键排序：我们使用而不是tuples根据频率进行排序。这使得排序明确，因为它始终考虑第一个元素（频率）。sorted(tuples, key=lambda x: x[0])``tuples.sort()
新节点构造：新的组合节点表示为(combFreq, leastTwo)，其中leastTwo是两个最小节点的元组。这样，每个元素仍然是一个(frequency, subtree)元组，保持结构的一致性。

输出

此代码现在应该可以无错误地执行，并正确构建哈夫曼树。的结构tree将表示根据提供的频率构建的完整二叉树。

2024-11-12