fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Binary Search Tree [2]
  4. //
  5. //  Created by Himanshu on 16/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. struct node {
  12.     int info = 0;
  13.     struct node *left, *right, *parent;
  14. };
  15. typedef struct node Node;
  16.  
  17. node* newNode(int data, Node *par)
  18. {
  19.     node* Node = new node();
  20.     Node->info = data;
  21.     Node->left = NULL;
  22.     Node->right = NULL;
  23.     Node->parent = par;
  24.  
  25.     return(Node);
  26. }
  27.  
  28. Node* insert (Node *root, int n, Node *par) {
  29.     if (root == NULL) {
  30.         root = newNode(n, par);
  31.     } else {
  32.         if (root->info > n) {
  33.             par = root;
  34.             root->left = insert (root->left, n, par);
  35.         } else {
  36.             par = root;
  37.             root->right = insert (root->right, n, par);
  38.         }
  39.     }
  40.     return root;
  41. }
  42.  
  43. Node* search (Node *root, int n) {
  44.     if (root == NULL || root->info == n) {
  45.         return root;
  46.     } else {
  47.         if (root->info > n) {
  48.             return search (root->left, n);
  49.         } else {
  50.             return search (root->right, n);
  51.         }
  52.     }
  53. }
  54.  
  55. Node* findMinimum (Node *root) {
  56.     while (root->left != NULL) {
  57.         root = root->left;
  58.     }
  59.     return root;
  60. }
  61.  
  62. Node* findMaximum (Node *root) {
  63.     while (root->right != NULL) {
  64.         root = root->right;
  65.     }
  66.     return root;
  67. }
  68.  
  69. Node* findSuccessor (Node *root) {
  70.     if (root->right != NULL) {
  71.         return findMinimum(root->right);
  72.     }
  73.     Node* y = root->parent;
  74.     while (y != NULL && root == y->right) {
  75.         root = y;
  76.         y = y->parent;
  77.     }
  78.     return y;
  79. }
  80.  
  81. Node* deleteNode (Node *root, Node *x) {
  82.     Node *par = root->parent;
  83.  
  84.     if (x->left != NULL && x->right != NULL) {
  85.         Node* z = findSuccessor(x);
  86.         x->info = z->info;
  87.         x = z;
  88.     }
  89.  
  90.     par = x->parent;
  91.  
  92.     if (x->left != NULL) {
  93.         if (par) {
  94.             if (par->left == x) {
  95.                 par->left = x->left;
  96.             } else {
  97.                 par->right = x->left;
  98.             }
  99.         } else {
  100.             root = par->left;
  101.         }
  102.         // To prevent memory leak
  103.         delete (x);
  104.     } else if (x->right != NULL) {
  105.         if (par) {
  106.             if (par->left == x) {
  107.                 par->left = x->right;
  108.             } else {
  109.                 par->right = x->right;
  110.             }
  111.         } else {
  112.             root = par->right;
  113.         }
  114.         // To prevent memory leak
  115.         delete (x);
  116.     } else {
  117.         if (par) {
  118.             if (par->left == x) {
  119.                 par->left = NULL;
  120.             } else {
  121.                 par->right = NULL;
  122.             }
  123.         } else {
  124.             root = NULL;
  125.         }
  126.         // To prevent memory leak
  127.         delete (x);
  128.     }
  129.  
  130.     return root;
  131. }
  132.  
  133. int main() {
  134.     Node *root = newNode(5, NULL);
  135.     root = insert(root, 3, NULL);
  136.     root = insert(root, 2, NULL);
  137.     root = insert(root, 4, NULL);
  138.     root = insert(root, 7, NULL);
  139.  
  140.     //Searching 4 in the tree
  141.     if (search (root, 4)) {
  142.         cout<<"4 is present in the BST"<<endl;
  143.     } else {
  144.         cout<<"4 is not in the BST"<<endl;
  145.     }
  146.  
  147.     //Searching parent of node 3 in the tree
  148.     Node *node = search (root, 3);
  149.     if (node->parent) {
  150.         cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
  151.     } else {
  152.         cout<<"Parent of node is NULL"<<endl;
  153.     }
  154.  
  155.     //Searching successor of node 2 in the tree
  156.     node = search (root, 2);
  157.     if (node) {
  158.         cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  159.     } else {
  160.         cout<<"Successor of node 2 is NULL"<<endl;
  161.     }
  162.  
  163.     //Deleting node 3 in the tree
  164.     cout<<"Deleting node 3"<<endl;
  165.     root = deleteNode(root, search (root, 3));
  166.  
  167.     // Checking if node 3 exists in the tree
  168.     if (search (root, 3)) {
  169.         cout<<"3 is present in the BST"<<endl;
  170.     } else {
  171.         cout<<"3 is not in the BST"<<endl;
  172.     }
  173.  
  174.     //Searching successor of node 2 in the tree
  175.     node = search (root, 2);
  176.     if (node) {
  177.         cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  178.     } else {
  179.         cout<<"Successor of node 2 is NULL"<<endl;
  180.     }
  181.  
  182.     //Searching successor of node 4 in the tree
  183.     node = search (root, 4);
  184.     if (node) {
  185.         cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
  186.     } else {
  187.         cout<<"Successor of node 4 is NULL"<<endl;
  188.     }
  189.  
  190.     return 0;
  191. }
  192.  
Success #stdin #stdout 0.01s 5484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 is present in the BST
Parent of node 3 is 5
Successor of node 2 is 3
Deleting node 3
3 is not in the BST
Successor of node 2 is 4
Successor of node 4 is 5
https://ideone.com/GU0vlP
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years 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!