1

現在、 ALDS1_8_Aを行っています。2分探索木です。

解答コードは、以下のような形です。

insert関数の中で、xを現在の比べるノード,yを親のノード,zを挿入するノード
として考えていると思うのですが、xに対して初期値のrootポインタを入れている挙動が分かりません。
具体的には、While文の条件文です。
xNilではない条件だと思うのですが、そもそもxに最初からNilなんて入っているのでしょうか?
xに入っている初期の値は、Nilではなくrootだと思います。
rootは、Nodeポインタ型だと思うのですが、rootNilではないと思います。
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;
  }
}

1 件の回答 1

4
Node *root, *NIL;

rootNIL はグローバル変数なので、初期値は 0 になります。よって、ローカル変数 xy も初期値は 0 です。NIL との比較は 0 と比較していることになります。


C言語のまともなコードなら、NIL という変数は作らずに NULL を使うのが普通でしょう。C++のまともなコードなら、NIL という変数は作らずに nullptr を使うのが普通でしょう。

4
  • int32_t様 ご回答ありがとうございます。 rootNIL は、Node 型のグローバル変数なのに初期値は0なのでしょうか? もしこれらが、int型であったら初期値が0ということはわかるのですが、構造体やクラスであっても、イニシャライズしていなかったら初期値は0なのでしょうか? ご教授よろしくお願い致します。 Commented 2023年1月9日 12:44
  • 構造体でも全フィールドが0です。この場合はNode型ではなくNode*型なので、0のポインタ値です。
    – int32_t
    Commented 2023年1月9日 13:38
  • グローバル(静的)の場合に限り各フィールドの初期値 0 なことには注意してね。局所変数 (自動変数) の初期値は不定であって 0 とは限らないです。またフィールドの初期値 0 をもってオブジェクトの初期化済みと考えると誤りますのでその辺も理解が必要です。この質問においては NILroot がオブジェクトではない(単なるポインタ)であることが重要。
    – 774RR
    Commented 2023年1月10日 4:19
  • 言語仕様に基づいて厳密にいうとポインタ型については 0 ではなく「空ポインタ」です。 無効 (オブジェクトや関数を指さない) なポインタであることを表すなんらかの状態であって整数の 0 との互換性は限定的です。 Commented 2023年1月18日 7:34

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。