C言語で二分探索木（木構造・ツリー構造）をプログラミング

二分探索木解説ページのアイキャッチ

SHARE

このページにはプロモーションが含まれています

このページでは、データ管理を行うためのプログラムでよく用いられる「木構造」の中の「二分探索木」について解説し、そのC言語で実装したプログラムの例を紹介・解説します。

まず木構造とは

二分探索木の解説に入る前に、まずは木構造について解説します。

木構造とは木の形をしたデータ構造

木構造とは木の形をしたデータ構造になります。

木構造を木でたとえた図

実際には、この木を上下逆さまにした見た目の構造になります。

基本的な木構造の図

スポンサーリンク

ノードと枝

木構造はノード（節）と枝の２つの要素から構成されます。

図においてはノードは丸で示し、枝はノードとノードを繋ぐ線として表される事が多いです。このページでもこれに倣って木構造を表現しています。

ノードと枝の説明図

ノード

木構造においては、一般的に、ノードは管理したいデータそのものを持つ要素となります。

例えば会員メンバーの情報を管理する木構造であれば、ノードには「会員番号・名前」などのデータを格納しますし、身体測定情報を管理する木構造であれば、ノードには「名前・身長・体重」などのデータを格納します。

枝

それに対して枝はノードとノードの関係があることを示す要素です。

具体的には、この枝では、次で解説する親子関係があることを示します。

親ノードと子ノード

木構造では各ノードに親子関係があります。

あるノードとあるノードが枝で結ばれる場合、それらのノードには親子関係があります。

例えば下の図の赤いノードに注目すると、この赤いノードから枝をたどって上側にあるのが赤いノードの親ノードとなります。

逆に赤いノードから枝をたどって下側にあるのが子ノードとなります。

親ノードと子ノードの説明図

さらに、「あるノードの子ノード」の子ノードは孫ノードと呼びますし、あるノードから見た子ノード以下のノードをひっくるめて子孫ノードと呼びます。

根ノードと葉ノード

さらに木構造においては根ノードと呼ばれるノードと葉ノードと呼ばれるノードがあります。

根ノードとは親ノードがいないノードです。木構造において最上位に位置するノードになります。木構造においては一般的に一つの木構造に根ノードは１つしかありません。

葉ノードとは子ノードがいないノードです。根ノードと異なり一つの木構造に葉ノードは複数存在する事が多いです。

根ノードと葉ノードの説明図

スポンサーリンク

二分探索木とは

二分探索木とは前述した木構造の種類の中の一つのデータ構造となります。

木構造と同様にノードや親子関係・根ノードなどが存在しますが、二分探索木では特に下記のような特徴を持ちます。

子ノードは２つ以下

二分探索木においては各ノードが持つ子ノードは２つ以下のみとなります。

二分探索木の例

子ノードは左の子ノードと右の子ノードの二種類

さらに二分探索木では子ノードは「左の子ノード」と「右の子ノード」の二種類に分けられます。ノードは「左の子ノード」と「右の子ノード」それぞれ１つのみしか持つ事が出来ません。

二分探索木における左の子と右の子

スポンサーリンク

左の子・親・右の子に大小関係

さらに二分探索木においては、各ノードとそのノードの子ノードは下記の関係を持ちます（実際には一方のみ “≦” で、もう一方は “<” の関係となります。どちらを “≦” にするかは自分で決めて良いです）。

左の子ノードの値 ≦ ノードの値 ≦ 右の子ノードの値

各ノードで複数の項目のデータを管理する場合は、探索を行う項目の値に対して上式が成立すれば良いです。

例えば会員情報として「会員番号」と「名前」を管理する二分探索木の場合について言うと、「会員番号」に対して探索を行うのであれば「会員番号の値」に対して上式が成立していれば良いですし、「名前」に対して探索を行うのであれば「名前の値（アルファベット順・五十音順）」に対して上式が成立すれば良いです。

後に紹介するプログラムでは「会員番号の値」に対して上式が成立するように実装しています。

また、二分探索木では各ノードに対して上の式が成り立つので、下の式も自然と成立する事になります。

左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値

つまり、あるノードの左側にはそのノードよりも大きい値のノードは無い、さらに右側にはそのノードよりも小さい値のノードは無いと言う事です。

例えば下の図は二分探索木の例になります。

各ノードの右側（右の子孫）には、そのノード以上の値を持つノードのみ、各ノードの左側（左の子孫）には、そのノード以下の値を持つノードのみが存在することが確認できると思います。

