これは宿題ではなく、面接の質問です。
ここでの問題は、アルゴリズムが定数空間でなければならないことです。スタックなしでこれを行う方法についてはまったくわかりません。スタックを使用して書いたものを投稿しますが、とにかく関係ありません。
私が試したことは次のとおりです。事前注文トラバーサルを実行しようとしましたが、一番左のノードに到達しましたが、そこで立ち往生しています。スタック/親ポインターなしでバックアップを「再帰」する方法がわかりません。
どんな助けでも大歓迎です。
(Java は私が快適に使用できるものなので、Java としてタグ付けしていますが、明らかなように、言語にかなり依存しています。)
私はそれを完全には考えていませんでしたが、その過程でツリーを台無しにする意思がある限り、それは可能だと思います.
すべてのノードには 2 つのポインターがあるため、二重にリンクされたリストを表すために使用できます。Root から Root.Left=Current に進むとします。これで Root.Left ポインタは使い物にならなくなったので、Current.Right に割り当てて Current.Left に進みます。一番左の子に到達するまでに、いくつかのノードから木がぶら下がっているリンク リストが作成されます。それを反復し、遭遇するすべての木についてプロセスを繰り返します
編集：考え抜いた。順番に印刷するアルゴリズムは次のとおりです。
void traverse (Node root) {
traverse (root.left, root);
}
void traverse (Node current, Node parent) {
while (current != null) {
if (parent != null) {
parent.left = current.right;
current.right = parent;
}
if (current.left != null) {
parent = current;
current = current.left;
} else {
print(current);
current = current.right;
parent = null;
}
}
}
Morris Inorder ツリー トラバーサルはどうですか? スレッド化されたツリーの概念に基づいており、ツリーを変更しますが、完了したら元に戻します。
リンキー: http://geeksforgeeks.org/?p=6358
余分なスペースを使用しません。
下向きのポインタベースのツリーを使用していて、親ポインタやその他のメモリがない場合、一定のスペースをトラバースすることはできません。
バイナリツリーがポインタベースのオブジェクト構造ではなく配列にある場合は可能です。ただし、その後、任意のノードに直接アクセスできます。これは一種の不正行為です;-)
iluxa の元の回答の短縮版を次に示します。これは、まったく同じノード操作と印刷手順をまったく同じ順序で実行しますが、単純化された方法で実行されます [1]。
void traverse (Node n) {
while (n) {
Node next = n.left;
if (next) {
n.left = next.right;
next.right = n;
n = next;
} else {
print(n);
n = n.right;
}
}
}
[1] さらに、ツリーのルート ノードに左の子がない場合でも機能します。
受け入れられた回答には次の変更が必要です。そうしないと、BST にノードが 1 つしかないツリーが出力されません。
if (current == NULL && root != NULL)
print(root);
検索ツリーなので、いつでも次のキー/エントリを取得できます
次のようなものが必要です（コードはテストしていませんが、可能な限り簡単です）
java.util.NavigableMap<K, V> map=...
for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) {
process(e)
}
明確にするために、これはhigherEntryであるため、再帰的ではありません。そこにあります:)
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
上記のiluxaの回答に対するマイナーな特殊ケース
if(current== null)
{
current = root;
parent = current.Right;
if(parent != null)
{
current.Right = parent.Left;
parent.Left = current;
}
}
質問のタイトルには、ノードに「親」ポインターがないことは記載されていません。BST では必ずしも必要ではありませんが、多くのバイナリ ツリーの実装には親ポインターがあります。クラスノード{ノード*左。ノード*右; ノード* 親; データデータ; };
この場合、紙に木の図をイメージし、端の両側から上下に、木の周りを鉛筆で描きます（下に行くときは、端の左側になり、上がると右側になります）。基本的に、4 つの状態があります。
Traverse( Node* node )
{
enum DIRECTION {SW, NE, SE, NW};
DIRECTION direction=SW;
while( node )
{
// first, output the node data, if I'm on my way down:
if( direction==SE or direction==SW ) {
out_stream << node->data;
}
switch( direction ) {
case SW:
if( node->left ) {
// if we have a left child, keep going down left
node = node->left;
}
else if( node->right ) {
// we don't have a left child, go right
node = node->right;
DIRECTION = SE;
}
else {
// no children, go up.
DIRECTION = NE;
}
break;
case SE:
if( node->left ) {
DIRECTION = SW;
node = node->left;
}
else if( node->right ) {
node = node->right;
}
else {
DIRECTION = NW;
}
break;
case NE:
if( node->right ) {
// take a u-turn back to the right node
node = node->right;
DIRECTION = SE;
}
else {
node = node->parent;
}
break;
case NW:
node = node->parent;
break;
}
}
}
ツリー自体を変更せずにバイナリ ツリーをトラバースできます (ノードに親ポインターがある場合)。そして、それは一定のスペースで行うことができます。同じhttp://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/のこの便利なリンクを見つけました
これは二分探索木であるため、一連の右/左の決定によってすべてのノードに到達できます。そのシリーズを0/1、最下位ビットから最上位ビットとして説明します。したがって、関数f（0）は、「葉が見つかるまで右側の分岐をとることによって見つかったノードを意味します。f（1）は、1つを左に、残りを右にとることを意味します。f（2）-つまり、バイナリ010- -は、葉が見つかるまで右、左、右の順に進むことを意味します。すべての葉に当たるまで、n = 0からf（n）を繰り返します。効率的ではありません（それぞれツリーの最上部から開始する必要があるため）。時間）が、一定のメモリと線形時間。