限られたメモリと、バイナリツリーの最初のヌルを探します

Question

Iは、各ノードが値を持つことができるバイナリツリーを持っている。

私はnull値を持ち、ルートに最も近いツリー内のノードを見つけたいです。ルートから同じ距離を持つ2つのノードがある場合は、どちらかが行います。私は、読み取りの数は、バイナリツリーへのアクセスを最小限にする必要があります。ワーキングメモリはちょうどk個のノードに制限されていることを前提としています。

深さkにDFSを網羅あるが、私は最初のツリー全体を介して実行しない限り、最も近いノードを見つけることができません。 BFSは一番近いでしょうが、DFSが同じメモリで、より深いヌルを見つけることができますので、それが失敗する可能性があります。

私は、読み取りの最小数は、ツリーへのアクセスを持っていると、最も近いヌルノードを見つけるしたいと思います。

（私は一般的な解決策が良いでしょう、あまりにも、最終的にNウェイの木でこれを実装する必要がないでしょう。木へんが書き込みアクセスを、ちょうど読みください。）

Answer 1

あなたは深さ優先探索を反復-深め見てみたいことがあります。これは、自動的に最も近いノードを見つけるだろうが、DFSと同じ深さに到達することができるようになります。これは、より多くの読み取りを使用しますけれどもアクセスします。

また、BFSで開始することができ、あなたが許可されたメモリとヌルが見つからない場合は、DFSを実行します。

Answer 2

私はシンプルな木の剪定でDFSを実装します。だから、それはあなたがツリー全体を実行する必要があること本当ではありません。たとえば

あなたは高さhでのnull値を見つけた場合は、のと同じである。のノードをスキップすることができますか深い位置ます。

Answer 3

あなたは、データ構造を変更することができない場合は、各ノード読まなければならないでしょう - 。幅優先を

あなたはデータ構造を変更することができた場合は、各ノードは最初のnullの子ノードの相対的な深さを記録することができます。 （それぞれの子の同等の値から動作するように）。

そして、あなたが最も初期のヌルを探していたときに追いかけるために、ツリー内のどのラインを知っています。

Answer 4

あなたは配列にあなたのツリーを保存するために喜んでいる場合は、

、簡単な方法があります。むしろ、その左右の子へのポインタを有する各ノードよりも、ノードnの子は1 + 2N、アレイ中2N + 2です。 （そして、ノードnの親は（n-1）/ 2、もしN！= 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進木に拡張することができます。例えば、三元ツリーに、左の子が右+ 3 3Nであり、1 + 3Nは、中心2 + 3Nであり、親は（n-1）/ 3本の場合、N！= 0。