fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct node
  6. {
  7.     int data; //node will store an integer
  8.     struct node *right_child; // right child
  9.     struct node *left_child; // left child
  10. };
  11.  
  12. struct node* search(struct node *root, int x)
  13. {
  14.     if(root==NULL || root->data==x) //if root->data is x then the element is found
  15.         return root;
  16.     else if(x>root->data) // x is greater, so we will search the right subtree
  17.         return search(root->right_child, x);
  18.     else //x is smaller than the data, so we will search the left subtree
  19.         return search(root->left_child,x);
  20. }
  21.  
  22. //function to find the minimum value in a node
  23. struct node* find_minimum(struct node *root)
  24. {
  25.     if(root == NULL)
  26.         return NULL;
  27.     else if(root->left_child != NULL) // node with minimum value will have no left child
  28.         return find_minimum(root->left_child); // left most element will be minimum
  29.     return root;
  30. }
  31.  
  32. //function to create a node
  33. struct node* new_node(int x)
  34. {
  35.     struct node *p;
  36.     p = malloc(sizeof(struct node));
  37.     p->data = x;
  38.     p->left_child = NULL;
  39.     p->right_child = NULL;
  40.  
  41.     return p;
  42. }
  43.  
  44. struct node* insert(struct node *root, int x)
  45. {
  46.     //searching for the place to insert
  47.     if(root==NULL)
  48.         return new_node(x);
  49.     else if(x>root->data) // x is greater. Should be inserted to right
  50.         root->right_child = insert(root->right_child, x);
  51.     else // x is smaller should be inserted to left
  52.         root->left_child = insert(root->left_child,x);
  53.     return root;
  54. }
  55.  
  56. // funnction to delete a node
  57. struct node* delete(struct node *root, int x)
  58. {
  59.     //searching for the item to be deleted
  60.     if(root==NULL)
  61.         return NULL;
  62.     if (x>root->data)
  63.         root->right_child = delete(root->right_child, x);
  64.     else if(x<root->data)
  65.         root->left_child = delete(root->left_child, x);
  66.     else
  67.     {
  68.         //No Children
  69.         if(root->left_child==NULL && root->right_child==NULL)
  70.         {
  71.             free(root);
  72.             return NULL;
  73.         }
  74.  
  75.         //One Child
  76.         else if(root->left_child==NULL || root->right_child==NULL)
  77.         {
  78.             struct node *temp;
  79.             if(root->left_child==NULL)
  80.                 temp = root->right_child;
  81.             else
  82.                 temp = root->left_child;
  83.             free(root);
  84.             return temp;
  85.         }
  86.  
  87.         //Two Children
  88.         else
  89.         {
  90.             struct node *temp = find_minimum(root->right_child);
  91.             root->data = temp->data;
  92.             root->right_child = delete(root->right_child, temp->data);
  93.         }
  94.     }
  95.     return root;
  96. }
  97.  
  98. void inorder(struct node *root)
  99. {
  100.     if(root!=NULL) // checking if the root is not null
  101.     {
  102.         inorder(root->left_child); // visiting left child
  103.         printf(" %d ", root->data); // printing data at root
  104.         inorder(root->right_child);// visiting right child
  105.     }
  106. }
  107.  
  108. int main()
  109. {
  110.     /*
  111.                    20
  112.                  /    \
  113.                 /      \
  114.                5       30
  115.              /   \     /\
  116.             /     \   /  \
  117.            1      15 25  40
  118.                 /          \
  119.                /            \
  120.               9             45
  121.             /   \          /
  122.            /     \        /
  123.           7      12      42
  124.     */
  125.     struct node *root;
  126.     root = new_node(20);
  127.     insert(root,5);
  128.     insert(root,1);
  129.     insert(root,15);
  130.     insert(root,9);
  131.     insert(root,7);
  132.     insert(root,12);
  133.     insert(root,30);
  134.     insert(root,25);
  135.     insert(root,40);
  136.     insert(root, 45);
  137.     insert(root, 42);
  138.  
  139.     inorder(root);
  140.     printf("\n");
  141.  
  142.     root = delete(root, 1);
  143.     /*
  144.                    20
  145.                  /    \
  146.                 /      \
  147.                5       30
  148.                  \     /\
  149.                   \   /  \
  150.                   15 25   40
  151.                 /           \
  152.                /             \
  153.               9              45
  154.             /   \           /
  155.            /     \         /
  156.           7      12       42
  157.     */
  158.  
  159.     root = delete(root, 40);
  160.     /*
  161.                    20
  162.                  /    \
  163.                 /      \
  164.                5       30
  165.                  \     /\
  166.                   \   /  \
  167.                   15 25  45
  168.                  /       / 
  169.                 /       /   
  170.                9       42    
  171.              /   \          
  172.             /     \        
  173.            7      12      
  174.     */
  175.  
  176.     root = delete(root, 45);
  177.     /*
  178.                    20
  179.                  /    \
  180.                 /      \
  181.                5       30
  182.                  \     /\
  183.                   \   /  \
  184.                   15 25  42
  185.                  /          
  186.                 /            
  187.                9            
  188.              /   \          
  189.             /     \        
  190.            7      12      
  191.     */
  192.     root = delete(root, 9);
  193.     inorder(root);
  194.     /*
  195.                    20
  196.                  /    \
  197.                 /      \
  198.                5       30
  199.                  \     /\
  200.                   \   /  \
  201.                   15 25  42
  202.                  /          
  203.                 /            
  204.                12            
  205.              /             
  206.             /             
  207.            7            
  208.     */
  209.     printf("\n");
  210.  
  211.     return 0;
  212. }
Success #stdin #stdout 0s 4596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 1  5  7  9  12  15  20  25  30  40  42  45 
 5  7  12  15  20  25  30  42
https://ideone.com/XvjNiK
language:
C (gcc 8.3)
created:
4 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!