Python中的有序遍历 [英] InOrder Traversal in Python

问题描述

我要解决的问题是在BST中找到其顺序遍历中的第一个出现节点. 我的代码在下面给出

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)

此代码始终返回None，这是怎么回事.当我找到一个值为k的节点时，我想我已经返回了节点.为什么python无法通过此节点????谢谢

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

推荐答案

以递归方式调用自己时，就像这样:

When you call yourself recursively, like this:

InOrder_search_recursive(node.lChild)

与其他任何函数一样，这只是正常的函数调用.它只是调用函数并返回结果.它不会自动return该函数的值或执行其他任何操作.

That's just a normal function call, like any other. It just calls the function and gets back a result. It doesn't automatically return the value from that function, or do anything else.

因此，您进行左子树搜索，忽略结果，然后继续检查node.value == key，如果失败，则进行右子树搜索，再次忽略结果，然后移到最后函数的含义，即您返回None.

So, you do the left-subtree search, ignore the results, then go on to check node.value == key, and, if that fails, you do the right-subtree search, again ignore the results, and fall off the end of the function, meaning you return None.

要使此工作有效，您需要return取回的值.但是，当然，只有not None.

To make this work, you need to return the value you got back. But, of course, only if it's not None.

此外，您忘记了将key参数传递给递归调用，因此您只会得到TypeError. (我猜您的真实代码没有这个问题，但是由于您没有向我们展示您的真实代码或有效的示例，所以我不确定…)

Also, you forgot to pass the key argument down to the recursive call, so you're just going to get a TypeError. (I'm guessing your real code doesn't have this problem, but since you didn't show us your real code, or a working example, I can't be sure…)

所以:

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.)

(You don't need the not None check for the right-side search, because if it returns None, we have nothing else to try and are just going to return None anyway.)

这篇关于Python中的有序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！