- ベストアンサー
二分探索木
二分探索木の完全なソースコードが載っているサイトは無いでしょうか??調べてみたのですが、関数ごとに分けて書かれているものばかりで、中々見つかりません。お願いします。
- candlefire
- お礼率70% (65/92)
- C・C++・C#
- 回答数4
- ありがとう数5
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
完全とは、追加、検索、削除ですか? 多分本をみるのが一番早いとおもいます。 自分が二分探索木を勉強する時に参考にした、 URLをの乗せておきます。
その他の回答 (3)
- galoon
- ベストアンサー率28% (38/133)
枝の数(深さ)がその都度変化することを前提として考えると通常「再起」と呼ばれる技法を採用するはずですので、その関数ごとに分かれているものが完全版に当たるのではないでしょうか。(もちろん処理の都合で必要以上に関数化されているものもありますが) URLの記事が参考になるかも。
お礼
ご回答ありがとうございます。探索木の意味がよく分かりました。
- tsuna555
- ベストアンサー率53% (22/41)
関数ごとに分かれている物を、まとめればいいのでは?
- jacta
- ベストアンサー率26% (845/3158)
『C言語による最新アルゴリズム事典』に含まれていたように記憶しています。
お礼
ご回答ありがとうございます。他にも沢山役に立ちそうなソースが沢山のっていて、便利ですね。
関連するQ&A
- 二分探索木を用いての探索
C言語でプログラミングしています。 二分探索木を用いて探索するプログラムなのですが 与えられた値の前後の値(与えられた値より大きく(小さく)てその値 に一番近いもの)を見つけたいのですが分かりません。 いろいろとネット等で調べてみると「挿入してその左右を見る」 となっているのですが…。 普通の二分探索木ではだめなのでしょうか? よろしくお願いします。
- 締切済み
- C・C++・C#
- schemeで二分探索木の問題について
schemeの問題で,「二分探索木であることを判定する関数を定義せよ」という問題があります。二分探索木とは,左の部分木に含まれる値はノードの値より小さく,右は大きい二分木です。 頑張って考えたのですが,まったくわかりません。 どなたかご回答をしていただけると助かります。 よろしくお願いします。
- 締切済み
- その他(プログラミング・開発)
- 二分探索木と二分探索の違い
高校のときにCOBOLを用いた二分探索を習いました。 今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。 添付画像のような二分木があるとき、a~jの各ノードに1~10の整数のどの整数が入るか。 という問題ですが、ちんぷんかんぷんです。 二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。 もし、同じなら、1~10の中央値の5がルートになりますよね。 このような問題の簡単な求め方があれば教えてください。お願いいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 二分木探索でN番目の要素を探索するには
二分木探索で特定の要素の有無を調べる関数は作れたのですが、N番目に小さい要素を見つける方法が思い浮かびません。 二分木探索でN番目に小さい(昇順でN番目)の要素を探索するにはどのような手法があるのか教えて頂けないでしょうか? よろしくお願い致します。
- ベストアンサー
- C・C++・C#
- 二分探索は木のように例えられる?
二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか? 回答のほうよろしくお願いいたします。
- ベストアンサー
- その他(プログラミング・開発)
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため(探索経路を短くするため)、子の数を最大m個までとするm分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- 二分探索木の深さについてです。
二分探索木の深さについてです。 この画像の式4.1から4.2への変換の解説・手順。また、式4.2から4.3への変換の解説・手順。最後に4.4への変換の説明をお願いします。 できるだけ詳しく書いていただけると助かります iD(i-1)をD(n-1)を用いて表そうとかんがえたのですが、出来ません。 http://34vv.net/drg/ できないです(T_T)
- 締切済み
- 数学・算数
- 二分探索木のパターン数
二分探索木のパターン数 二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。 例えば 6 / \ 4 9 /\ / 2 5 8 / 7 こんな感じです。 http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8 で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。 というものです。図を書いて色々考えてみたのですが求め方が分かりません。 全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか?
- ベストアンサー
- 数学・算数
お礼
ご回答ありがとうございます。大変参考になりました!!