[解決済み] 幅優先探索を再帰的に実行する

質問

例えば、2分木の幅優先探索を実装したいとします。 再帰的に . あなたならどうする？

補助ストレージとしてコールスタックのみを使用することは可能でしょうか？

解決方法は？

(これは単なる思考訓練、あるいはトリック的な宿題や面接の質問だと思いますが、何らかの理由でヒープ領域が許されない[本当に悪いカスタムメモリマネージャ？奇妙なランタイム/OS問題？]、一方でスタックへのアクセスはまだある...という奇妙なシナリオが想像できます)。

パンゲアトランバーサルは伝統的にスタックではなくキューを使用します。 キューとスタックの性質はかなり正反対なので、コールスタック（これはスタックであり、それゆえにこの名前がある）を補助記憶装置（キュー）として使おうとすると、コールスタックで何か馬鹿馬鹿しいことをしていない限り、かなり失敗する運命にあるのです。

同じ意味で、非尾部再帰を実装しようとすると、本質的にアルゴリズムにスタックを追加することになるのです。 これはもはや二分木上の幅優先探索ではなく、従って従来のBFSの実行時間やその他は完全に適用されない。 もちろん、任意のループを再帰呼び出しにすることは可能だが、それは意味のある再帰とは言えない。

しかし、他の人が示したように、ある程度のコストをかけてBFSのセマンティクスに従ったものを実装する方法もあるのです。 比較のコストは高いが、ノードの探索は安い場合、次のようになる。 サイモン・ブーチャン を使えば、単純に深さ優先の反復探索を行い、葉だけを処理すればよいのです。 これは、ヒープに格納される成長するキューがなく、単にローカルな深さ変数があり、木が何度も走査されるにつれてスタックが呼び出しスタック上に何度も構築されることを意味します。 そして パトリック 配列にバックされた二分木は、通常、幅優先の探索順序で格納されます。したがって、これに対する幅優先探索は、補助的な待ち行列を必要とせず、些細なことでしょう。