2分探索木で特定のノードの次のノードを得る方法

[ぬっち]

いつもお世話になっています。

現在、勉強も兼ねてSTLのMapを自作しています。
Mapを実装するのには、2分探索木を用いる方法があるというのを聞き、自分なりに2分探索木を実装しました。
最終的には、STLのIteratorと似たような性質を持つものを作ろうとしています。
それで今のところは特定のキー値に対して、格納されている値を引き出すことには成功しているのですが、どうも現在Iteratorが指しているノードの次のノードを見つける方法がうまくいきません。
ソートされた状態で走査しようと考えているためInorderな走査を考えています。
よろしければ、その方法を教えていただけないでしょうか？
簡単なサンプルを載せておきます。

//現在出来ていること

MyMap < int, float > map;
map.add( 4, 3.0f );
map.add( 3, 2.0f );
map.add( 6, 9.0f );

MyMap < int, float > ::iterator it;
it = map.Find( 4 );

std::cout << it.GetValue() << std::endl;    //きちんと4.0と表示される

//行いたいこと

it = it.Inc();        //行いたい部分（次のノードを代入）
std::cout << it.GetValue() << std::endl;    //9.0と表示して欲しい

説明しにくい部分が多々あり、説明不足となっていますが、よろしくお願いします。

[たいちう]

MyMapのソースを見せる気はないのですか？添付ミス？

[ぬっち]

テキストファイルも添付出来たんですね^^;
画像ファイルだけかと思っていました;;

専用の型、
Portability::PortInt32　→ int
などがあり、かつコメントもほとんど書いていませんので、結構読みにくくなっているかもしれませんがよろしくお願いします。
BinarySearchTreeクラスのDeleteなどは今のところ問題ないので、このままでも大丈夫だと思っています。
注目していただきたいのはファイル内で実装していない、IteratorのGetNextメソッドです。（507行目あたりから）
このメソッドは、IncIterator内で呼ばれることによって、Iteratorのprivateメンバであるm_pNodePtrの更新を行っています。
現在作ってある状態では、当たり前ですが使用するとアクセス違反を起こします。（GetNext内の実装は今のところ出来上がっていないものとして考えてください。）
Iteratorの作り方自体、間違えている可能性も高いので、そのあたりも含めてよろしくお願いします。

[たいちう]

> 専用の型、
> Portability::PortInt32　→ int
> などがあり、かつコメントもほとんど書いていませんので、
> 結構読みにくくなっているかもしれませんがよろしくお願いします。

せっかく添付してくれましたが、コンパイルできるコードではないのですよね。
必要なコードを全て揃えてくれるか、専用の型など使わずに
現象を再現できる最小限の実装にしてくれた方がレスが付きやすいと思うのですが。
もちろん後者がお勧めです。

おそらくPortabilityクラスを回答者の憶測で作ってもデバッグできると思いますし、
一瞥するだけで問題点を指摘できる人もいるかもしれませんが、
今の私には時間もその気も能力もありません（能力的には将来も）。

これほどのコードが書けるならば、最小限の実装にして
デバッグすれば、自己解決できそうな気もします。

[ぬっち]

より簡単な実装法としては、私の勉強したサイトの方がよりよいのかなと思いますので、そちらを使わせていただきます。
私が2分探索木を勉強したのは、
http://www.geocities.jp/ky_webid/algorithm/017.html
からでして、
http://www.geocities.jp/ky_webid/algorithm/016.html
の通りがけ順なぞりにおいて今回の場合には、
printf( "%2d ", p->data );
でデータを出力する代わりに、
return p;
のように、指定したノードの次のノードを関数の戻り値にしたいのです。
つまり、

node GetNext( node* p )
{
//...いろいろな処理？
return (pの次のノード（つまり2分探索木では渡されたノードより大きい値を持つノードのうち最も小さな値を持つノード）)
}

ですがこの再帰関数を用いた方法ですと、どのようにこれを実装すればよいのかがよくわかりません。
それで再帰関数を用いない方法での実装も考えてみたのですが、どうもうまい方法が思いつきません。

一応、Map srcとして、動作済みのソースコードをUPしておきます。
Map srcを作り変えることも考えましたが、掲載したHPのほうがよりわかりやすいのではないかと思いましたので、そちらを採用しました。
よろしくお願いします。

[たいちう]

これで大分回答しやすくなりました。
アルゴリズムの説明用のコードを書いてみましたので、
宜しければ参考にしてください。

[ぬっち]

おお、なるほどたどってきた親ノードのポインタを確保しておくバッファと、だどったルートを記憶しているわけですね！
すごいわかりやすいです。

現在では、そのバッファは10となっていますが、これを可変にするにはStackあたりが良さそうですね。
いろいろとすっきりしました、ありがとうございました。