二分探索木における子孫の大小関係を表した例

二分探索が得意なデータ構造

二分探索木は名前の通り、二分探索をしやすいデータ構造です。

「左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値」という関係がありますので、探索する値があるノードの値よりも大きいか小さいかどうかを判断し、その結果に応じて子をたどっていく（探索する値 < ノードの値であれば左の子、探索する値 > ノードの値であれば右の子をたどっていく）のを繰り返すだけでデータを探索する事が出来ます。

二分探索木での探索の例

二分探索木のプログラミング

それでは二分探索木を実現するプログラムについて考えていきましょう。

このページでは会員メンバーのデータを管理する二分探索木について考えたいと思います。

「会員番号」と「名前」の２つのデータを管理する二分探索木としてプログラムを考えていきたいと思います。また、探索を行う項目は「会員番号」とし、この「会員番号」は重複はしないものとします。

スポンサーリンク

ノードを表す構造体

まず各ノードを表す構造体について考えます。構造体の名前は struct node_t としておきます。

ノードと枝で解説した通り、ノードは管理するデータそのものを持ちます。ですので、「会員番号」と「名前」を格納するメンバが必要です。

データそのものを格納するメンバ 
int number;
char name[256];

さらに、子ノードは左の子ノードと右の子ノード解説した通り、二分探索木のノードは左の子ノードと右の子ノードを持ちますので、これらを指すために２つのポインタもメンバに必要です。

他のノードを指すメンバ 
struct node_t *left;
struct node_t *right;

構造体が自身の構造体を指しているところがポイントです。

ただし、ノードは左の子ノードや右の子ノードを持っているとは限りません。子ノードがいない場合は、NULL を指す事で、左の子ノード・右の子ノードを持っていないこと示すようにします。

総合すると、二分探索木において、ノードを表現する構造体は下記のようになります。

ノードを表現する構造体 
struct node_t {
  int number;
  char name[256];
  struct node_t *left;
  struct node_t *right;
};

単なるデータですが、ポインタでその子ノードとなるデータを繋ぐことで、木のように表現しています。例えば下の図のような二分探索木（名前については図から省略）であれば、

二分探索木のノードを表す構造体の説明図

各ノードの構造体の値の例はそれぞれ下記のようになります（name はてきとうに設定しています）。

  • 会員番号 100 のノード
    • number：100
    • name：AAA
    • left：会員番号 50 のノードのアドレス
    • right：会員番号 200 のノードのアドレス
  • 会員番号 50 のノード
    • number：50
    • name：BBB
    • left：会員番号 30 のノードのアドレス
    • right：会員番号 70 のノードのアドレス
  • 会員番号 30 のノード
    • number：30
    • name：CCC
    • left：NULL
    • right：NULL
  • 会員番号 200 のノード
    • number：200
    • name：DDD
    • left：NULL
    • right：会員番号 300 のノードのアドレス

二分探索木の探索

続いて二分探索木に対する操作を解説していきます。

まずは二分探索木の中から指定した探索値を持つノードを探索する方法について解説します。

二分探索木は左の子・親・右の子に大小関係で解説したように、下記の関係を持ちます。

左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値

つまり、あるノードの子孫ノードに探索値を持つノードがあるとすれば、そのノードの値よりも探索値が小さい場合は、探索値を持つノードは必ず左の子孫ノード内に存在する事になります。

逆にノードの値よりも探索値が大きい場合は、探索値を持つノードは必ず右の子孫ノード内に存在する事になります。

子孫との大小関係を考慮した探索の考え方

したがって最上位の親ノードである根ノードから順に、ノードの値と探索値の比較を行い、大小関係に基づいて子を辿っていく事で探索値を見つけることが可能です。

具体的な手順は下記のようになります。

  1. 注目ノードを根ノードする
  2. 注目ノードと探索値の大小関係を調べる
    • 同じ値である場合、その注目ノードが探索値を持つノードであるので探索完了
    • 探索値の方が小さい場合、注目ノードの左の子を新たな注目ノードに設定して 2. に戻る
      （左の子が無い場合は探索値は無い事になるので探索終了）
    • 探索値の方が大きい場合、注目ノードの右の子を新たな注目ノードに設定して 2. に戻る
      （右の子が無い場合は探索値は無い事になるので探索終了）

再掲になりますが、例えば下の図で値 33 を持つ緑色のノードを探索する場合は太矢印をたどっていく事で探索値を見つけることができます。

二分探索木での探索の例

探索を行う関数の例は下記のようになります。

