二分探索木によるプログラミング
では、二分探索木を使った探索処理をプログラムにしてみましょう。
配列を構造体に移し替える
先の図5のようなデータ構造でも、人間はそれを目で追っていくことで値を見付けることができます。しかしプログラムでは、元々の配列を木構造に組み替えることになるため、図5のように数値だけがぶら下がった状態では、最終的に見付かった値が「配列の何番目だったか」を示すことができません。
そこで、値と共にそれが元の配列の何番目だったかを示す情報を追加する必要が生じます。さらに、木構造では「左」と「右」のノードを保持する必要があります。よってこの二分探索木をプログラムで扱うには、リスト3のようなポインタによる左右2方向のリンクを持つ自己参照型の構造体を定義することになります。
リスト3：双方向リンクを持つ構造体を定義
typedef struct _n {
int id; /* 添字 */
int num; /* 値 */
struct _n *left; /* 左 -- 自己参照 */
struct _n *right; /* 右 -- 自己参照 */
} _node;
木構造を生成する
リンクを持つ構造体では、その先頭と終端を示すためにNULLを用います。二分探索木では、左右の要素が存在しなければNULLとします。
この構造体はノードが必要となるたびにmalloc関数でメモリを確保して生成することにします。構造体が生成されたときには左右のノードは未定となっているため、まずNULLを代入しておきます。そして、次の値を保持する構造体が生成されたとき、値の大小を調べて左右のポインタに振り分ける――という形で、次々と構造体をつないでいくことにします。
先頭のノードを生成して初期化する処理と、続く構造体を次々に生成して木構造を作る処理はリスト4とリスト5のようになります。
リスト4は先頭のノードを生成して初期値を代入する処理と、実際に木構造を生成する関数を呼び出す処理で、main関数内に記述します。リスト5が、実際に木構造を生成するmaketree関数で、引数には親ノード（主ノード）へのポインタ、配列の添字、値――の3つを採ります。
maketree関数では、値numが親ノードp1の値(num)より大きければ右(p1->right)へ、小さければ左(p1->left)へ値を振り分けていきます。このとき移動先がNULLであればmalloc関数で新たな構造体を生成してそこへノードを追加し、そうでなければそこには既にノードが存在しているので、そのノードを親ノードにして自分自身(maketree関数）を再帰的に呼び出します。
リスト4：ノードの初期化と二分探索木の生成
/* 先頭のノードを初期化 */
start = malloc(sizeof(_node));
start->id = 0;
start->num = arry[0];
start->left = NULL;
start->right = NULL;
p1 = start;
/* 残る値から木構造を生成 */
for (i=1; i<7; i++) {
maketree(p1, i, arry[i]); -- リスト5の関数を呼び出す
}
リスト5：再起を利用して二分探索木を生成する関数～maketree
void maketree(_node *p1, int id, int num)
{
_node *p2;
/* 値の大小によって左右に振り分ける */
if (p1->num <= num) { /* 主ノードより大きいとき */
/* 右がNULLならそこに新たなノードをぶら下げる */
if (p1->right == NULL) {
p2 = malloc(sizeof(_node));
p2->id = id;
p2->num = num;
p2->left = NULL;
p2->right = NULL;
p1->right = p2;
} else { /* NULLでなければ右側のノードに移動 */
maketree(p1->right, id, num);
}
} else {
/* 左がNULLならそこに新たなノードをぶら下げる */
if (p1->left == NULL) {
p2 = malloc(sizeof(_node));
p2->id = id;
p2->num = num;
p2->left = NULL;
p2->right = NULL;
p1->left = p2;
} else { /* NULLでなければ左側のノードに移動 */
maketree(p1->left, id, num);
}
}
}
木構造をたどって値を見付ける
こうして生成された二分探索木から特定の値（探索値）を見付ける処理は、以下のような手順となります。
先頭のノードから始める
探索値とノードの値が等しければ → 探索終了
そうでなく
探索値の方がノードの値より小さければ → 左のノードへ移動
探索値の方がノードの値より大きければ → 右のノードへ移動
移動先のノードで……
探索値とノードの値が等しければ → 探索終了
そうでなく
探索値の方がノードの値より小さければ → 左のノードへ移動
探索値の方がノードの値より大きければ → 右のノードへ移動
：
この処理をノードの値がNULLになるまで繰り返す
whileループで比較を繰り返す
このような処理には、移動先のノードがNULLになるまで繰り返すwhileループが適しています。探索値をint型のnという変数に保持するとすれば、木構造をたどって探索する処理はリスト6のようになります。
この処理はsearch関数という名前で、make関数から呼び出します。引数には先頭のノードへのポインタと探索値を採ります。
これらをすべてまとめた最終的なプログラムex5203.cはリスト7のようになります。
リスト6：木構造をたどって値を探索する関数～search
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);
}
リスト7：二分探索木によって値を探索するプログラム～ex5203.c
#include <stdio.h>
#include <stdlib.h>
/* ノードの構造体 */
typedef struct _n {
int id; /* 添字 */
int num; /* 値 */
struct _n *left; /* 左 -- 自己参照 */
struct _n *right; /* 右 -- 自己参照 */
} _node;
/* 探索先の配列 */
int arry[] = {3, 6, 2, 7, 1, 4, 8};
/* 配列の値を表示 */
void showarray(void)
{
int i;
printf("探索先 :");
for (i=0; i<7; i++) {
printf("%d ", arry[i]);
}
printf("¥n");
}
/* 二分探索木の生成 -- 再帰を利用*/
void maketree(_node *p1, int id, int num)
{
_node *p2;
/* 値の大小によって左右に振り分ける */
if (p1->num <= num) { /* 主ノードより大きいとき */
/* 右がNULLならそこに新たなノードをぶら下げる */
if (p1->right == NULL) {
p2 = malloc(sizeof(_node));
p2->id = id;
p2->num = num;
p2->left = NULL;
p2->right = NULL;
p1->right = p2;
} else { /* NULLでなければ右側のノードに移動 */
maketree(p1->right, id, num);
}
} else {
/* 左がNULLならそこに新たなノードをぶら下げる */
if (p1->left == NULL) {
p2 = malloc(sizeof(_node));
p2->id = id;
p2->num = num;
p2->left = NULL;
p2->right = NULL;
p1->left = p2;
} else { /* NULLでなければ左側のノードに移動 */
maketree(p1->left, id, num);
}
}
}
/* 木構造をたどって探索 */
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);
}
/* ---------------------------------------------
main
---------------------------------------------- */
int main(void)
{
_node *start, *p1;
int i, n;
/* 配列の値を表示 */
showarray();
/* 探索する値を入力 */
printf("input number : ");
scanf("%d", &n);
printf("¥n");
/* 先頭のノードを初期化 */
start = malloc(sizeof(_node));
start->id = 0;
start->num = arry[0];
start->left = NULL;
start->right = NULL;
p1 = start;
/* 残る値から木構造を生成 */
for (i=1; i<7; i++) {
maketree(p1, i, arry[i]);
}
/* 木構造をたどって探索 */
return (search(p1, n));
}
＊
これで、ひととおりの処理が出来上がりました。最終的にはmalloc関数で生成した構造体の木構造をたどって、free関数でメモリを解放する処理が必要です。しかし、今回のテーマである『値の探索』という目的とは異なるため、今回はメモリの解放処理については割愛します。
|
|
|
TOP