fork download 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5.  
  6.  
  7. typedef struct tnode {
  8.   char *key;
  9.   char *value;
  10.   struct tnode *left;
  11.   struct tnode *right;
  12.   struct tnode *parent;
  13. } tnode;
  14.  
  15.  
  16. tnode *btree_empty(){
  17.  
  18.   tnode *t = (tnode *)malloc(sizeof(struct tnode));
  19.   t->key = NULL;
  20.   t->value = NULL;
  21.   t->left = NULL;
  22.   t->right = NULL;
  23.   t->parent = NULL;
  24.  
  25.   return t;
  26. }
  27.  
  28. void *btree_insert(char *key, char *val, tnode *t)
  29. {
  30.  
  31.   if (t->key == NULL){
  32.     strcpy(t->key, key);
  33.     strcpy(t->value, val);
  34.   }
  35.   else
  36.     if (strcmp(key, t->key) < 0)
  37.       if(t->left == NULL){
  38. 	t->left = (tnode *)malloc(sizeof(struct tnode));
  39. 	strcpy(t->left->key, key);
  40. 	strcpy(t->left->value, val);
  41. 	t->left->parent = t;
  42.       }
  43.       else
  44. 	btree_insert(key, val, t->left);
  45.     else
  46.       if(t->right == NULL){
  47. 	t->right = (tnode *)malloc(sizeof(struct tnode));
  48. 	strcpy(t->right->key, key);
  49. 	strcpy(t->right->value, val);
  50. 	t->right->parent = t;
  51.       }
  52.       else
  53. 	btree_insert(key, val, t->right);
  54. }
  55.  
  56. //最小値
  57. tnode *left_min(tnode *t){
  58.   if (t->left == NULL)
  59.     return t;
  60.   else
  61.     left_min(t->left);
  62. }
  63.  
  64.  
  65. void *btree_delete(char *key, tnode *t)
  66. {
  67.   tnode *tnode;
  68.   if(t != NULL){
  69.     if(strcmp(key, t->key) < 0)
  70.       btree_delete(key, t->left);
  71.     else if(strcmp(key, t->key) > 0)
  72.       btree_delete(key, t->right);
  73.     else
  74.       {//このノードを消去
  75. 	if(t->left == NULL && t->right == NULL){//tは末端
  76. 	  if(strcmp(t->key, t->parent->key) < 0){
  77. 	    //tは親から見て左ノード
  78. 	    t->parent->left = NULL;//親からの参照をなくす
  79. 	    free(t);
  80. 	  }
  81. 	  else{
  82. 	    //tは親から見て右ノード
  83. 	    t->parent->right = NULL;
  84. 	    free(t);
  85. 	  }
  86. 	}
  87. 	else if(t->left != NULL && t->right == NULL){//左ノードのみ
  88. 	  //親子関係再設定
  89. 	  t->parent->left = t->left;
  90. 	  t->left->parent = t->parent;
  91. 	  free(t);
  92. 	}
  93. 	else if(t->left == NULL && t->right != NULL){
  94. 	  t->parent->right = t->right;
  95. 	  t->right->parent = t->parent;
  96. 	}
  97. 	else{//子が2つ
  98. 	  tnode = left_min(t->right);
  99. 	  tnode->parent->left = NULL;
  100. 	  strcpy(t->key, tnode->key);
  101. 	  strcpy(t->value, tnode->value);
  102. 	  free(tnode);
  103. 	}
  104.       }
  105.   }
  106. }
  107.  
  108.  
  109.  
  110.  
  111. tnode *btree_search(char *key, tnode *t){
  112.  
  113.   if (t == NULL) 
  114.     return NULL;
  115.   else
  116.     if (strcmp(key, t->key) == 0)
  117.       return t;
  118.     else 
  119.       if (strcmp(key, t->key) < 0)
  120. 	btree_search(key, t->left);
  121.       else
  122. 	btree_search(key, t->right);
  123. }
  124.  
  125.  
  126. void btree_destroy(tnode *t){
  127.  
  128.   if (t != NULL){
  129.     if (t->left != NULL)
  130.       btree_destroy(t->left);
  131.     if (t->right != NULL)
  132.       btree_destroy(t->right);
  133.     free(t);
  134.   }
  135. }
  136.  
  137.  
  138. int main(void){
  139.   char *x, *key, *val;
  140.   tnode *top, *search;
  141.   x = (char *)malloc(sizeof(char) * 100);
  142.   key = (char *)malloc(sizeof(char) * 100);
  143.   val = (char *)malloc(sizeof(char) * 100);
  144.  
  145.  
  146.   top = btree_empty();
  147.  
  148.   while(scanf("%s", x) != EOF){
  149.     scanf(" ");
  150.     if(strcmp(x, "insert") == 0){
  151.       scanf("%s %s", key, val);   
  152.       btree_insert(key, val, top);
  153.     }
  154.     else if(strcmp(x, "delete") == 0){
  155.       scanf("%s", key);
  156.       btree_delete(key, top);
  157.     }
  158.     else if(strcmp(x ,"search") == 0){
  159.       scanf("%s", key);
  160.       search = btree_search(key, top);
  161.     }
  162.     else if(strcmp(x, "quit") == 0){
  163.       return 0;
  164.     }
  165.     scanf(" ");
  166.   }
  167.  
  168.   return 0;
  169. }
  170.  
  171.  
  172.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FdLdY2
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!