1

二分木の葉ノードのリストと内部ノードのリストのタプルを返す関数を作成しようとしています。

そこで私が試みた方法は、2 つのリスト (1 つはリーフ ノード用、もう 1 つは内部ノード用) を初期化することでした。

私はすでにコードを作成しており、問題なく動作するはずですが、問題が 1 つだけあります。再帰的に行う必要があるため、関数自体を呼び出す必要があります。つまり、リストの初期化が再度行われ、リストがリセットされるだけです。これは私が欲しいものではありません。それらのリストに要素を追加し続け、最終的にそれらを返したい...

編集:申し訳ありませんが、コードを追加することはできませんが、大まかなアイデアを提供できます:

list1=[]
list2=[]
if (leaf node reached):
            add leaf node to list1

else:
            add node to list2
            call the function on the left child
            call the function on the right child
return (leaves_data,internals_data)
4

2 に答える 2

0

何らかの方法で、初期化が 1 回だけ行われるようにする必要があります。これにはさまざまな方法があります。

これを行う 1 つの方法は、関数の外部で初期化を行うことです。次のようなもの (疑似コード) があるとします。

function recursiveFunction():
    // Here you had your old init code, you don't need it here anymore
    // Here your function is the same as before
    // [ ... ]
    recursiveFunction()
    return; // Some return statement
end 

// Init stuff here (make sure these variables/list you init are globally defined, so they can be accessed from inside the function
// Then call your recursive function:
recursiveFunction()

それを行う別の簡単な (ただし、必ずしもきれいな方法であるとは限りません)、init が完了したときに true に設定されるグローバル変数を外部に置くことです。たとえば、次のようなものです。

global variable init_is_done = false // Make sure this can be accessed inside your function

function recursiveFunction():
    // Check if init_is_done is true before doing init
    if not init_is_done:
        // Have your init code here
        init_is_done = true
    endif

    // Here your function is the same as before
    // [ ... ]
    recursiveFunction()
    return; // Some return statement
end 

// Now you can just call your function
recursiveFunction()

使用している言語に応じて、さまざまな方法が適しています。私は確かに関数の外にinitのものを持たせようとします。これがうまくいくことを願っています。

于 2013-03-15T02:37:02.730 に答える
0

各再帰ステップで、最初に空のリストを作成して、その反復からのデータのみを保存します。次に、より多くのコンテンツを含む他のリストを返すことが期待される再帰関数を呼び出します。返されたリストをに追加すると、再帰関数が反復しているツリーの関連するブランチに正しい部分的な結果が得られます。最後に、関数からマージされたリストを返し、ツリーの上位レベルで結果を再度追加し、ルート レベルに戻るまで結果を成長させます。

これは再帰ステップと呼ばれ、再帰のベース (つまり、再帰を停止させるルール) が正しい限り機能します。

def get_nodes(l):
    # Recursion base
    if l is None: return ([], [])
    if l.children is None: return ([], [l])

    # Recursion step
    this = ([l], [])
    internal, leaf = get_nodes(l.children.left)
    this[0] += internal
    this[1] += leaf

    internal, leaf = get_nodes(l.children.right)
    this[0] += internal
    this[1] += leaf

    return this

(注: テストされていない疑似コード、単なる例)

上記の説明はすべて概念的なものであり、単純な実装と見なす必要があります。ただし、実際の実装では、複数のリストを何度も作成して追加することは避けます。コード内でこれを行うには、リストをグローバル スコープに移動し、global キーワードを使用してグローバル値をローカル変数にバインドします。

于 2013-03-15T02:47:00.883 に答える