- ベストアンサー
二分探索木の行きがけ順走査
二分探索木の行きがけ順走査は、普通再起を使うと思います。 再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。 木以外に何か使ってもいいのなら、 http://www.psg.cs.titech.ac.jp/pro1/11.pdf の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。 再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。
- esid
- お礼率50% (2/4)
- Java
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
まず、「再起」ではなく「再帰」であることにご注意ください。 構造化された言語で関数やサブルーチンを呼び出すとき、通常「コールスタック」と呼ばれるスタックの一種を引数や返り値、リターンアドレスの受け渡しや保存に用います。Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。 木を使っていいのであれば、木をスタックとして使えばよさそうです。ただ、木をスタックや連想配列として使っていいのであれば、効率以外に制限はないと言えますし、木をスタックなどとして使ってはいけないのであれば、どの使い方が「他のどのデータ構造にもない使い方」といえるのか判断が難しいでしょう。 「木以外のデータ構造を使わない」という条件だけではあまり意味がない条件だと思えます。もう少し厳密な条件があるのかもしれません。
関連するQ&A
- 行きがけ順で表示するプログラム
アルゴリズムの勉強をし始めたものです。 深さ優先探索で 0 ／ ＼ 1 2 ／＼ ／＼ 3 4 5 6 ／＼ 8 9 の木を行きがけ順で表示（0,1,3,4,2,5,8,9,6）するC言語のプログラムを作っています。参考書を見ながら途中まで作ってみました /* 行きがけ順で表示するプログラム */ /* 配列のデータが9個と決まっている場合 */ #include <stdio.h> #define N 100 struct cell { int node; struct cell *next; }; void preorder(int n, struct cell **S);/* 前順 */ int main() { struct cell *S[N]; int root; preorder(root, S); } void preorder(int n, struct cell **S)/* 前順 */ { struct cell *q; printf("%d", n);/* 表示 */ q = S[n]; while(q != NULL) { preorder(q -> node, S);/* 再帰 */ q = q -> next; } return; } ここから例えば配列のデータが1,3,5,7,9,11,13,15,17と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか？参考書を見てもアルゴリズムの部分しか書かれていなかったので完成形が見えてこないです。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 探索アルゴリズムの名称について
以下の探索もしくは組み合わせのアルゴリズムに名称があるのかを教えていただければ幸いです． ある変数a1,a2,a3・・・，b1,b2,b3・・・があり（それぞれ小さい順にソートされている）， このaとbにより影響する評価関数が最小となる最適な組を探索するアルゴリズムです． (1)まずa1・b1のペアを用いた時の値を算出する． (2)次にa2・b1のペアとa1・b2のペアでの値をそれぞれ算出し，小さい方を見つける． （今回はa1・b2のペアの方が小さかったとします．） (3)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し，小さい方を見つける． (2)，(3)の様な処理を繰り返し行い，最小となるa・bの組を探索する． 以上の様なアルゴリズムなのですが，名称があるのかをお聞きしたいと思います． 言葉で書くとイメージしづらいですが，小学・中学ぐらいで勉強した最短経路問題のように 格子状の図を書くと分かりやすいと思います． 二方向のみをみて探索していきます． 個人的には，二分木探索に近いと思うのですがどうでしょうか？ ただ，進み方によっては，同じ組み合わせを探索する事も出来るので， 完全な二分木探索ではないような気がします． 皆様のお力をお貸しいただければありがたいです． お願いいたします．
- 締切済み
- 数学・算数
- 木構造の前置形と行きがけ順について
はじめまして。今データ構造とアルゴリズムを勉強しているのですが、前置形でつまずいてしまいました。以下の問題を解くのですが、いまいち自分で出した答えに自身がないのです。 問題 式((a+b)+c*(d+e)+f)*(g+h)を前置形に変換せよ。 自分は、与えられた式を元に木を再現して、それから行きがけ順に並べたのですが。自信がないところは、ずばり、最初の項で和が３つあるところなんです。考え方の一つとして、枝分かれを３つという考え（すなわち、*++ab*c+def+gh）と、３つを一つの和ともう２つの和と分けて考える（すなわち*++ab+*c+def+gh）のと、どちらが正解なのでしょうか？といいますのも、defのところで、今度は逆に前置形からもとの式を作り直すときに違う式ができるのでは、と思うからです。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- B木のプログラムについて
Javaアプレットで学ぶデータ構造とアルゴリズムを勉強中です。 「B木プログラムを作ってみよう」という演習問題なのですが、簡単がプログラムを教えていただけないでしょうか。 宜しくお願いいたします。
- 締切済み
- Java
- 木構造（位相構造）を比較するアルゴリズムって？
木構造（位相構造）を2つ用意し、根からたどって比較してゆき、 差分をとるようなプログラムを書こうと思っています。 しかしアルゴリズムがまったくわからないので質問させていただきます。 子ノードの順番が異なる場合も同じものと見なすような条件で、 末端にノードが追加された程度の差異がわかればよいです。 （鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。） このようなアルゴリズムというのはあるのでしょうか？
- ベストアンサー
- 数学・算数
- 2分木と双方向線形リストを同時に実現する方法
ファイルに書かれている文字列を読み込み， (1)ソートしてファイル出力 (2)読み込んだ順と逆順にファイル出力 というプログラムを作成する場合， (1)は２分木のデータ構造を用いて実現したのですが，２分木のデータ構造をそのまま利用することで逆順に出力させることは可能でしょうか？ 私は無理だと思うので，２分木に加えて双方向の線形リストになるようにポインタを設定する必要があると考えているのですが，もっと上手く実現するアルゴリズムはあるでしょうか？ アドバイスを頂けるとありがたいです．
- ベストアンサー
- C・C++・C#
- データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。
データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 データ構造とアルゴリズムについて学習しています。 （質問事項） ・データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 詳細に教えて頂けると大変助かります。 （私の現状） たとえば、データ構造は、単純なものでは、配列やコレクション、２分木などの構造で、アルゴリズムは２分木探索の実装方法だと思っています。 データ構造とアルゴリズムについては初心者です。 （現在、就職活動中で、これらを学ぶ必要がありご質問させて頂いています） どうか、皆様、教えて頂いた情報を最大限に活用させていただきますので、（皆様にとってはくだらない質問かもしれませんが…）どうぞよろしくお願いいたします。
- 締切済み
- その他([技術者向] コンピューター)
- データ構造とアルゴリズムの問題が分かりません。
データ構造とアルゴリズムの問題が分かりません。 以下の問題で悩んでいます。 索引は書籍中の単語が書籍の何ページ目に出現するかを表す。もちろん、索引に含まれるある単語が複数のページに出現する場合や、索引に含まれる複数の単語が同一のページに出現する場合もある。 この索引で対象とする単語は、その書籍の中で重要な意味をもつものとして、また、特定の単語はたかだか数ページにのみ出現すると仮定する。 （1）単方向リストを用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （2）単方向リストを用いてデータ構造の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （3）二分探索木を用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （4）二分探索木を用いたデータ構の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （5）二分探索木を用いたデータ構の場合、アルファベット順の索引を出力するたねには、どのような整列アルゴリズムを適用すれば適切か、整列に必要な時間計算量とともに示しなさい。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- 締切済み
- 科学
- 二分探索アルゴリズムの終了条件について
いつもお世話になっています。 現在他人のプログラムを読解する力をつけようと 訓練しています。 以下の文はとあるアルゴリズム本の２分探索の個所を 抜粋したものです。 int bs(*array, size, mokuteki) { ue=size-1, sita=0; while(1){ naka=(sita+ue) / 2; if(array[naka] == mokuteki) return ARU; else if(sita > ue) //・・・・・・★ return NAI; else { if(array[naka] < mokuteki) sita = naka+1; else ue = naka-1; } } } ここで★部分の終了条件なのですが、なぜ sita >= ue でいけないのか自分では理解できません。 要はsitaとueが同じ値になり、目的値が見つからなかった のに再度ループする必要があるのか？、ということです。 特に明確な答えはいりませんがぜひ ご意見を聞かせてください。 ちなみに作者は 「ue==sitaの状態ならば、幅１の範囲がありますから ループをもう一回実行する必要があります。」 と書いています。私には理解できません。 ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」 という本です。だいたい一通り読みましたが読んでて 楽しいしわかりやすいし良書だと思います。高価ですが・・・。
- ベストアンサー
- その他（プログラミング・開発）
お礼
すみません。誤字がありました。 ＞Javaで書く以上は、少なくともスタックは使っていると思ってください。その時点でこの条件が達成できるか怪しくなります。 そうですよね。自分でも確かにスタックは無いと、と思います。 木の使い方も含めて、何かもう少し条件をはっきりさせないといけないですね。実はこのことを発言した張本人が、後で『木以外のデータ構造は何も使わないでは無理かも。他のデータ構造をちょっと使ってもいい』などと口走っていた気がします…。 ありがとうございました。