![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67b6d)
二分探索木の行きがけ順走査は、普通再起を使うと思います。
再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。
木以外に何か使ってもいいのなら、
http://www.psg.cs.titech.ac.jp/pro1/11.pdf
の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。
再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。
No.1ベストアンサー
- 回答日時:
まず、「再起」ではなく「再帰」であることにご注意ください。
構造化された言語で関数やサブルーチンを呼び出すとき、通常「コールスタック」と呼ばれるスタックの一種を引数や返り値、リターンアドレスの受け渡しや保存に用います。Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。
木を使っていいのであれば、木をスタックとして使えばよさそうです。ただ、木をスタックや連想配列として使っていいのであれば、効率以外に制限はないと言えますし、木をスタックなどとして使ってはいけないのであれば、どの使い方が「他のどのデータ構造にもない使い方」といえるのか判断が難しいでしょう。
「木以外のデータ構造を使わない」という条件だけではあまり意味がない条件だと思えます。もう少し厳密な条件があるのかもしれません。
すみません。誤字がありました。
>Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。
そうですよね。自分でも確かにスタックは無いと、と思います。
木の使い方も含めて、何かもう少し条件をはっきりさせないといけないですね。実はこのことを発言した張本人が、後で『木以外のデータ構造は何も使わないでは無理かも。他のデータ構造をちょっと使ってもいい』などと口走っていた気がします…。
ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・「I love you」 をかっこよく翻訳してみてください
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・昔のあなたへのアドバイス
- ・かっこよく答えてください!!
- ・あなたが好きな本屋さんを教えてください
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
次のhtml・cssでspan内の文字を...
-
配列にnullを代入すると、null...
-
マイクラでPythonのプログラミ...
-
ゲーム開発の入門書を探しています
-
正規表現について質問です。 カ...
-
jdk17.06のインストーラーが起...
-
プログラミングの問題です。大...
-
jdbcでinsert,delete,createをe...
-
session,requestはjspで未定義...
-
サーブレットをapacheで公開す...
-
下記のリストならno002が含まれ...
-
is this even a thing?
-
JAの支部?地域の農協のカード...
-
えハミルトン路と全域木のちが...
-
CSV出力を画面から選択したデー...
-
ショートカットキーについて
-
list の空は [] ってあわらすのに
-
あんまりお料理しないのに台所...
-
質問です。 配列が100以上の場...
-
Jupyter notebookですわかりま...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
printf / sprintf のスタック消...
-
最大スタックサイズを大きくす...
-
_CRTIMPの意味は?
-
スタックフレームの消滅
-
スタックの伸張方向
-
エラー?メッセージ
-
スタックとキューの使い所
-
CASLとCASL2の違いについて
-
逆ポーランド記法
-
キューとスタックの問題です、...
-
再帰関数を使うとき、ソフトウ...
-
pthreadのスタックサイズ設定取...
-
再帰処理を非再帰処理に書き換...
-
二分探索木の行きがけ順走査
-
gccでスタックサイズを変更する...
-
スタックのpush/pop動作について
-
スタックを用いて整数配列を入...
-
ゆゆにゃ。
-
スタック領域変更
おすすめ情報