Python中的InOrder遍历

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的节点时，我想我已经返回了节点。为什么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，所以您应该按顺序遍历树，发现第一次出现时就停止。

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)

关于迭代器的教程部分和下面关于生成器的部分解释了这部分的工作原理。唯一缺失的位是对yield from的解释，这在佩普380中得到了解释。