二分木を実装する（C言語）

データ構造の一つである二分木を実装してみます。

データ探索

データを単純に配列に入れておくと、例えば、



のようになる。この中にあるデータを探索しようとすると、データ個数がNの場合は、最大N回の比較をしなければならない。

二分木は、



のようなデータ構造をとり、探索する値がノード（節点）の値より小さければ左側のノードへ、大きければ右側のノードへと経路を辿っていくことで、線形検索よりも短い時間で検索ができる。左右に均等に二分された木構造になっていれば、最大logN回の比較で検索が終わる。

データ構造

二分木の各ノード(節点）は、要素の値と子のノードへのポインタを持つ。左、右の子のノードへのポインタを配列にして、配列の添え字で左右を表すようにしているので、左右を表す変数を使うと、nodeの子が左右それぞれの場合でコードを分けずに、共用のコードで書くことができる。

typedef struct Node {
  int item;
  struct Node* lr[2];
} NODE;

このノードを連結させて木構造を作る。

ノードの作成

新しいノードを作成するには、ノードのためのメモリ領域を確保し、要素の値、子のノードへのポインタを設定して、作成したノードのポインタを戻り値として返す。新しいノードなので、子は存在しないため、子のノードへのポインタ（node->lr[]）はNULLになる。

NODE* node_create(int x) {
  NODE *node = malloc(sizeof(NODE));
  node->item = x;
  node->lr[0] = NULL;
  node->lr[1] = NULL;
  return node;
}

ノードの挿入

木に新たにノードを挿入する場合は、新しいノードを作成することになるが、二分木の構造として適切な場所を見つける必要がある。

二分木の根ノード（引数にポインタが渡される）から、格納する要素の値がノードのitemの値より小さければ左（node->lor[0]）、大きければ右（node->lr[1]）の子ノードの経路を辿っていく。ノードがNULL（まだ存在しない）ところまで進み、そこに新しいノードを作成する。
新しいノードまで、再帰呼び出しで経路を辿っているので、新しいノードを作成したらそのノードのポインタを呼び出し元に返していく。再帰呼び出しを戻っていくので、新しく作成されたノードを含む根ノードが得られ、その根ノードのポインタを戻り値として返している。

NODE *node_insert(NODE *node, int x) {
  if (node == NULL) {
    return node_create(x);
  }
  int lr = (x < node->item) ? 0 : 1;
  node->lr[lr] = node_insert(node->lr[lr], x);
  return node;
}

ノードの検索

木の中にデータがあるかどうかを検索して、あればそのノードのポインタ、なければNULLを返す。ノードのitemと検索するデータを比較して、一致すればそのノードのポインタを返す。なければ、データがノードのitemよりちいさければnodeをnode->lr[0]に、大きければnode->lr[1]に変更して、nodeがNULLにならない限り繰り返す。

NODE *node_find(NODE *node, int x) {
  while (node != NULL) {
    if (x == node->item) {
      return node;
    }
    int lr = (x < node->item) ? 0 : 1;
    node = node->lr[lr];
  }
  return NULL;
}

ノードの削除

引数で与えられた値を持つノードを削除する。そのノードが末端のノードならば、そのまま削除すればいい。末端でないノードの場合は、削除するノードの要素の値に最も近い値を持つノードを見つけて、その値で削除するノードの要素を書き換え、書き換えた要素を持つノードを削除する。

削除するノードに最も近い値を持つノードは、値が小さい側と大きい側それぞれ一つずつあるので、どちらを用いるか決めておけばいい。値が小さい側で最も近い値を持つノードは、削除するノードの左側の子ノードの中で、最も右側にあるノード（右側の子ノードがなくなる位置のノード）である。このノードの値を削除するノードの位置においても、二分木構造におけるノードの値の大小関係は維持されることが分かる。



値が大きい側で最も近い値を持つノードは、反対側、削除するノードの右側の子ノードの中で、最も左側にあるノード（左側の子ノードがなくなる位置のノード）になる。削除するノードの値を、左右どちら側の子ノードの中の最も近い値で置き換えても、二分木構造におけるノードの値の大小関係が維持されることが分かる。



以下の実装では、左側の子ノードの中で、最も右側のノードの値を用いている.

NODE *node_remove(NODE *node, int x) {
  if (x == node->item) {
    free(node);
    return NULL;
  }
  int lr = (x < node->item) ? 0 : 1;
  node->lr[lr] = node_remove(node->lr[lr], x);
  return NULL;
}

二分木の表示

二分木構造の各ノードの要素の値を、木構造における各ノードの高さの表現（インデントで表現）と併せて表示している。二分木を使用する用途で、二分木のデータ構造を表示する必要性はないと思うが、コードの動作確認などで、各ノードが木構造のどこに配置されているかを確認するのに利用できると思う。

void node_print(NODE *node, int depth) {
  if (node == NULL) {
    return;
  }
  node_print(node->lr[1], depth + 1);   /* print left nodes */
  for (int i = 0; i < depth; i++) {     /* print spaced of depth */
    printf(" ");
  }
  printf("%d\n", node->item);           /* print node */
  node_print(node->lr[0], depth + 1);   /* print right nodes */
  return;
}

例えば、ページの最初のデータの木構造の場合は、

  89
    88
   72
    71
 70
   64
  59
   53
49
  33
   27
 14
   13
  10
   1

のように表示される。

使い方

二分木のノードの宣言、二分木へのデータの挿入、削除、検索は、以下のように行う。

  NODE *node = NULL;

  int x;
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    nmode = node_insert(node, x);
  }

  scanf("%d", &x);
  NODE *t = node_find(node, x);
  if (t != NULL) {
    printf("%d\n", t->item);
  } else {
    printf("not found\n");
  }

  scanf("%d", &x);
  node = node_remode(node, x);

  node_print(node);