Python中的顺序遍历

Question

我要解决的问题是在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不能传递这个节点？？？提前谢谢

Answer 1

当你递归地给自己打电话时，像这样：

InOrder_search_recursive(node.lChild)

这只是一个普通的函数调用，和其他任何函数调用一样。它只是调用函数并返回结果。它不会自动return该函数的值，也不会执行任何其他操作。

所以，您执行左子树搜索，忽略结果，然后继续检查node.value == key，如果失败，您执行右子树搜索，再次忽略结果，并从函数的末尾掉下来，这意味着您返回None。

要使此工作正常，您需要return返回的值。但是，当然，只有当它是not None时。

另外，您忘记了将key参数传递给递归调用，所以您将得到一个TypeError。（我猜你的真实代码没有这个问题，但是因为你没有向我们展示你的真实代码，或者一个有效的例子，我不能确定……）

所以：

def Inorder_search_recursive(node, key):
    if not node:
        return None
    result = InOrder_search_recursive(node.lChild, key)
    if result is not None:
        return result
    if node.value==key:
        return node
    return InOrder_search_recursive(node.rChild, key)

（您不需要对右侧搜索进行not None检查，因为如果它返回None，我们就没有其他东西可以尝试了，只需要返回None。）

Answer 2

由于您的问题是to find the first occurrence node in its inorder traversal，您应该1）按顺序遍历树，2）在找到第一个匹配项时停止。

def search(node, key):
    if node is None:
        return None
    # Search the left subtree and return early if key is found
    n = search(node.lChild, key)
    if n is not None:
        return n
    # Check middle and return early if key is found
    if node.value == key:
        return node
    # Search right subtree
    return search(node.rChild, key)

Answer 3

我的另一个答案给出了一个新手友好的解决方案，但是如果你想要更有力和简洁的答案：

def Inorder_search_recursive_all(node, key):
    if not node:
        return
    yield from InOrder_search_recursive(node.lChild, key)
    if node.value==key:
        yield node
    yield from InOrder_search_recursive(node.rChild, key)

这将按顺序在树中生成所有匹配项。它将它们作为迭代器提供给您，因此如果您只需要第一个，您可以在找到一个迭代器时立即停止，而不会浪费工作：

def Inorder_search_recursive(node, key):
    return next(Inorder_search_recursive_all(node, key), None)

关于Iterators的教程部分和关于生成器的下一部分解释了这一工作的大部分原理。唯一缺少的位是yield from的解释，这在PEP 380中得到了解释。