fork(1) download
copy 
  1. #include<stdio.h> 
  2. #include<stdlib.h> 
  3.  
  4. struct node 
  5. { 
  6.     int key; 
  7.     struct node *left, *right; 
  8. }; 
  9.  
  10. // A utility function to create a new BST node 
  11. struct node *newNode(int item) 
  12. { 
  13.     struct node *temp =  (struct node *)malloc(sizeof(struct node)); 
  14.     temp->key = item; 
  15.     temp->left = temp->right = NULL; 
  16.     return temp; 
  17. } 
  18.  
  19. // A utility function to do inorder traversal of BST 
  20. void inorder(struct node *root) 
  21. { 
  22.     if (root != NULL) 
  23.     { 
  24.         inorder(root->left); 
  25.         printf("%d ", root->key); 
  26.         inorder(root->right); 
  27.     } 
  28. } 
  29.  
  30. /* A utility function to insert a new node with given key in BST */
  31. struct node* insert(struct node* node, int key) 
  32. { 
  33.     /* If the tree is empty, return a new node */
  34.     if (node == NULL) return newNode(key); 
  35.  
  36.     /* Otherwise, recur down the tree */
  37.     if (key < node->key) 
  38.         node->left  = insert(node->left, key); 
  39.     else
  40.         node->right = insert(node->right, key); 
  41.  
  42.     /* return the (unchanged) node pointer */
  43.     return node; 
  44. } 
  45.  
  46.  
  47. struct node * minValueNode(struct node* node) 
  48. { 
  49.     struct node* current = node; 
  50.  
  51.     /* loop down to find the leftmost leaf */
  52.     while (current->left != NULL) 
  53.         current = current->left; 
  54.  
  55.     return current; 
  56. } 
  57.  
  58.  
  59. struct node* deleteNode(struct node* root, int key) 
  60. { 
  61.     // base case 
  62.     if (root == NULL) return root; 
  63.  
  64.     // If the key to be deleted is smaller than the root's key, 
  65.     // then it lies in left subtree 
  66.     if (key < root->key) 
  67.         root->left = deleteNode(root->left, key); 
  68.  
  69.     // If the key to be deleted is greater than the root's key, 
  70.     // then it lies in right subtree 
  71.     else if (key > root->key) 
  72.         root->right = deleteNode(root->right, key); 
  73.  
  74.     // if key is same as root's key, then This is the node 
  75.     // to be deleted 
  76.     else
  77.     { 
  78.         // node with only one child or no child 
  79.         if (root->left == NULL) 
  80.         { 
  81.             struct node *temp = root->right; 
  82.             free(root); 
  83.             return temp; 
  84.         } 
  85.         else if (root->right == NULL) 
  86.         { 
  87.             struct node *temp = root->left; 
  88.             free(root); 
  89.             return temp; 
  90.         } 
  91.  
  92.         // node with two children: Get the inorder successor (smallest 
  93.         // in the right subtree) 
  94.         struct node* temp = minValueNode(root->right); 
  95.  
  96.         // Copy the inorder successor's content to this node 
  97.         root->key = temp->key; 
  98.  
  99.         // Delete the inorder successor 
  100.         root->right = deleteNode(root->right, temp->key); 
  101.     } 
  102.     return root; 
  103. } 
  104.  
  105. // Driver Program to test above functions 
  106. int main() 
  107. { 
  108.  
  109.     struct node *root = NULL; 
  110.     root = insert(root, 50); 
  111.     root = insert(root, 30); 
  112.     root = insert(root, 20); 
  113.     root = insert(root, 40); 
  114.     root = insert(root, 70); 
  115.     root = insert(root, 60); 
  116.     root = insert(root, 80); 
  117.  
  118.     printf("Inorder traversal of the given tree \n"); 
  119.     inorder(root); 
  120.  
  121.     printf("\nDelete 20\n"); 
  122.     root = deleteNode(root, 20); 
  123.     printf("Inorder traversal of the modified tree \n"); 
  124.     inorder(root); 
  125.  
  126.     printf("\nDelete 30\n"); 
  127.     root = deleteNode(root, 30); 
  128.     printf("Inorder traversal of the modified tree \n"); 
  129.     inorder(root); 
  130.  
  131.     printf("\nDelete 50\n"); 
  132.     root = deleteNode(root, 50); 
  133.     printf("Inorder traversal of the modified tree \n"); 
  134.     inorder(root); 
  135.  
  136.     return 0; 
  137. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of the given tree 
20 30 40 50 60 70 80 
Delete 20
Inorder traversal of the modified tree 
30 40 50 60 70 80 
Delete 30
Inorder traversal of the modified tree 
40 50 60 70 80 
Delete 50
Inorder traversal of the modified tree 
40 60 70 80
https://ideone.com/93ercY
language:
C (gcc 8.3)
created:
5 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!