探索を行う関数の例 
/* searchNode:指定されたnumberを持つノードを探索する
   引数１ root : 探索を開始するノードのアドレス
   引数２ number : 探索する会員番号
   返却値 : number を持つノードのアドレス（存在しない場合は NULL）*/
struct node_t *searchNode(struct node_t *root, int number){
  struct node_t *node;
  
  node = root;

  /* 探索を行うループ（注目ノードがNULLになったら終了 */
  while(node){
    if(number < node->number){
      /* 探索値がノードの値よりも小さい場合 */

      /* 注目ノードを左の子ノードに設定 */
      node = node->left;
    } else if(number > node->number){
      /* 探索値がノードの値よりも大きい場合 */

      /* 注目ノードを右の子ノードに設定 */
      node = node->right;
    } else {
      /* 探索値 = ノードの値の場合 */
      return node;
    }
  }
  
  /* 探索値を持つノードが見つからなかった場合 */
  return NULL;
}

二分探索木への追加

続いてノードの追加（会員情報の追加）について解説します。

二分探索木に対するノードの追加のポイントは、「左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値」の関係を崩さないように追加することです。どの場所に追加するかが重要です。

その場所は「探索」と同じような手順で行うことができます。

探索では、辿るべき注目ノードの左の子ノードもしくは右の子ノードが無い場合は処理を終了していましたが、その場所こそが「左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値」の関係を崩さずにノードを追加できる場所となります。

具体的には下記手順でノードを追加することができます。

  1. 注目ノードを根ノードする
  2. 注目ノードと追加する値の大小関係を調べる
    • 同じ値である場合
      • すでに追加する値を持つノードがあるので追加処理終了
    • 探索値の方が小さい場合
      • 左の子がある場合、注目ノードの左の子を新たな注目ノードに設定して 2. に戻る
      • 左の子が無い場合、注目ノードの左の子の位置にノードを追加
    • 探索値の方が大きい場合
      • 右の子がある場合、注目ノードの右の子を新たな注目ノードに設定して 2. に戻る
      • 右の子が無い場合、注目ノードの右の子の位置にノードを追加

例えば下の二分探索木に対して値 40 のノードを追加する場合、探索していくと赤矢印のところで子ノードがなくて探索に失敗します。

二分探索木で探索に失敗する例

なので、この子ノードの位置に新たなノードを追加することになります。

二分探索木へのノードの追加

ノードを追加しても各ノードに対して下記が成立していることも確認していただけると思います。

左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値

追加するノードは葉ノードになりますので、左の子ノードを指すポインタ、右の子ノードを指すノードを指すポインタ両方共に NULL を設定する必要があります。

これらを考慮したノードを追加する関数は下記のようになります。

ノードの追加を行う関数例 
/* mallocNode:ノードの構造体のメモリを確保し、データを設定
   引数１ number : 追加する会員番号
   引数２ name : 追加する会員の名前
   返却値 : 追加したノードのアドレス */
struct node_t *mallocNode(int number, char *name){
  struct node_t *add;

  add = (struct node_t*)malloc(sizeof(struct node_t));
  if(add == NULL){ 
    return NULL;
  }

  add->left = NULL;
  add->right = NULL;
  add->number = number;
  strcpy(add->name, name);

  return add;
}

/* addNode:指定されたnumberとname持つノードを追加する
   引数１ root : 根ノードのアドレス
   引数２ number : 追加する会員番号
   引数３ name : 追加する会員の名前
   返却値 : 根ルートのアドレス */
struct node_t *addNode(struct node_t *root, int number, char *name){
  struct node_t *node;

  /* まだノードが一つもない場合 */
  if(root == NULL){
    /* 根ノードとしてノードを追加 */
    root = mallocNode(number, name);
    if(root == NULL){
      printf("malloc error\n");
      return NULL;
    }
    return root;
  }

    /* 根ノードから順に追加する場所を探索 */
    node = root;
    while(1) {
      if(number < node->number){
        /* 追加する値がノードの値よりも小さい場合 */

        if(node->left == NULL){
          /* そのノードの左の子が無い場合（もう辿るべきノードが無い場合）*/

          /* その左の子の位置にノードを追加 */
          node->left = mallocNode(number, name);

          /* 追加完了したので処理終了 */
          break;
       }

       /* 左の子がある場合は左の子を新たな注目ノードに設定 */
       node = node->left;

   } else if(number > node->number){
     /* 追加する値がノードの値よりも大きい場合 */

    if(node->right == NULL){
      /* そのノードの右の子が無い場合（もう辿るべきノードが無い場合）*/

      /* その右の子の位置にノードを追加 */
      node->right = mallocNode(number, name);

      /* 追加完了したので処理終了 */
      break;
      }

      /* 右の子がある場合は右の子を新たな注目ノードに設定 */
      node = node->right;
    } else {
      /* 追加する値とノードの値が同じ場合 */

      printf("%d already exist\n", number);
      break;
    }
 }

