DFSは再帰と余分なスペースなしで可能ですか？

Question

ベクトルベースの反復プロセスだけでなく再帰も、両方ともDFSツリー（bツリー）の探索に使用できます。どちらの場合も、再帰呼び出し中またはベクトル内でスタックに余分なスペースが必要です。宇宙を必要とせず、最小限のスペースが必要な技術は存在しますか？

Answer 1

バイナリツリーを検索している場合、各パスをビットのパターンとして表すことができます。したがって、ルートポイントから下向きに検索し、バイナリ語のビットをつぶやくことによって進行状況を把握することができます。各レベルに1ビット必要です。

 A 
    /\ 
    B C 
    /\ \ 
    D E F 

Aで検索を開始すると、ABDで指定された検索は00（左 - 左）です。次は01、左右に対応するABEです。 10はA-C-子供なし。 11はACFです。

最下位ビットは、トラバーサルの最後に向ける方向を示します（つまり、リーフを選択します）。ビットシーケンスが他の方法で読み取られる場合、このメソッドは幅優先トラバーサルを指定します。

情報を少なく保存した結果、同じノードに再度アクセスします。

これはデータのリニアスキャンに相当するため、ツリーを持つ利点が損なわれることに注意してください。スタック余裕ができないスペースがある場合は、あらかじめ割り当てられたベクトルを使用することをお勧めします。これをソートしておくと、バイナリ検索などの処理を行うことができます。バイナリ検索はこれよりも効率的です。

Answer 2

ツリーをトラバースするために必要なスペースは、ログ（N）スペースで最悪の場合でも実行できます。ノードが単一のブランチである場合は、O（1）スペース/メモリのパフォーマンスを使用して行うことができます。しかし、ログ（N）のパフォーマンスは実際には小さいです。 2^300ノード（この宇宙には収まらない）があると想像すれば、300のような検索に必要なスペースがあり、数KBのRAMに収まることができます。