二分探索木の行きがけ順走査

質問

二分探索木の行きがけ順走査は、普通再起を使うと思います。
再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。
木以外に何か使ってもいいのなら、
http://www.psg.cs.titech.ac.jp/pro1/11.pdf
の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。
再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。

回答No.1

Foxtrot_OW · ベストアンサー

まず、「再起」ではなく「再帰」であることにご注意ください。

構造化された言語で関数やサブルーチンを呼び出すとき、通常「コールスタック」と呼ばれるスタックの一種を引数や返り値、リターンアドレスの受け渡しや保存に用います。Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。

木を使っていいのであれば、木をスタックとして使えばよさそうです。ただ、木をスタックや連想配列として使っていいのであれば、効率以外に制限はないと言えますし、木をスタックなどとして使ってはいけないのであれば、どの使い方が「他のどのデータ構造にもない使い方」といえるのか判断が難しいでしょう。
「木以外のデータ構造を使わない」という条件だけではあまり意味がない条件だと思えます。もう少し厳密な条件があるのかもしれません。

お礼

すみません。誤字がありました。

＞Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。
そうですよね。自分でも確かにスタックは無いと、と思います。
木の使い方も含めて、何かもう少し条件をはっきりさせないといけないですね。実はこのことを発言した張本人が、後で『木以外のデータ構造は何も使わないでは無理かも。他のデータ構造をちょっと使ってもいい』などと口走っていた気がします…。

ありがとうございました。