二分探索木をたどる
前回、簡単に触れた二分探索木をたどって目的の値を見付けるまでの処理を、ソースコードを踏まえながら確認してみましょう。
全体の動作
基本的な動作は以下のようになります。
- 先頭のノードから調べる
- 被探索値と先頭のノードの値とを比較する
被探索値がノードの値と同じなら→終了
被探索値がノードの値より小さければ→左のノードへ移動
大きければ→右のノードへ移動
- 移動先のノードで上記2.の処理を行う
この動作をソースにしたものがリスト2（前回のリスト6）です。順に追っていきましょう。
関数の宣言
search関数はint型の値を返し、2つの引数を採ります。
int search(_node *p, int n)
_node型のポインタpは、呼び出し側から与えられる二分探索木の先頭ノードへのポインタです。ここから子ノードをたどっていき、int型のnを探します。
戻り値は、値nが見付かれば0、見付からなければ-1としています。これはあくまでサンプルなので、値nが見付かったときには、このsearch関数内で「何番目に見付かったか」をprintf関数で表示するようにしています。
実用を考えた場合には、値nが見付かった場所（この例では配列の添字）を関数の戻り値として返す形にした方がよいでしょう。
whileループで繰り返す
引数として受け取った先頭のノード（を示すポインタ）pには、値の大小関係（引数nとpのメンバnumとの大小関係）によって、次々と右(right)または左(left)のノードを示すポインタが代入されていきます。
右または左に値が存在しないときには、rightまたはleftはNULLとなっているので、pがNULLになるまでwhileループで処理を繰り返します。
while (p != NULL) {
二分探索木を表す構造体_nodeの定義は、先に紹介したとおりです。
3段階の比較
ループ内では、以下のような3段階の比較を行います。
引数nがpのメンバnumと等しければ
→ 値の添字（メンバidの値）を表示して0を返す
if (n == p->num) {
printf("%d は %d 番目に見付かりました。¥n", n, p->id + 1);
return(0); /* 値が見付かれば終了 */
そうではなく
引数nがpのメンバnumより小さければ
→ pにpのメンバleftを代入 ―― 左のノードへ移動
else if (n <= p->num) {
p = p->left;
そうではなく
引数nがpのメンバnumより大きければ
→ pにpのメンバrightを代入 ―― 右のノードへ移動
else {
p = p->right;
}
}
見付からなかった場合の対処
こうしてループで処理を繰り返していくと、値nが探索木の中に見付かったときには、必ずループの中で処理を終えて呼び出し元に戻ります。
whileループを抜け出すのは、値nが見付からなかったときだけですから、その場合には「見付からなかった」というメッセージを表示して-1を返します。
printf("%d は見付かりませんでした。¥n", n);
return(-1);
}
リスト2：木構造をたどって値を探索する関数～search（前回のリスト6）
int search(_node *p, int n)
{
while (p != NULL) {
if (n == p->num) {
printf("%d は %d 番目に見付かりました。¥n", n, p->id + 1);
return(0); /* 値が見付かれば終了 */
} else if (n <= p->num) {
p = p->left;
} else {
p = p->right;
}
}
/* ループを抜け出たということは見付からなかったということ */
printf("%d は見付かりませんでした。¥n", n);
return(-1);
}
|
|
|
TOP