私は各ノードが値を持つことができるバイナリツリーを持っています。制限付きメモリを持つバイナリツリーで最初にnullを見つけよう
値がnullで、ルートに最も近いノード内のノードを探したいとします。ルートから同じ距離のノードが2つある場合は、どちらかが実行されます。バイナリツリーへの読み取りアクセス数を最小限に抑える必要があります。作業メモリがk個のノードに限定されていると仮定してください。
深さkまでのDFSは網羅的ですが、ツリー全体を最初に実行しない限り、最も近いノードは見つかりません。 BFSは最も近いものを見つけるでしょうが、DFSが同じメモリを持つより深いヌルを見つけることができるため、失敗する可能性があります。
私はツリーへの読み取りアクセスを最小限に抑えて、最も近いヌルノードを見つけたいと考えています。
（私は一般的な解決策が良いでしょう、あまりにも、最終的にNウェイの木でこれを実装する必要がないでしょう。木へんが書き込みアクセス、ちょうどお読みください。）
Iterative-deepening depth-first searchをご覧ください。それは最も近いノードを自動的に見つけますが、DFSと同じ深さに達することができます。それはより多くの読み取りアクセスを使用します。
また、BFSで始めることもできます。また、許可されたメモリでnullが見つからない場合は、DFSを実行します。
IDDFSを最適化するための良い順序があるのだろうか？たとえば、私のメモリが4つのノードであり、ツリーがバイナリであれば、ノード0,1,2,3を読み込んだ後、すでに0,1,2を読み込んでいるので、最初からノード4,5,6を読み込むことができます。今私が0,1,2,6をメモリに持っていれば、0,2などを再読み込みせずに7を読むことができます。 意味が分かるように描かなければならない... – Eyal
私はあなたを正しく理解しているかどうかはわかりませんが、あなたはそれらのノードを読むという事実を記録するためにメモリを使わなければならないでしょう。 BFS以上にはならない。 – Geerad
@Geerad：IDDFSにはlessor memoryとBFSが必要です.DFSの明示的なキューは必要ありません。 –
あなたが変更できない場合データ構造の場合は、各ノードを幅広く読み取る必要があります。
データ構造を変更できる場合、各ノードは最初のヌル・チャイルド・ノードの相対的な深さを記録できます。 （それぞれ子供の同等の価値から取り組む）。
次に、最も古いヌルを探すときに、ツリー内のどの行が追跡されるかを知っています。
単純なツリープルーニングを使用してDFSを実装します。それで、あなたは木全体を走らなければならないというのは本当ではありません。
たとえば、高さhでヌル値を見つけた場合、ノードをスキップして同じ位置またはより深い位置にすることができます。
ツリーを配列に保存したい場合は、簡単な方法があります。各ノードがその左と右の子へのポインタを持つのではなく、ノードnの子は配列の2n + 1と2n + 2です。 （とN場合はノードnの親が、N-1）/ 2（である！= 0）
Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};
単純に配列を反復処理は、直線的BFSと同等ですが、Oのスペース要件（1）。
これは、n-aryツリーに簡単に拡張できます。例えば、3値ツリーでは、左側の子は3n + 1であり、中心は3n + 2であり、右側は3n + 3であり、n！= 0ならばparentは（n-1）/ 3である。
私は、最も近いヌルノードが最も少ないリードよりも重要だと考えますか？ –
BFSの失敗の詳細を教えてください。 –
リチャード：深さk内にヌルノードがある場合は、ルートに最も近いものを出力したい。そうでなければ、私は失敗する。 Pate：BFSのメモリ使用量が指数関数的に増加します。 kのメモリでは、私はDFSでk深度に達することができますが、BFSは深く進むことができません。だから、DFSで見つけられるがBFSでは見つけられない解決策があるかもしれない。 – Eyal