我要解决的问题是在BST中找到其无序遍历中的第一个出现节点。 下面是我的代码
def Inorder_search_recursive(node,key):
if not node:
return None
InOrder_search_recursive(node.lChild)
if node.value==key:
return node
InOrder_search_recursive(node.rChild)
这段代码总是不返回任何值,这是怎么回事。当我找到一个值为k的节点时,我想我已经返回了node。为什么python不能传递这个节点???提前谢谢
当你递归地给自己打电话时,像这样:
这只是一个普通的函数调用,和其他任何函数调用一样。它只是调用函数并返回结果。它不会自动
return
该函数的值,也不会执行任何其他操作。所以,您执行左子树搜索,忽略结果,然后继续检查
node.value == key
,如果失败,您执行右子树搜索,再次忽略结果,并从函数的末尾掉下来,这意味着您返回None
。要使此工作正常,您需要
return
返回的值。但是,当然,只有当它是not None
时。另外,您忘记了将
key
参数传递给递归调用,所以您将得到一个TypeError
。(我猜你的真实代码没有这个问题,但是因为你没有向我们展示你的真实代码,或者一个有效的例子,我不能确定……)所以:
(您不需要对右侧搜索进行
not None
检查,因为如果它返回None
,我们就没有其他东西可以尝试了,只需要返回None
。)由于您的问题是
to find the first occurrence node in its inorder traversal
,您应该1)按顺序遍历树,2)在找到第一个匹配项时停止。我的另一个答案给出了一个新手友好的解决方案,但是如果你想要更有力和简洁的答案:
这将按顺序在树中生成所有匹配项。它将它们作为迭代器提供给您,因此如果您只需要第一个,您可以在找到一个迭代器时立即停止,而不会浪费工作:
关于Iterators的教程部分和关于生成器的下一部分解释了这一工作的大部分原理。唯一缺少的位是
yield from
的解释,这在PEP 380中得到了解释。相关问题 更多 >
编程相关推荐