•  06-07-2019
  •  | 
  •  

質問

リンクツリーのすべてのノードを訪問する最良の方法は何ですか（すべてのノードは親とすべての子への参照を持ち、ルートノードは親としてnullを持ちます）。非再帰のブラウニーポイント。

役に立ちましたか？

解決

擬似コード：

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

編集：再帰的かどうか
技術的に正しいために、そしてこの投稿でAndreyTと他の人が指摘したように、このアプローチは、明示的に管理されたスタックが代わりに使用される再帰アルゴリズムの 形式ですCPUスタックと、Whileループのレベルで再帰が行われる場所。これは、いくつかの微妙でありながら重要な点で再帰的実装とは異なりますそれ自体：

  • ＆quot;変数＆quot;のみスタックにプッシュされます。 「スタックフレーム」はありません。スタック上の関連するリターンアドレス、唯一の「リターンアドレス」 whileループに対して暗黙的であり、そのインスタンスは1つしかありません。
  • 「スタック」次の「フレーム」をリストとして使用できます。リスト内の任意の場所で、どのような方法でもロジックにブレーキをかけることなく取得できます。

他のヒント

先行予約の走査を探しています。私はあなたがそれを非再帰的に行うことができると思います キュー：。擬似コード：

空のキューを作成し、ルートノードをプッシュします。

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

すべての子へのリンクと親へのリンクもある場合、非再帰的アルゴリズムはかなり簡単です。木があることを忘れてください。それは、各親子リンクが1つのジャンクションから別のジャンクションへの通常の双方向廊下である迷宮だと考えてください。迷路全体を歩くために必要なことは、各ジャンクションで左側の次の廊下に曲がることだけです。 （または、左手が常に左側の壁に触れている状態で迷路を歩くと考えてください）。ルートジャンクションから開始する（および任意の方向に移動する）場合は、ツリー全体を歩いて、常に子の前に親を訪問します。各「廊下」この場合、2回（一方の方向と他方の方向）に移動し、各「ジャンクション」 （ノード）は、「コリドー」と同じ回数だけアクセスされます。参加してください。

一連のノードを使用します。起動するセットにルートを配置します。次に、ループ内で、ノードをセットから引き出してアクセスし、その子をセットに入れます。セットが空になったら、完了です。

擬似コード内：

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

ルートノードから開始し、既にアクセスしたノードの親/子のみにアクセスする場合、ツリーをトラバースしてその先祖にアクセスする前にノードにアクセスする方法はありません 。

あらゆる種類のトラバーサル、深さ優先（再帰/スタックベース）、幅優先（キューベース）、深さ制限、または単に順序なしセットからそれらを引き出すだけです。

「最高の」メソッドはツリーに依存します。最初に幅が広いのは、枝がほとんどない非常に背の高い木に適しています。深さ優先は、多くの枝を持つ木に適しています。

ノードには実際に親へのポインタがあるため、定数メモリアルゴリズムもありますが、はるかに遅くなります。

スペースの複雑さがその特定の検索アルゴリズムの悩みの種であることが多いため、幅優先検索に同意しません。おそらく反復深化アルゴリズムを使用することは、このタイプの使用のより良い代替手段であり、幅優先探索と同じタイプのトラバーサルをカバーします。幅優先検索のフリンジの処理にはわずかな違いがありますが、コーディングを（疑似）するのはそれほど難しくないはずです。

リファレンス： http://en.wikipedia.org/wiki/Iterative_deepening

これは、非再帰的アプローチである truly です：スタックなし、一定のスペース。このPythonコードは、各ノードに子のリストが含まれ、ノードオブジェクトが等式を定義しないことを前提としているため、「インデックス」関数はIDを比較しています：

def walkTree(root, visit_func):
    cur  = root
    nextChildIndex = 0

    while True:
        visit_func(cur)

        while nextChildIndex >= len(cur.children) and cur is not root:
            nextChildIndex = cur.parent.children.index(cur) + 1
            cur  = cur.parent

        if nextChildIndex >= len(cur.children):
            break

        cur = cur.children[nextChildIndex]
        nextChildIndex = 0

少し洗練され、より簡潔で読みやすくすることができると確信していますが、それが要点です。

ルート（レベル0）でノードのリストを作成し、各ノードを順に反復処理して、レベルを終了したら、直接の子（親ノードが現在探しているノード）を探します（レベル1） 0を繰り返しレベル1に移動し、まだアクセスしていないノードがなくなるまで続けます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top