fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. struct Node
  6. {
  7.   int value;
  8.   struct Node *left;
  9.   struct Node *right;
  10. };
  11.  
  12. struct Node *newNode(int value)
  13. {
  14.   struct Node *p = malloc(sizeof(*p));
  15.   p->value = value;
  16.   p->left = NULL;
  17.   p->right = NULL;
  18.   return p;
  19. }
  20.  
  21. struct Node *addNode(struct Node *p, int value)
  22. {
  23.   if (p == NULL)
  24.   {
  25.     return newNode(value);
  26.   }
  27.   else
  28.   {
  29.     if (value < p->value)
  30.     {
  31.       p->left = addNode(p->left, value);
  32.     }
  33.     else
  34.     {
  35.       p->right = addNode(p->right, value);
  36.     }
  37.  
  38.     return p;
  39.   }
  40. }
  41.  
  42. struct Node *deleteMinNode(struct Node *p)
  43. {
  44.   struct Node* r;
  45.  
  46.   if (p == NULL)
  47.   {
  48.     return NULL;
  49.   }
  50.   else
  51.   {
  52.     if (p->left == NULL)
  53.     {
  54.       r = p->right;
  55.       free(p);
  56.       return r;
  57.     }
  58.     else
  59.     {
  60.       p->left = deleteMinNode(p->left);
  61.       return p;
  62.     }
  63.   }
  64. }
  65.  
  66. struct Node *deleteNode(struct Node *p, int value, int *deleted)
  67. {
  68.   struct Node *r;
  69.   struct Node *n;
  70.  
  71.   if (p == NULL)
  72.   {
  73.     *deleted = 0;
  74.     return NULL;
  75.   }
  76.   else
  77.   {
  78.     if (value < p->value)
  79.     {
  80.       p->left = deleteNode(p->left, value, deleted);
  81.       return p;
  82.     }
  83.     else if (p->value < value)
  84.     {
  85.       p->right = deleteNode(p->right, value, deleted);
  86.       return p;
  87.     }
  88.     else
  89.     {
  90.       if (p->left == NULL)
  91.       {
  92.         r = p->right;
  93.         free(p);
  94.       }
  95.       else if (p->right == NULL)
  96.       {
  97.         r = p->left;
  98.         free(p);
  99.       }
  100.       else
  101.       {
  102.         n = p->right;
  103.  
  104.         while (n->left != NULL)
  105.         {
  106.           n = n->left;
  107.         }
  108.  
  109.         p->value = n->value;
  110.         p->right = deleteMinNode(p->right);
  111.         r = p;
  112.       }
  113.  
  114.       *deleted = 1;
  115.       return r;
  116.     }
  117.   }
  118. }
  119.  
  120. void writeNode(struct Node *p)
  121. {
  122.   if (p == NULL)
  123.   {
  124.     printf("_ ");
  125.   }
  126.   else
  127.   {
  128.     printf("[ %d ", p->value);
  129.     writeNode(p->left);
  130.     writeNode(p->right);
  131.     printf("] ");
  132.   }
  133. }
  134.  
  135. void destroyNode(struct Node *p)
  136. {
  137.   if (p == NULL)
  138.   {
  139.     return;
  140.   }
  141.   else
  142.   {
  143.     destroyNode(p->left);
  144.     destroyNode(p->right);
  145.     free(p);
  146.   }
  147. }
  148.  
  149. int main(int argc, char *argv[])
  150. {
  151.   int i;
  152.   int deleted;
  153.   struct Node *p = NULL;
  154.  
  155.   for (i = 1; i < argc; i++)
  156.   {
  157.     if (strcmp(argv[i], "--") == 0)
  158.     {
  159.       break;
  160.     }
  161.     else
  162.     {
  163.       p = addNode(p, atoi(argv[i]));
  164.     }
  165.   }
  166.  
  167.   printf("入力データ ");
  168.   writeNode(p);
  169.   printf("\n");
  170.  
  171.   for (i = i + 1; i < argc; i++)
  172.   {
  173.     printf("deleteNode(%d)\n", atoi(argv[i]));
  174.     p = deleteNode(p, atoi(argv[i]), &deleted);
  175.  
  176.     if (deleted)
  177.     {
  178.       printf("==> ");
  179.       writeNode(p);
  180.       printf("\n");
  181.     }
  182.     else
  183.     {
  184.       printf("deleteNode: 指定キーのノードがありません\n");
  185.     }
  186.   }
  187.  
  188.   destroyNode(p);
  189.  
  190.   return 0;
  191. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SNQ2Qi
language:
C (gcc 8.3)
created:
11 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!