  return root;
}

mallocNode 関数は下記を行う関数になっています。

  • ノードのメモリを確保
  • 指定されたデータ（会員番号と名前）をノードに設定
  • ノードの左の子ノードと右の子ノードを指すポインタそれぞれに NULL を設定

スポンサーリンク

二分探索木からのノードの削除

次はノードの削除（会員情報の削除）について解説します。

こちらも追加同様に「左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値」の関係を崩さないように削除することがポイントになります。

削除処理は下記の手順で行います。

  1. 削除対象ノードを探索する
  2. 削除対象ノードを削除する

削除対象ノードの探索

1. の削除対象ノードの探索は基本的に探索で紹介した方法と同様の方法で行うことができます。

削除対象ノードを探索するソースコードは下記のようになります（node は削除対象ノードのアドレスを格納する変数、parent はその削除対象ノードの親ノードのアドレスを格納する変数、number は削除したいノードの会員番号を格納した変数）。

削除対象ノードの探索 
 /* 削除対象ノードを指すノードを探索 */
  node = root;
  parent = NULL;
  
  while(node !=  NULL){
    if(number < node->number){
      parent = node;
      node = node->left;
    } else if(number > node->number){
      parent = node;
      node = node->right;
    } else {
      break;
    }
  }

parent は削除対象ノードの親ノードを指すポインタになります。

削除時は削除対象ノードの親ノードの設定も必要になりますので、その親ノードへのポインタも覚えておくようにしておくと便利だと考えてこの変数を使っています。

2. のノードの削除処理は、削除するノードの子ノードの数によって異なります。それぞれについて解説していきます。

削除対象ノードに子ノードが無い場合の削除

考え方が一番簡単なのはこのパターンです。葉ノードを消しても上記の関係は崩れませんので、単純にそのノードを削除してしまえば良いです。

ただし、単純に削除対象ノードのメモリを解放するだけ（free するだけ）だと、親ノードはまだ削除対象ノードを指したままの状態です。

これだと探索などを行う際に解放済みのメモリにアクセスしてエラー終了してしまいます。

削除したノードを指している例

ですので、削除対象ノードを指していた親ノードの子ノードを指すポインタを NULL に設定する必要があります。

削除したノードを指しているポインタをNULLに設定する図

このパターンのノードを削除する関数は下のようになります。

子ノードがないノードの削除 
/* deleteNoChildeNode:指定された子の無いノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ parent：削除するノードの親ノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteNoChildNode(struct node_t *root, struct node_t *node, struct node_t *parent){

  if(parent != NULL){
    /* 親がいる場合（根ノード以外の場合）は
    削除対象ノードを指すポインタをNULLに設定 */
    if(parent->left ==  node){
       /* 削除対象ノードが親ノードから見て左の子の場合 */
        parent->left = NULL;
    } else {
      /* 削除対象ノードが親ノードから見て右の子の場合 */
      parent->right = NULL;
    }
    free(node);
  }  else {
    /* 削除対象ノードが根ノードの場合 */
    free(node);
      
    /* 根ノードを指すポインタをNULLに設定 */
    root = NULL;
  }
    
  return root;
}

削除対象ノードに子ノードが一つだけある場合の削除

イメージとしては削除対象ノードを削除して、子孫ノードをそのままの形で一段階根ノード側に寄せる感じです。これにより二分探索木の大小関係を崩さずに削除することができます。

具体的な削除手順は下記のようになります。

  1. 削除対象ノードに子ノードのデータとポインタをコピー
  2. コピー元の子ノードを削除

処理の流れを図で表すと下のようになります。

子ノードが一つあるノードの削除の流れ

このパターンのノードの削除関数は下のようになります。

子ノードが１つのノードの削除 
/* deleteOneChildeNode:指定された子が一つのノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ child : 削除するノードの子ノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteOneChildNode(struct node_t *root, struct node_t *node, struct node_t * child){
   
  /* 削除対象ノードにその子ノードのデータとポインタをコピー */
  node->number = child->number;
  strcpy(node->name, child->name);
  node->left = child->left;
  node->right = child->right;
    
  /* コピー元のノードを削除 */
  free(child);
  
  return root;
}

