Advertisement
Shailrshah

Binary Search Tree Insertion & Deletion

Aug 31st, 2013
325
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.36 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. struct tree{
  4.     int data;
  5.     struct tree *left,*right;
  6. }*root = NULL;
  7. void insert(int val){
  8.     struct tree *newNode = (struct tree*) malloc(sizeof(struct tree));
  9.     newNode->data = val; newNode->right = newNode->left = NULL;
  10.     if(!root) root = newNode;
  11.     else{
  12.         struct tree *help = root,*previous = NULL;
  13.         while(help){
  14.             previous = help;
  15.             if(val < help->data) help = help ->left;
  16.             else if(val > help->data) help = help->right;
  17.             else{
  18.                 printf("\nDublicate values not allowed.\n");
  19.                 return;
  20.             }
  21.         }
  22.         if(val > previous->data)   previous->right = newNode;
  23.         else    previous->left = newNode;
  24.     }
  25. }
  26. void eliminate(int value){
  27.     struct tree *help = root, *previous = help;
  28.     while (help){ //start from root, traverse until help becomes null or node's value matches
  29.         if(help->data==value) break;
  30.         previous  = help;
  31.         if (value > help-> data) help = help->right;
  32.         else help = help->left;
  33.     }
  34.     if(!help) printf("Element not found!\n");
  35.     else{
  36.         struct tree *target = help;
  37.         if (!target->left && !target->right) { //if node is a leaf node
  38.             if(target == root)
  39.                 root = NULL;
  40.             else if(previous->left == target) previous->left = NULL;
  41.             else previous->right = NULL;
  42.         }
  43.         else if (!target->left || !target->right) { //if node has one child
  44.             if(target == root){
  45.                 if(target->left)    root = root->left;
  46.                 else root = root->right;
  47.             }
  48.             if(previous->left == target){
  49.                 if(target->left)    previous->left = target->left;
  50.                 else previous->left = target->right;
  51.             }
  52.             else{
  53.                 if(target->left)    previous->right = target->left;
  54.                 else previous->right = target->right;
  55.             }
  56.         }
  57.         else { //if node has 2 children                    
  58.             struct tree* t = target; //t will point to leftmost leaf node of target's right subtree
  59.             t = t->right;
  60.             while(t->left){
  61.                previous = t;
  62.                 t = t->left;
  63.             }
  64.             if(t->right){
  65.                 previous = t;    
  66.                 t = t->right;
  67.             }
  68.             target->data = t->data;
  69.             if(previous->right) previous->right = NULL;
  70.             else previous->left = NULL;
  71.             free(t);
  72.         }
  73.         free(target);
  74.     }
  75. }
  76. void display(struct tree* help){
  77.     if(help){
  78.         display(help->left);
  79.         printf(" |%d| ", help->data);
  80.         display(help->right);
  81.     }
  82.     if(!root)   printf("The tree is empty.\n");
  83. }
  84. int main(){
  85.     int n, choice;
  86.     while(1){
  87.         display(root);
  88.         printf("\n\n1. Insert 2. Delete 3. Exit.\nInput: ");
  89.         scanf("%d", &choice);
  90.         switch(choice){
  91.             case 1: printf("\nInsert: ");
  92.                     scanf("%d",&n);
  93.                     insert(n);
  94.                     break;
  95.             case 2: if(root){
  96.                         printf("\nDelete: ");
  97.                         scanf("%d",&n);
  98.                         eliminate(n);
  99.                     }
  100.                     break;
  101.             case 3: return 0;
  102.         }
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement