リンクされたツリーのすべてのノード (すべてのノードは親とすべての子への参照を持ち、ルート ノードは親として null を持ちます) を訪問する最良の方法は何ですか? 非再帰的ブラウニーポイント。
10 に答える
擬似コード:
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 ループ。これは、いくつかの微妙ではあるが重要な点で、再帰的な実装自体とは異なります。
- 「変数」のみがスタックにプッシュされます。スタックには「スタック フレーム」と関連付けられた戻りアドレスはなく、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
ルート ノードから開始し、既にアクセスしたノードの親/子のみにアクセスする場合、先祖にアクセスする前にノードにアクセスするようにツリーをトラバースする方法はありません。
あらゆる種類のトラバーサル、深さ優先 (再帰/スタック ベース)、幅優先 (キュー ベース)、深さ制限、またはそれらを順序付けられていないセットから引き出すだけで機能します。
「最良の」方法はツリーによって異なります。幅優先は、枝がほとんどない非常に背の高い木に適しています。深さ優先は、多くの枝を持つ木に適しています。
ノードは実際にはその親へのポインタを持っているため、定数メモリ アルゴリズムもありますが、はるかに低速です。
スペースの複雑さがその特定の検索アルゴリズムの悩みの種であることが多いため、幅優先検索には同意しません。おそらく、反復深化アルゴリズムを使用することは、このタイプの使用のより良い代替手段であり、幅優先検索と同じタイプのトラバーサルをカバーしています。幅優先検索からのフリンジの処理には小さな違いがありますが、(疑似) コード化するのはそれほど難しくありません。
ルート (レベル 0) でノードのリストを作成し、各ノードを順番に反復して、直接の子 (親ノードが現在探しているノードである) を探します (レベル 1)。レベル 0 が終了したら次に進みます。レベル 1 を繰り返し、未訪問のノードがなくなるまで繰り返します。