algorithm - レベル優先順および深さ優先順で再帰的なツリー走査

Question

レベル優先順でツリーを再帰的にトラバースし、ポストオーダーで非再帰的にトラバースできるアルゴリズムはありますか。どうもありがとう。

Answer 1

再帰で使用される暗黙の呼び出しスタックの代わりにスタックを使用することにより、ポストオーダーでツリーを繰り返し再帰できます。

Answer 2

効果的に再帰的な幅優先検索を取得するには、反復深化深さ優先検索を使用できます。これは、分岐係数が高く、通常の幅優先検索が過度のメモリ消費によって停止する傾向がある状況に特に適しています。

編集: マルコス・マリンはすでにそれについて言及しましたが、完全を期すために、ウィキペディアの幅優先トラバーサルのページでは、アルゴリズムを次のように説明しています。

1. ルート ノードをキューに入れます。
2. ノードをキューから取り出して調べます。
   • 探している要素がこのノードで見つかった場合は、検索を終了して結果を返します。
   • それ以外の場合は、まだ検出されていない後続ノード (直接の子ノード) をキューに入れます。
3. キューが空の場合、グラフ上のすべてのノードが調べられました。検索を終了して「見つかりません」を返します。
4. 手順 2 から繰り返します。

注: キューの代わりにスタックを使用すると、このアルゴリズムが深さ優先検索になります。

非再帰的な深さ優先トラバーサルを行いたい場合、最後の行は明らかに興味深いものです。事前注文または事後注文を取得するには、ステップ 2.b でノードを追加する方法を変更するだけです。

Answer 3

ウィキペディアによると、

トラバーサル

リンクされたリストや 1 次元配列などの線形データ構造 (トラバーサルの論理的手段が 1 つしかない) と比較して、ツリー構造はさまざまな方法でトラバースできます。バイナリ ツリーのルートから開始して、実行できる 3 つの主要な手順があり、それらが実行される順序によってトラバーサル タイプが定義されます。

これらのステップ (順不同) は、現在のノードでアクションを実行する (ノードを「訪問する」と呼ばれます)、左の子ノードに移動し、右の子ノードに移動します。したがって、プロセスは再帰によって最も簡単に記述されます。

空でない二分木を前の順序でトラバースするには、ルート ノードから始めて、各ノードで次の操作を再帰的に実行します。

1. ノードにアクセスします。
2. 左のサブツリーをトラバースします。
3. 右のサブツリーをトラバースします。(これは深さ優先トラバーサルとも呼ばれます。 )

空でない二分木を順番にトラバースするには、各ノードで次の操作を再帰的に実行します。

1. 左のサブツリーをトラバースします。
2. ノードにアクセスします。
3. 右のサブツリーをトラバースします。(これは、対称トラバーサルとも呼ばれます。)

空でないバイナリ ツリーをポストオーダーでトラバースするには、各ノードで次の操作を再帰的に実行します。

1. 左のサブツリーをトラバースします。
2. 右のサブツリーをトラバースします。
3. ノードにアクセスします。

最後に、ツリーはlevel-orderでトラバースすることもできます。この場合、レベルのすべてのノードにアクセスしてから、下位レベルに移動します。これは、幅優先トラバーサルとも呼ばれ ます。