maketree関数の仕組み
前回紹介した二分探索木を生成する関数“maketree”のソースを追いながら、処理の仕組みを説明していきましょう。
ノードを表す構造体の定義
リスト1は、前回紹介した二分探索木を生成する関数“maketree”のソースです。_nodeは1つのノードを表す構造体で、以下のように定義されています。
typedef struct _n {
int id; /* 添字 */
int num; /* 値 */
struct _n *left; /* 左 -- 自己参照 */
struct _n *right; /* 右 -- 自己参照 */
} _node;
先頭ノードの生成と初期化
まず、先頭のノードを以下のようにして生成し、初期化します。
start = malloc(sizeof(_node));
start->id = 0;
start->num = arry[0];
start->left = NULL;
start->right = NULL;
p1 = start;
これで、左右の「枝」がNULLとなっているノードが1つ出来上がりました。続いて、残る値を先頭のノードの下にぶら下げていきます。このときforループを使い、値の数だけ“maketree”関数を呼び出します。
for (i=1; i<7; i++) {
maketree(p1, i, arry[i]);
}
3つの引数
maketree関数は以下のように宣言され、3つの引数を採ります。
void maketree(_node *p1, int id, int num)
3つの引数は以下のような意味を持っています。
構造体_node型のp1 ---- 親のノード
int型のid ------------ 子ノードの添字
int型のnum ----------- 子ノードの値
値の比較と子ノードの生成
ノードの枝を次々と追っていくために、_node型のポインタを用意します。
_node *p2;
引数で受け取った親ノードの値(p1->num)と子ノードの値(num)との大小を比較し、子ノードの値の方が小さければ左、大きければ右へノードを割り振ります。
このとき、割り振り先（左または右）がNULLであれば新たなノードを生成して親のノードの左(p1->left)または右(p1->right)にそれへのポインタを代入します。
NULLでなければそこには既に値を持ったノード（孫ノード）が存在することになるので、その孫ノードを親ノードとしてmaketree関数――自分自身を呼び出します。
if (p1->num <= num) { ----------- 親ノードの値より子ノードの値が大きいとき
if (p1->right == NULL) { ------ 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); ---- 右のノードを親として再帰呼び出し
}
：
（左ノードの処理は省略）
Cの関数呼び出しとスタック
このように、探索木の左へ左へあるいは右へ右へと進んでいくような処理では、値の判断とその結果によるメモリの確保など、階層をたどって同じ処理を何度も実行することになります。
そのような場合に、一定の処理を実行する関数の中で自分自身を呼び出す再帰が役立ちます。
再帰は、機能ごとに関数を作ってそれを呼び出す手続き型言語の便利な機能です。関数はアドレスを持ち、関数を呼び出す際にはそのアドレスに制御を移します。その際、関数に渡す引数と呼び出した後に戻る場所のアドレスが、スタックと呼ばれるメモリ領域に保存されます。
スタックは「先入れ後出し式」の棚――というより穴のようなもので ※1 、ある関数が最初に呼び出されるとき、戻る場所のアドレスと引数がスタックに保存されます。その関数の中で自分自身を呼び出すと、さらにその戻り場所と引数がスタックに保存されます。
スタックに値が保存されることを、（スタックに）「積む」と表現します。あたかも、棚に荷物を積んでいくようなイメージです。
なお、Cでは引数は右（終端）側から順にスタックに積まれていき、呼び出された関数は第1引数から順に引数を受け取ります。そのため、printf関数のように第1引数の文字列（printfの場合は書式指定文字列）を先に解析することで、続く引数の数を特定できるような、引数の数が可変となる関数を定義できるのです ※2 。
あくまで概念としての「穴」のイメージであって、実際にはメモリに値が保存されているに過ぎません。ただCPUのアーキテクチャとして、後から保存した値から先に読み出すことしかできないようになっているだけです。アセンブリ言語では、スタックに値を保存する命令がPUSH、スタックから値を取り出す命令がPOPです
Cがお手本にした手続き型言語のPascalでは、引数は左側（第1引数）から順にスタックに積まれるため、第1引数を解析して続く引数の数を知る――といった処理は行えません
関数からの戻り先
実行される機械語の命令はまったく同じものですが、2番目に呼び出された関数の処理が終わると、後から保存された戻り先のアドレスに制御が移ります。
それは、自分自身が自分自身を再帰的に呼び出した場所の次の位置です。そこから処理を続けて関数の最後にたどり着くと、先にスタックに積んだ戻り先のアドレスに制御が移る……という具合です。
リスト1：再帰を利用して二分探索木を生成する関数～maketree（前回のリスト5）
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);
}
}
}
|
TOP