削除対象ノードに子ノードが二つある場合の削除

削除対象ノードに子ノードが二つある場合は下記の手順を踏めばシステマチックに「左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値」関係を崩さずにノードを削除することが可能です。

  1. 削除対象ノードの左の子孫ノードたちから一番大きい値を持つノード（最大ノード）を探す
  2. 最大ノードのデータを削除対象ノードにコピー（ポインタはコピーしない）
  3. 最大ノードを削除

最大ノードは、当然削除対象ノードの左の子孫ノードの中で一番大きな値を持つノードです。

また、削除対象ノードの右の子孫のどのノードよりも小さい値を持つノードです。なぜなら二分探索木の各ノードには下記の関係があるからです。

左の子孫ノードの値 ≦ ノードの値 ≦ 右の子孫ノードの値

ですので、最大ノードのデータで削除対象ノードに上書きしたとしても、上記の関係は保たれたままになり、後は 3. の処理で最大ノードを削除してやれば、上記の関係を保ったまま子ノードが２つある削除対象ノードを削除することができます。

3. の処理では、最大ノードの子の数に応じて削除対象ノードに子ノードが無い場合か削除対象ノードに子ノードが一つだけある場合の処理を行えば良いわけですので、結局子ノードが１つ以下の場合の削除が行えれば 3. の処理も実現することが可能です（最大ノードは最大の値を持つノードなので右の子ノードを持ちません。従って子ノードが２つになることはありえません）。

子ノードを２つ持っているノードを削除する関数は下記のようになります。

子ノードが２つのノードの削除 
/* deleteTwoChildeNode:指定された子が二つのノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteTwoChildNode(struct node_t *root, struct node_t *node){

  struct node_t *max;
  struct node_t *maxParent;
  
  /* 左の子から一番大きい値を持つノードを探索 */
  max = node->left;
  maxParent = node;
    
  while(max->right != NULL){
    maxParent = max;
    max = max->right;
  }
  printf("max number is %d\n", max->number);
    
  /* 最大ノードのデータのみ削除対象ノードにコピー */
  node->number = max->number;
  strcpy(node->name, max->name);
    
  /* 最大ノードを削除 */
  
  /* maxは最大ノードなので必ずmax->rightはNULLになる */
  if(max->left == NULL){
    /* 最大ノードに子がいない場合 */
    root = deleteNoChildNode(root, max, maxParent);      
    } else {
      /* 最大ノードに子供が一ついる場合 */
      root = deleteOneChildNode(root, max, max->left);
    }

    return root;
}

二分探索木の表示

次は二分探索木の全ノードのデータを表示する方法について解説します。

この表示にはやり方があると思いますが、ここでは下のように、木の形を保ったまま左に９０度回転したように二分探索木を表示する方法を解説します。首を傾ければ木のように見えるはず…。

      +500(500)
    +300(300)
      +250(250)
  +200(200)
      +175(175)
    +150(150)
      +125(125)
+100(100)
  + 50(50)
      + 25(25)
    + 10(1)
      +  5(5)

この表示は再帰呼び出しを用いることで簡単に実現することが可能です。

二分探索木の全ノードを表示する関数は下記のようになります。

二分探索木の表示 
/* printTree:rootを根ノードとする二分探索木をの全ノードを表示する
   引数１ root : 木の根ノードのアドレス
   引数２ depth: 関数呼び出しの深さ
   返却値 : なし */
void printTree(struct node_t *root, int depth){
  int i;

  if(root == NULL){
    return ;
  }

  /* 右の子孫ノードを表示 */
  printTree(root->right, depth+1);
 
  /* 深さをスペースで表現 */ 
  for(i = 0; i < depth; i++){
    printf("  ");
  }

  /* ノードのデータを表示 */
  printf("+%3d(%s)\n", root->number, root->name);

  /* 左の子孫ノードを表示 */
  printTree(root->left, depth+1);

  depth++;
}

二分探索木のプログラム例

ここまでの解説を考慮して私が作成した二分探索木のプログラム全体は下記のようになります。

二分探索木 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAME_LEN 256

/* 二分探索木のノードを表す構造体 */
struct node_t {
  int number;
  char name[MAX_NAME_LEN];
  struct node_t *left;
  struct node_t *right;
};


