fork download
copy 
  1. /**
  2.  *  Binary Search Tree - BST non-recursive solution
  3.  *  -----------------------------------------------
  4.  *
  5.  *  Methods:
  6.  *  -------
  7.  *  add
  8.  *  search
  9.  *  delete
  10.  *   
  11.  *  inorder
  12.  *  postorder
  13.  *  inorder
  14.  */
  15.  
  16. #include <stdio.h>
  17. #include <malloc.h>
  18.  
  19. struct Node {
  20.  
  21.        int data;
  22.        struct Node *left;
  23.        struct Node *right;
  24. };
  25.  
  26. struct Node *root=NULL;
  27.  
  28. void add(int);
  29. void inorder(struct Node*);
  30. void preorder(struct Node*);
  31. void postorder(struct Node*);
  32. int  search(int);
  33. void delete(int);
  34.  
  35. int main() {
  36.     int node;
  37.     int whatsearch; 
  38.  
  39.     add(8);
  40.     add(3);
  41.     add(10);
  42.     add(1);
  43.     add(2);
  44.     add(14);
  45.     add(11);
  46.     add(6);
  47.     add(4);
  48.     add(7);     
  49.  
  50.     postorder(root);
  51.  
  52.     printf("\nNode to search=");
  53.     scanf("%d",&whatsearch);
  54.  
  55.     if(search(whatsearch)) {
  56.  
  57.        printf("The node %d exists in Tree \n",whatsearch);
  58.  
  59.     } else {
  60.  
  61.        printf("The node %d not exist in Tree \n",whatsearch);
  62.     }
  63.  
  64.     printf("Give me a node to remove NODE=");
  65.     scanf("%d",&node);
  66.  
  67.     printf("\nTrying to remove the node=%d", node);
  68.     delete(node);
  69.  
  70.     //Traversals
  71.     printf("\n\nPostorder:\n");
  72.     postorder(root);    
  73.     printf("\nInorder:\n");
  74.     inorder(root);    
  75.     printf("\nPreorder:\n");
  76.     preorder(root);    
  77.  
  78.  
  79.     //return SUCCESS to the Operating System
  80.     return (0);  
  81. };
  82.  
  83. void add (int val) {
  84.  
  85.      struct Node *curr, *new;
  86.  
  87.      if(root == NULL) {
  88.  
  89.         root = (struct Node*) malloc(sizeof(struct Node));
  90.  
  91.         root->data = val;
  92.  
  93.         root->left = NULL;
  94.  
  95.         root->right = NULL;
  96.  
  97.      } else {
  98.  
  99.        curr = root;
  100.  
  101.        while(1) {
  102.  
  103.             if(val < curr->data) {
  104.  
  105.                if(curr->left) {
  106.  
  107.                  curr = curr->left;
  108.  
  109.                } else {
  110.  
  111.                  new = (struct Node*) malloc(sizeof(struct Node));             
  112.  
  113.                  new->data = val;
  114.  
  115.                  new->left = NULL;
  116.  
  117.                  new->right = NULL; 
  118.  
  119.                  curr->left = new;
  120.  
  121.                  break; 
  122.                }
  123.  
  124.             } else {
  125.  
  126.                if(curr->right) {
  127.  
  128.                  curr = curr->right;
  129.  
  130.                } else {
  131.  
  132.                  new = (struct Node*) malloc(sizeof(struct Node));             
  133.  
  134.                  new->data = val;
  135.  
  136.                  new->left = NULL;
  137.  
  138.                  new->right = NULL; 
  139.  
  140.                  curr->right = new;
  141.  
  142.                  break; 
  143.                }
  144.             } 
  145.        }     
  146.      }
  147. };
  148.  
  149. void postorder(struct Node* node) {
  150.  
  151.     if(node->left) {
  152.  
  153.        postorder(node->left);
  154.     } 
  155.  
  156.     if(node->right) {
  157.  
  158.        postorder(node->right);
  159.     } 
  160.  
  161.     printf("%d ",node->data);   
  162.  
  163. };
  164.  
  165. void inorder(struct Node* node) {
  166.  
  167.     if(node->left) {
  168.  
  169.        inorder(node->left);
  170.     } 
  171.  
  172.     printf("%d ",node->data);   
  173.  
  174.     if(node->right) {
  175.  
  176.        inorder(node->right);
  177.     } 
  178.  
  179. };
  180.  
  181.  
  182. void preorder(struct Node* node) {
  183.  
  184.     printf("%d ",node->data);   
  185.  
  186.     if(node->left) {
  187.  
  188.        preorder(node->left);
  189.     } 
  190.  
  191.     if(node->right) {
  192.  
  193.        preorder(node->right);
  194.     } 
  195. };
  196.  
  197.  
  198. int search(int val) {
  199.  
  200.     struct Node *curr = root;
  201.  
  202.     int found = 0;
  203.  
  204.     while(!found && curr) {
  205.  
  206.          if(curr->data == val) {
  207.  
  208.             found = 1;
  209.  
  210.          } else {
  211.  
  212.             if(val < curr->data) {
  213.  
  214.                curr = curr->left;
  215.  
  216.             } else {
  217.  
  218.                curr = curr->right;
  219.             }  
  220.  
  221.          } 
  222.     }       
  223.  
  224.    return found;
  225. }
  226.  
  227. void delete(int val) {
  228.  
  229.     struct Node *curr = root, *parrent, *next;
  230.  
  231.     int found = 0;
  232.  
  233.     while(!found && curr) {
  234.  
  235.          if(curr->data == val) {
  236.  
  237.             found = 1;
  238.  
  239.          } else {
  240.  
  241.             if(val < curr->data) {
  242.  
  243.                parrent = curr;
  244.  
  245.                curr = curr->left;
  246.  
  247.             } else {
  248.  
  249.                parrent = curr;
  250.  
  251.                curr = curr->right;
  252.             }  
  253.  
  254.          } 
  255.     }       
  256.  
  257.  
  258.     if( found ) {
  259.  
  260.        if(curr->left == NULL && curr->right == NULL) {
  261.  
  262.           if(parrent->data < curr->data) parrent->right = NULL;
  263.  
  264.                            else parrent->left = NULL;
  265.  
  266.           free(curr);
  267.  
  268.        } else if(curr->left == NULL && curr->right != NULL) {
  269.  
  270.           //for debug
  271.           //printf("node=%d parent=%d",curr->data, parrent->data);  
  272.  
  273.           next = curr->right;
  274.  
  275.           if(parrent->data < curr->data) parrent->right = next;
  276.  
  277.                            else parrent->left = next;
  278.           free(curr);
  279.  
  280.        } else if(curr->left != NULL && curr->right == NULL) {
  281.  
  282.          //for debug 
  283.          //printf("node=%d parent=%d",curr->data, parrent->data);
  284.  
  285.          next = curr->left;
  286.  
  287.          if(parrent->data < curr->data) parrent->right = next;
  288.  
  289.                                  else   parrent->left = next;
  290.          free(curr);
  291.  
  292.        } else if(curr->left != NULL && curr->right != NULL) {
  293.  
  294.                struct Node *p,*c;
  295.  
  296.                //if the node has left subtree and rightsubtree then trying to find out the mostly right from left subtree
  297.                c = curr->left;
  298.  
  299.                while(c->right) {
  300.  
  301.                      p = c;
  302.  
  303.                      c=c->right;
  304.                }
  305.  
  306.                //for debug
  307.                //printf("node=%d parrent=%d",c->data,p->data);
  308.  
  309.                curr->data = c->data;
  310.  
  311.                next = c->left;
  312.  
  313.                if(p->data < c->data) p->right = next;
  314.                             else     p->left = next;
  315.  
  316.                free(c);  
  317.        }
  318.  
  319.  
  320.     printf("\nThe node is removed\n");        
  321.  
  322.     } else {
  323.  
  324.        printf("\nNode not found!");
  325.     } 
  326. }
Success #stdin #stdout 0s 5304KB
comments ()
stdin
copy 
7
7
stdout
copy 
2 1 4 7 6 3 11 14 10 8 
Node to search=The node 7 exists in Tree 
Give me a node to remove NODE=
Trying to remove the node=7
The node is removed


Postorder:
2 1 4 6 3 11 14 10 8 
Inorder:
1 2 3 4 6 8 10 11 14 
Preorder:
8 3 1 2 6 4 10 14 11
https://ideone.com/aUZX9H
BST iterative
language:
C (gcc 8.3)
created:
326 days ago
visibility:
secret

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!