現在、 ALDS1_8_Aを行っています。2分探索木です。
解答コードは、以下のような形です。
insert関数の中で、x
を現在の比べるノード,y
を親のノード,z
を挿入するノード
として考えていると思うのですが、xに対して初期値のroot
ポインタを入れている挙動が分かりません。
具体的には、While文の条件文です。
x
がNil
ではない条件だと思うのですが、そもそもxに最初からNil
なんて入っているのでしょうか?
xに入っている初期の値は、Nilではなくroot
だと思います。
root
は、Nodeポインタ型だと思うのですが、root
はNil
ではないと思います。
C/C++では、変数は定義したが実際にはその中に値が入っていない場合はNil
となるのでしょうか?
ご教授よろしくお願い致します。
struct Node {
int key;
Node *right, *left;
};
Node *root, *NIL;
void insert(int k) {
Node *y = NIL;
Node *x = root;
Node *z;
z = (Node *)malloc(sizeof(Node));
z->key = k;
z->left = NIL;
z->right = NIL;
while ( x != NIL ) {
y = x;
if ( z->key < x->key )
x = x->left;
else
x = x->right;
}
if ( y == NIL ) {
root = z;
} else {
if ( z->key < y->key )
y->left = z;
else
y->right = z;
}
}