/* deleteTree:二分探索木のノード全てを削除する
   引数１ root : 根ノードのアドレス
   返却値 : なし */
void deleteTree(struct node_t *root){
  if(root == NULL){
    return;
  }

  deleteTree(root->left);
  deleteTree(root->right);

  printf("free:%d(%s)\n", root->number, root->name);
  free(root);

}

/* mallocNode:ノードの構造体のメモリを確保し、データを設定
   引数１ number : 追加する会員番号
   引数２ name : 追加する会員の名前
   返却値 : 追加したノードのアドレス */
struct node_t *mallocNode(int number, char *name){
  struct node_t *add;

  add = (struct node_t*)malloc(sizeof(struct node_t));
  if(add == NULL){ 
    return NULL;
  }

  add->left = NULL;
  add->right = NULL;
  add->number = number;
  strcpy(add->name, name);

  return add;
}

/* addNode:指定されたnumberとname持つノードを追加する
   引数１ root : 根ノードのアドレス
   引数２ number : 追加する会員番号
   引数３ name : 追加する会員の名前
   返却値 : 根ルートのアドレス */
struct node_t *addNode(struct node_t *root, int number, char *name){
  struct node_t *node;

  /* まだノードが一つもない場合 */
  if(root == NULL){
    /* 根ノードとしてノードを追加 */
    root = mallocNode(number, name);
    if(root == NULL){
      printf("malloc error\n");
      return NULL;
      }
      return root;
   }

   /* 根ノードから順に追加する場所を探索 */
   node = root;
   while(1) {
     if(number < node->number){
       /* 追加する値がノードの値よりも小さい場合 */

       if(node->left == NULL){
         /* そのノードの左の子が無い場合（もう辿るべきノードが無い場合）*/

         /* その左の子の位置にノードを追加 */
         node->left = mallocNode(number, name);

         /* 追加完了したので処理終了 */
         break;
       }

       /* 左の子がある場合は左の子を新たな注目ノードに設定 */
       node = node->left;

     } else if(number > node->number){
       /* 追加する値がノードの値よりも大きい場合 */

       if(node->right == NULL){
         /* そのノードの右の子が無い場合（もう辿るべきノードが無い場合）*/

         /* その右の子の位置にノードを追加 */
         node->right = mallocNode(number, name);

         /* 追加完了したので処理終了 */
         break;
       }

       /* 右の子がある場合は右の子を新たな注目ノードに設定 */
       node = node->right;
     } else {
       /* 追加する値とノードの値が同じ場合 */

       printf("%d already exist\n", number);
       break;
    }
   }
    
   return root;
}

/* searchNode:指定されたnumberを持つノードを探索する
   引数１ root : 探索を開始するノードのアドレス
   引数２ number : 探索する会員番号
   返却値 : number を持つノードのアドレス（存在しない場合は NULL）*/
struct node_t *searchNode(struct node_t *root, int number){
  struct node_t *node;
  
  node = root;

  /* 探索を行うループ（注目ノードがNULLになったら終了 */
  while(node){
    if(number < node->number){
      /* 探索値がノードの値よりも小さい場合 */

      /* 注目ノードを左の子ノードに設定 */
      node = node->left;
    } else if(number > node->number){
      /* 探索値がノードの値よりも大きい場合 */

      /* 注目ノードを右の子ノードに設定 */
      node = node->right;
    } else {
      /* 探索値 = ノードの値の場合 */
      return node;
    }
  }
  
  /* 探索値を持つノードが見つからなかった場合 */
  return NULL;
}

/* deleteNoChildeNode:指定された子の無いノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ parent：削除するノードの親ノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteNoChildNode(struct node_t *root, struct node_t *node, struct node_t *parent){

  if(parent != NULL){
    /* 親がいる場合（根ノード以外の場合）は
    削除対象ノードを指すポインタをNULLに設定 */
    if(parent->left ==  node){
       /* 削除対象ノードが親ノードから見て左の子の場合 */
        parent->left = NULL;
    } else {
      /* 削除対象ノードが親ノードから見て右の子の場合 */
      parent->right = NULL;
    }
    free(node);
  }  else {
    /* 削除対象ノードが根ノードの場合 */
    free(node);
      
    /* 根ノードを指すポインタをNULLに設定 */
    root = NULL;
  }
    
  return root;
}

