1

The problem I am tackle with is to find the first occurrence node in its inorder traversal in a BST. The code I have is given below

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)

This code always return None, what's wrong with it. I think I've return node when I find a node with value k. Why cannot python pass this node???Thanks in advance

4

3 回答 3

3

当你递归调用自己时，像这样：

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无论如何都会返回。）

于 2014-01-17T00:59:13.480 回答
1

由于您的问题是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)
于 2014-01-17T01:02:46.717 回答
1

我的另一个答案给出了对新手友好的解决方案，但如果您想要更强大和简洁的答案：

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，这在PEP 380中进行了解释。

于 2014-01-17T01:20:45.987 回答