《仮定》 各ノードに格納されたデータ要素は互いに相異なる。
この授業では、この仮定をもとにプログラムを作成していく。
例えば、データ要素の追加処理では、追加対象のデータ要素がすでに二分探索木に格納されているときには何もせずに終了する、といった処理を行う。この仮定を忘れないで欲しい。
【参考】
struct node {
int value; /* データ要素 */
struct node * left; /* 左側の子供へのポインタ */
struct node * right; /* 右側の子供へのポインタ */
};
参考までに、自己参照構造体を使った二分探索木のイメージを示す。
これは、上で抽象的に示した二分探索木の具体例と同じものである。なお、この図には、「二分探索木を指すポインタ変数」（次節参照）も示している。
int main(void){
struct node * root; /* 二分探索木（の根）を指すポインタ変数 */
... 二分探索木に関する適当な処理 ...
return 0;
}
【仮引数 rt 】
連結リストの場合と同様に、初期設定関数、追加関数、削除関数では、ポインタ変数rootに対して「ポインタ変数のポインタ渡し」を使用する。そこで、各関数の仮引数宣言のところでは、rootを短縮した「rt」という仮引数名を使用する。「rt」という仮引数を見たら、「ポインタ変数rootに対してポインタ変数のポインタ渡しを行っている」と解釈して欲しい。
void init( struct node * * rt ){
*rt = NULL;
}
【初期設定関数の呼び出し】
int main(void){
struct node * root; /* 二分探索木（の根）を指すポインタ変数 */
init(&root); /* 二分探索木の初期設定 */
... 二分探索木に関する適当な処理 ...
return 0;
}
| *rt | … |
二分探索木（の根）へのポインタ root。（注）ポインタ渡しを使用する。従って、仮引数rtの値は変数rootへのポインタになっている。
|
| val | … |
新たなデータ要素（追加対象の値）。
|
(1) |
新たなノードを生成する。 |
(2) |
新たなノードにデータ要素valを設定する。 |
(3) |
新たなノードの自己参照メンバ（leftとright）にNULLを設定する。 |
(4) |
ポインタ変数rootに新たなノードへのポインタを代入する（注：ポインタ渡しを使用する）。
|
(B) |
二分探索木が空でなかったとき、valを登録すべき位置を求めなければならない。
これは、大まかに言って、次のような処理を用いて求めることができる。
|
(0) |
作業用ポインタ変数の宣言 次の二つのポインタ変数（struct node*型）を用意する。 |
| current | … |
二分探索木の中を降りて行く途中のノード（以下では、「比較対象ノード」と呼ぶ）へのポインタを保持する。
|
| parent | … |
比較対象ノードの親ノード（一つ前の比較対象ノード）へのポインタを保持する。
|
(1) |
currentの初期設定 まず、currentに「二分探索木の根」へのポインタを初期設定する。 |
(2) |
追加場所の探索処理 次に、currentがNULLになるまで（言い換えると、比較対象ノードがなくなるまで）か、または、valがすでに格納されていることが分かるまで、次の処理を繰り返す。 （⇒⇒⇒このステップの動作例） |
(*) |
valと比較対象ノードのデータ要素valueを比較し、その比較結果に応じて次のように処理する。
|
|
(a) |
val＝valueのとき、valがすでに格納されていたことが分かるので、何もせずに終了する。
|
|
(b) |
val＜valueのとき、比較対象ノードの左部分木のどこかにvalを格納しなければならない。そこで、現在の比較対象ノードの左側へ降りて行く。具体的には、次を実行する。
|
|
(c) |
val＞valueのとき、比較対象ノードの右部分木のどこかにvalを格納しなければならない。そこで、現在の比較対象ノードの右側へ降りて行く。具体的には、次を実行する。
|
(3) |
新たなデータ要素valの登録 以上の繰り返し処理を行っている間に、いつかはcurrentの値がNULLになる。NULLになった時点で val を登録すべき位置が確定している。その位置とは、最後の比較対象ノード（注：parentが指しているノード）の「左側の子供（の位置）」かまたは「右側の子供（の位置）」である。どちら側に登録すべきかは、valと最後の比較対象ノードのデータ要素を比較することによって決めることができる。そこで、次のように処理する。 （⇒⇒⇒このステップの動作例） |
(a) |
まず、新たなノードを生成して、そのデータ要素メンバにvalを設定し、自己参照メンバにNULLを設定する。
|
|
(b) |
次に、追加対象のデータ要素valとparentが指しているノードのデータ要素valueを比較する。
|
|
(c) |
val＜valueのとき、新たなノードを、parentが指しているノードの左側の子供として登録する。
|
|
(d) |
val＞valueのとき、新たなノードを、parentが指しているノードの右側の子供として登録する。
|
void add( struct node * * rt, int val ){
struct node * current, * parent, * new_node;
/* (A) 二分探索木が空だったとき */
if( *rt == NULL ){
new_node = malloc(sizeof(struct node)); /* (1) */
new_node->value = val; /* (2) */
new_node->left = NULL; /* (3) */
new_node->right = NULL;
*rt = new_node; /* (4) */
return; /* 終了 */
}
/* (B) 二分探索木が空でなかったとき */
current = *rt; /* (1) */
while( current != NULL ){ /* (2) */
if( val == current->value ){ return; } /* (2)(a) */
if( val < current->value ){ /* (2)(c) */
parent = current;
current = current->left;
} else { /* (2)(d) */
parent = current;
current = current->right;
}
}
/* (B)(3) valの登録 */
new_node = malloc(sizeof(struct node)); /* (3)(a) */
new_node->value = val;
new_node->left = NULL;
new_node->right = NULL;
if( val < parent->value ){ /* (3)(b) */
parent->left = new_node;
} else { /* (3)(c) */
parent->right = new_node;
}
}
| root | … |
二分探索木（の根）へのポインタ root。（注）ポインタ渡しは使用しない。
|
| val | … |
検索対象のデータ要素（いまの場合、整数値）。
|
(0) |
作業用ポインタ変数の宣言 次のポインタ変数（struct node*型）を用意する。 |
| current | … |
二分探索木の中を降りて行く途中のノード（比較対象ノード）へのポインタを保持する。
|
(1) |
currentの初期設定 まず、currentに「二分探索木の根」へのポインタを初期設定する。 |
(2) |
探索処理 次に、currentがNULLになるまで（言い換えると、比較対象ノードがなくなるまで）か、または、valがすでに登録されていることが分かるまで、次の処理を繰り返す。 （⇒⇒⇒このステップの動作例[1]、 ⇒⇒⇒このステップの動作例[2]） |
(*) |
valと比較対象ノードのデータ要素valueを比較し、その比較結果に応じて次のように処理する。
|
|
(a) |
val＝valueのとき、currentを戻り値として返す（終了）。
|
|
(b) |
val＜valueのとき、現在の比較対象ノードの左側へ降りていく。具体的には、次を実行する。
|
|
(c) |
val＞valueのとき、現在の比較対象ノードの右側へ降りて行く。具体的には、次を実行する。
|
(3) |
currentがNULLになったとき currentがNULLとなって上記の繰り返し処理が完了したら、 それはvalを保持したノードが存在しないことを示している。 そこで、NULLを戻り値として返す（終了）。 |
struct node * search( struct node * root, int val ){
struct node * current;
current = root; /* (1) */
while( current != NULL ){ /* (2) */
if( val == current->value ){ return current; } /* (2)(a) */
if( val < current->value ){ /* (2)(b) */
current = current->left;
} else { /* (2)(c) */
current = current->right;
}
}
return NULL; /* (3) */
}
/**********************************************************************
* ヘッダファイル
**********************************************************************/
#include <stddef.h> /*-- NULL , size_t --*/
#include <stdio.h> /*-- printf関数 --*/
#include <stdlib.h> /*-- malloc関数 --*/
/**********************************************************************
* 二分探索木のノードを表す自己参照構造体
**********************************************************************/
struct node {
int value; /*-- データ要素 --*/
struct node * left; /*-- 左側の子供へのポインタ --*/
struct node * right; /*-- 右側の子供へのポインタ --*/
};
/**********************************************************************
* 基本操作関数（プロトタイプ宣言）
**********************************************************************/
void init( struct node * * rt ); /*-- 初期設定 --*/
void add( struct node * * rt, int val ); /*-- 追加 --*/
struct node* search( struct node * root, int val ); /*-- 検索 --*/
/**********************************************************************
* main関数
* 以下では、配列Aに格納された正整数（最後の-1を除く）を二分探索木に登録し、
* 検索関数を利用することによって二分探索木の内容を表示している。
* なお、配列Aの最後に格納されている -1 は、登録対象の整数列の終わりを
* 示すための目印である。
* （このような、「終わり」を表す目印を総称して「番兵」と呼ぶ。）
**********************************************************************/
int main(void){
int A[] = { 29, 13, 5, 19, 15, 47, 35, 33, 40, 51, 65, -1 };
int i;
struct node * root; /* 二分探索木（の根）を指すポインタ変数 */
struct node * p; /* 作業用変数 */
/*-★ 二分探索木の初期設定 --*/
init( &root );
/*-★ 各A[i]を二分探索木に追加する --*/
i = 0;
while( A[i] > 0 ){
add( &root, A[i] );
i++;
}
/*-★ 二分探索木の根へのポインタを表示 --*/
printf("root=%p\n", root);
/*-★ 各A[i]を検索して、A[i]を保持するノードの内容を表示する --*/
i = 0;
while( A[i] > 0 ){
p = search( root, A[i] );
printf("%p:[%d;%p,%p]\n", p, p->value, p->left, p->right);
i++;
}
return 0;
}
/**********************************************************************
* 基本操作関数（関数本体の定義）
**********************************************************************/
/*-★ 初期設定関数 --*/
void init( struct node * * rt ){
*rt = NULL;
}
/*-★ 追加関数（データ要素を追加する） --*/
void add( struct node * * rt, int val ){
struct node * current, * parent, * new_node;
/* (A) 二分探索木が空だったとき */
if( *rt == NULL ){
new_node = malloc(sizeof(struct node)); /* (1) */
new_node->value = val; /* (2) */
new_node->left = NULL; /* (3) */
new_node->right = NULL;
*rt = new_node; /* (4) */
return; /* 終了 */
}
/* (B) 二分探索木が空でなかったとき */
current = *rt; /* (1) */
while( current != NULL ){ /* (2) */
if( val == current->value ){ return; } /* (2)(a) */
if( val < current->value ){ /* (2)(c) */
parent = current;
current = current->left;
} else { /* (2)(d) */
parent = current;
current = current->right;
}
}
/* (B)(3) valの登録 */
new_node = malloc(sizeof(struct node)); /* (3)(a) */
new_node->value = val;
new_node->left = NULL;
new_node->right = NULL;
if( val < parent->value ){
parent->left = new_node; /* (3)(b) */
} else {
parent->right = new_node; /* (3)(c) */
}
}
/*-★ 検索関数（データ要素を検索する） --*/
struct node * search( struct node * root, int val ){
struct node * current;
current = root;
while( current != NULL ){
if( val == current->value ){ return current; }
if( val < current->value ){
current = current->left;
} else {
current = current->right;
}
}
return NULL;
}
（出力結果）
root=0x804a050 0x804a050:[29;0x804a060,0x804a0a0] 0x804a060:[13;0x804a070,0x804a080] 0x804a070:[5;(nil),(nil)] 0x804a080:[19;0x804a090,(nil)] 0x804a090:[15;(nil),(nil)] 0x804a0a0:[47;0x804a0b0,0x804a0e0] 0x804a0b0:[35;0x804a0c0,0x804a0d0] 0x804a0c0:[33;(nil),(nil)] 0x804a0d0:[40;(nil),(nil)] 0x804a0e0:[51;(nil),0x804a0f0] 0x804a0f0:[65;(nil),(nil)]【問題】 A[0]を追加した直後の二分探索木、A[1]を追加した直後の二分探索木、A[2]を追加した直後の二分探索木、... のそれぞれの図を示せ。 【補足】 二分探索木の内容表示関数やメモリ解放関数は、二分探索木の走査（トラバーサル）を学習するときに解説する。現時点では、各データ要素を検索することによって各ノードの内容を表示して欲しい。また、メモリ領域を解放する必要もない。
/*-★ 各A[i]を二分探索木に追加する --*/
i = 0;
while( A[i] > 0 ){
add( &root, A[i] );
A[i]を追加した直後の二分探索木の内容を表示する
i++;
}
内容表示の仕方は前節のプログラムを参照せよ。
【問題２】
整数列を格納したint型の配列A=A[0], A[1], ..., A[n-1]が与えられたとき、
A[0]〜A[n-1]をすべて登録した二分探索木を構築して、
その二分探索木へのポインタを戻り値として返す関数を作成せよ。
関数名をarray_to_treeにすること。
【問題３】
次の要件を満たす関数を作成せよ。関数名を delete_leaf にすること。