/* deleteOneChildeNode:指定された子が一つのノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ child : 削除するノードの子ノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteOneChildNode(struct node_t *root, struct node_t *node, struct node_t * child){
   
  /* 削除対象ノードにその子ノードのデータとポインタをコピー */
  node->number = child->number;
  strcpy(node->name, child->name);
  node->left = child->left;
  node->right = child->right;
    
  /* コピー元のノードを削除 */
  free(child);
  
  return root;
}

/* deleteTwoChildeNode:指定された子が二つのノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   返却値 : 根ノードのアドレス */
struct node_t *deleteTwoChildNode(struct node_t *root, struct node_t *node){

  struct node_t *max;
  struct node_t *maxParent;
  
  /* 左の子から一番大きい値を持つノードを探索 */
  max = node->left;
  maxParent = node;
    
  while(max->right != NULL){
    maxParent = max;
    max = max->right;
  }
  printf("max number is %d\n", max->number);
    
  /* 最大ノードのデータのみ削除対象ノードにコピー */
  node->number = max->number;
  strcpy(node->name, max->name);
    
  /* 最大ノードを削除 */
  
  /* maxは最大ノードなので必ずmax->rightはNULLになる */
  if(max->left == NULL){
    /* 最大ノードに子がいない場合 */
    root = deleteNoChildNode(root, max, maxParent);      
    } else {
      /* 最大ノードに子供が一ついる場合 */
      root = deleteOneChildNode(root, max, max->left);
    }

    return root;
}



/* deleteNode:指定されたnumberを持つノードを削除する
   引数１ root : 木の根ノードのアドレス
   引数２ number : 削除する会員番号
   返却値 : 根ノードのアドレス */
struct node_t *deleteNode(struct node_t *root, int number){
  struct node_t *node;
  struct node_t *parent;

  if(root == NULL){
    return NULL;
  }

  /* 削除対象ノードを指すノードを探索 */
  node = root;
  parent = NULL;
  
  while(node !=  NULL){
    if(number < node->number){
      parent = node;
      node = node->left;
    } else if(number > node->number){
      parent = node;
      node = node->right;
    } else {
      break;
    }
  }
  
  /* 指定されたnumberを値として持つノードが存在しない場合は何もせず終了 */
  if(node == NULL){
    printf("%d を持つノードが存在しません\n", number);
    return root;
  }

  printf("Delete %d(%s) node\n", node->number, node->name);

  if(node->left == NULL && node->right == NULL){    
    /* 子がいないノードの削除 */
    root = deleteNoChildNode(root, node, parent);
  } else if((node->left != NULL && node->right == NULL) ||
    (node->right != NULL && node->left == NULL)){
    /* 子が一つしかない場合 */
    
    if(node->left != NULL){
      root = deleteOneChildNode(root, node, node->left);
    } else {
      root = deleteOneChildNode(root, node, node->right);
    }
  } else {
    /* 左の子と右の子両方がいるノードの削除 */
    root = deleteTwoChildNode(root, node);
  }
  
  return root;  
}

/* printTree:rootを根ノードとする二分探索木をの全ノードを表示する
   引数１ root : 木の根ノードのアドレス
   引数２ depth: 関数呼び出しの深さ
   返却値 : なし */
void printTree(struct node_t *root, int depth){
  int i;

  if(root == NULL){
    return ;
  }

  /* 右の子孫ノードを表示 */
  printTree(root->right, depth+1);
 
  /* 深さをスペースで表現 */ 
  for(i = 0; i < depth; i++){
    printf("  ");
  }

  /* ノードのデータを表示 */
  printf("+%3d(%s)\n", root->number, root->name);

  /* 左の子孫ノードを表示 */
  printTree(root->left, depth+1);

  depth++;
}

