Python中的InOrder遍历

我正在处理的问题是在BST中的inorder遍历中查找第一个出现节点。我有下面的代码Python中的InOrder遍历

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)

该代码被赋予总是返回None，有什么不对的地方。当我找到一个值为k的节点时，我想我已经返回了节点。为什么不能蟒蛇通过这个节点???在此先感谢

来源

2014-01-17 lexie

如果这是一个二叉搜索树，那么使用实际的二分搜索而不是顺序搜索可能会获得更好的结果。 – user2357112

是的你是对的，我只是想通了，我们可以首先用价值键找到那个值。我们可以使用BST的财产来节省很多时间。然后搜索它的左子树。如果其左子树也有一个带有值键的节点，则立即返回。 – lexie

当你称自己递归，就像这样：

InOrder_search_recursive(node.lChild)

这只是一个普通的函数调用，就像任何其他。它只是调用函数并返回结果。它不会自动从该函数中获取值，或者执行其他任何操作。所以，你做左子树搜索，忽略结果，然后继续检查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-17 00:59:13 abarnert

因为你的问题是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-17 01:02:46

我对方的回答让新手友好的解决方案，但如果你想更强大，更简洁的回答：

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中解释。

来源

2014-01-17 01:20:45 abarnert

Python中的InOrder遍历

回答

相关问题