1

私が取り組んでいる問題は、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)

このコードは常に None を返します。何が問題なのですか。値 k のノードを見つけたら、ノードを返したと思います。Pythonがこのノードを通過できないのはなぜですか???事前に感謝します

4

3 に答える 3

3

次のように、自分自身を再帰的に呼び出す場合:

InOrder_search_recursive(node.lChild)

これは、他の関数と同様に、通常の関数呼び出しです。関数を呼び出して結果を返すだけです。returnその関数からの値を自動的に取得したり、他のことをしたりすることはありません。

したがって、左サブツリー検索を実行し、結果を無視してから checknode.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

私の他の答えは初心者に優しい解決策を提供しますが、より強力で簡潔な答えが必要な場合:

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に関するチュートリアルのセクションと、Generators に関する次のセクションでは、これがどのように機能するかのほとんどを説明しています。唯一欠けているビットは、PEP 380yield fromで説明されているの説明です。

于 2014-01-17T01:20:45.987 に答える
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 に答える