int main(void){
  struct node_t *root, *node;
  int input;
  int number;
  char name[MAX_NAME_LEN];
  int loop;

  /* まだ木がないのでrootをNULLにセット */
  root = NULL;

  /* 最初にてきとうにノードを追加しておく */
  root = addNode(root, 100, "100");
  root = addNode(root, 200, "200");
  root = addNode(root, 300, "300");
  root = addNode(root, 50, "50");
  root = addNode(root, 150, "150");
  root = addNode(root, 250, "250");
  root = addNode(root, 10, "1");
  root = addNode(root, 125, "125");
  root = addNode(root, 5, "5");
  root = addNode(root, 25, "25");
  root = addNode(root, 500, "500");
  root = addNode(root, 175, "175");

  loop = 1;
  while(loop){
    printf("処理を選択(1:add, 2:delete, 3:search, 4:exit)");
    scanf("%d", &input);

    switch(input){
    case 1:
      printf("会員番号(1 - 999):");
      scanf("%d", &number);
      if(number < 1 || number > 999){
        printf("値が範囲外です\n");
        continue;
      }

      printf("名前:");
      scanf("%s", name);

      root = addNode(root, number, name);
      break;
    case 2:
      printf("会員番号(1 - 999):");
      scanf("%d", &number);
      if(number < 1 || number > 999){
        printf("値が範囲外です\n");
        continue;
      }

      root = deleteNode(root, number);
      
      break;
    case 3:
      printf("会員番号(1 - 999):");
      scanf("%d", &number);
      if(number < 1 || number > 999){
        printf("値が範囲外です\n");
        continue;
      }
      
      node = searchNode(root, number);
      if(node == NULL){
        printf("number %d is not found\n", number);
      } else {
        printf("number %d : %s\n", number, node->name);
      }
      break;
    default:
      loop = 0;
      break;
    }
    printTree(root, 0);
  }

  deleteTree(root);   
  
  return 0;
}

スポンサーリンク

まとめ

このページでは二分探索木について解説し、二分探索木に対して探索・追加・削除・表示を行う仕組みとその関数および二分探索木全体のプログラムを紹介しました。

二分探索木は基本的なデータ構造ですし、これを自分で実装してみるとポインタ等の理解も進みますので是非自分でもプログラミングしてみてください！

このページで紹介した二分探索木では、ノードを追加した順番によってはノードが一方に偏る可能性があります。

これを防ぐために、二分探索木を拡張して平衡二分探索木（AVL 木）を構成するための方法やプログラムを下記で紹介していますので、こちらも是非読んでみてください。

AVL木解説ページのアイキャッチ 【C言語】AVL 木（平衡２分探索木）の解説と実装

また、同じ基本的なデータ構造としてリスト構造がありますが、こちらも下のページで解説していますので是非ご覧ください（リスト構造の方が二分探索木よりも仕組みやプログラムが簡単です）。

リスト構造の解説ページアイキャッチ 【C言語】リスト構造について分かりやすく解説【図解】

修正履歴

コメントを頂き、下記を修正しています。

2020/3/23：deleteTree 関数を修正。

修正前 
void deleteTree(struct node_t *root){
  if(root == NULL){
    return;
  }
  if(root->left != NULL){
    deleteTree(root->left);
  }
  if(root->right != NULL){
    deleteTree(root->right);
  }
  printf("free:%d(%s)\n", root->number, root->name);
  free(root);

}
[/codebox title="修正後"] 
void deleteTree(struct node_t *root){
  if(root == NULL){
    return;
  }

  deleteTree(root->left);
  deleteTree(root->right);

  printf("free:%d(%s)\n", root->number, root->name);
  free(root);

}
[/codebox]

同じカテゴリのページ一覧を表示

2 COMMENTS

Kちゃん

deleteTree:二分探索木のノード全てを削除する
について質問です。
関数の冒頭で
if(root == NULL){
をしているので、

下記のようにそれぞれNULL確認をしなくてよいように感じたのですが、何か安全性などを考慮しているなど、理由があるのでしょうか。
if(root->left != NULL){
deleteTree(root->left);
}
if(root->right != NULL){
deleteTree(root->right);
}

下記のような書き方では未定義動作なるなど、問題があるのでしょうか。
void deleteTree(struct node_t *root){
if(root == NULL){
return;
}

deleteTree(root->left);
deleteTree(root->right);
printf(“free:%d(%s)\n”, root->number, root->name);
free(root);
}

daeu

Kちゃん

コメントありがとうございます！

さすが鋭いですね…。
回答としては「その NULL チェックに全く意味はありません」になります。
Kちゃんの書き方が正しいです！

もし再起処理でなくて、他の関数を呼んでいるのであれば、ちょっとは意味があったかと思います。
その関数の中で NULL チェックを行なっているとは限りませんので…。

ただ今回は再起処理で自分自身の関数を呼んでいるので、
関数の頭で NULL チェックをしている事が確定しており、意味のないチェックになってしまっていますね…。
紛らわしい書き方をしてしまってすみません…。

ということで、早速ソースコードを修正しました！
本当にコメントありがとうございます。私としてもいい勉強になりました！
また気づいた点などありました教えていただけると幸いです。

現在コメントは受け付けておりません。

前の記事

C言語でハノイの塔の解法プログラムを実装！

次の記事

クイックソートを図を使って分かりやすく解説（C言語サンプルプロ…
クイックソート解説ページのアイキャッチ