A. プログラム例

以下にプログラム例を示す．

   1 //============= ノードを表す構造体 ==============================
   2 typedef struct node_tag{
   3   int value;
   4   struct node_tag *left;
   5   struct node_tag *right;
   6 }node;
   7 
   8 //============== プロトタイプ宣言 =================================
   9 extern node *creat_node(int new_data);
  10 extern void insert_node(node *t_node, int new_data);
  11 extern void delete_node(node *del_node, int del_data);
  12 extern void print_tree(node *t_node, int depth);
  13 
  14 
  15 extern node *root_tree;

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "b_tree.h"
   4 
   5 node *root_tree=NULL;
   6 
   7 //============== ノード作成関数 ==================================================
   8 node *creat_node(int new_data)
   9 {
  10   node *new_node;
  11 
  12   new_node=(node *)malloc(sizeof(node));
  13 
  14   new_node->value = new_data;
  15   new_node->left = NULL;
  16   new_node->right = NULL;
  17 
  18   return new_node;
  19 }
  20 
  21 
  22 //============== ノードをツリーに追加する関数 =======================================
  23 void insert_node(node *t_node, int new_data)
  24 {
  25 
  26   if(t_node==NULL){            // rootが空の場合(最初のデータ)
  27     root_tree = creat_node(new_data);
  28     return;
  29   }
  30 
  31   if(t_node->value > new_data){
  32     if(t_node->left == NULL){
  33       t_node->left=creat_node(new_data);
  34     }else{
  35       insert_node(t_node->left, new_data);
  36     }
  37   }else{
  38     if(t_node->right == NULL){
  39       t_node->right=creat_node(new_data);
  40     }else{
  41       insert_node(t_node->right, new_data);
  42     }
  43   }
  44    
  45   return;
  46 }
  47 
  48 //============== ノードをツリーから削減する関数 ======================================
  49 void delete_node(node *del_node, int del_data)
  50 {
  51   node *parent=NULL;      // 削除するノードの親
  52   node *big=NULL;         // 左の最大ノード
  53   node *pbig=NULL;        // 左の最大ノードの親
  54   int flag=0;
  55 
  56   // 削除するノードの探索
  57   while(del_node!=NULL && del_node->value!=del_data){
  58     if(del_node->value < del_data){
  59       parent = del_node;
  60       del_node = del_node -> right;
  61     }else{
  62       parent = del_node;
  63       del_node = del_node -> left;
  64     }
  65   }
  66 
  67   if(del_node==NULL){
  68     printf("削除するデータがありません!\n");
  69     return;
  70   }
  71 
  72   if(del_node->left == NULL){        // 削除するデータの左あるいは両方の子が無い
  73     if(parent==NULL){                // 削除するデータがrootのとき
  74       root_tree = del_node->right;
  75     }else if(parent->value > del_data){ // 削除するデータが親の左の子
  76       parent->left=del_node->right;
  77     }else{                              // 削除するデータが親の右の子
  78       parent->right=del_node->right;
  79     }
  80     free(del_node);
  81     return;
  82   }
  83 
  84   if(del_node->right == NULL){       // 削除するデータの右の子が無い
  85     if(parent==NULL){                // 削除するデータがrootのとき
  86       root_tree = del_node->right;
  87     }else if(parent->value > del_data){
  88       parent->left=del_node->left;
  89     }else{                              // 削除するデータが親の右の子
  90       parent->right=del_node->left;
  91     }
  92     free(del_node);
  93     return;
  94   }
  95 
  96   //--- 削除するデータに左右の子がある場合 ---
  97 
  98   pbig=del_node;
  99   big=del_node->left;
 100 
 101   while(big->right != NULL){       // 左の最大値をもつノードの検索
 102     pbig = big;
 103     big = big->right;
 104     flag = 1;
 105   }
 106 
 107   del_node->value = big->value;
 108 
 109   if(flag == 0){
 110     pbig->left = big->left;
 111   }else{
 112     pbig->right = big->left;
 113   }
 114   
 115   free(big);
 116 
 117 
 118 }
 119 
 120 
 121 //============== ええ加減にツリーを表示する関数 =====================================
 122 void print_tree(node *t_node, int depth)
 123 {
 124   int i;
 125 
 126   if(t_node==NULL)return;
 127 
 128   print_tree(t_node->right,depth+1);
 129 
 130   for(i=0; i<depth; i++)printf("  ");
 131   printf("%d\n", t_node->value);
 132 
 133   print_tree(t_node->left, depth+1);
 134   
 135   return;
 136 }

   1 #include <stdio.h>
   2 #include "b_tree.h"
   3 
   4 int main(void)
   5 {
   6 
   7   insert_node(root_tree,5);
   8   insert_node(root_tree,9);
   9   insert_node(root_tree,3);
  10   insert_node(root_tree,4);
  11   insert_node(root_tree,7);
  12   insert_node(root_tree,6);
  13   insert_node(root_tree,10);
  14   insert_node(root_tree,12);
  15   insert_node(root_tree,2);
  16   insert_node(root_tree,1);
  17 
  18   printf("\n\n");
  19   print_tree(root_tree, 0);
  20   
  21   delete_node(root_tree, 9);
  22   printf("\n\n");
  23   print_tree(root_tree, 0);
  24   return 0;
  25 }

ホームページ: Yamamoto's laboratory
著者: 山本昌志