fork download 
  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* createNode (int data, Node *par) {
  18.     Node* newNode = new node();
  19.     newNode->info = data;
  20.     newNode->left = NULL;
  21.     newNode->right = NULL;
  22.     newNode->parent = par;
  23.  
  24.     return (newNode);
  25. }
  26.  
  27.  
  28. Node* insert (Node *root, int n, Node *par) {
  29.  
  30.     if (root == NULL) {
  31.         root = createNode(n, par);
  32.     } else {
  33.         if (root->info > n) {
  34.             par = root;
  35.             root->left = insert (root->left, n, par);
  36.         } else {
  37.             par = root;
  38.             root->right = insert (root->right, n, par);
  39.         }
  40.     }
  41.  
  42.     return root;
  43. }
  44.  
  45.  
  46. Node* search (Node *root, int n) {
  47.  
  48.     if (root == NULL || root->info == n) {
  49.         return root;
  50.     } else {
  51.         if (root->info > n) {
  52.             return search (root->left, n);
  53.         } else {
  54.             return search (root->right, n);
  55.         }
  56.  
  57.     }
  58. }
  59.  
  60.  
  61. Node* findMinimum (Node *root) {
  62.  
  63.     while (root->left != NULL) {
  64.         root = root->left;
  65.     }
  66.  
  67.     return root;
  68. }
  69.  
  70.  
  71. Node* findMaximum (Node *root) {
  72.  
  73.     while (root->right != NULL) {
  74.         root = root->right;
  75.     }
  76.  
  77.     return root;
  78. }
  79.  
  80.  
  81. Node* findSuccessor (Node *root) {
  82.  
  83.     if (root->right != NULL) {
  84.         return findMinimum(root->right);
  85.     }
  86.  
  87.     Node* y = root->parent;
  88.  
  89.     while (y != NULL && root == y->right) {
  90.         root = y;
  91.         y = y->parent;
  92.     }
  93.  
  94.     return y;
  95. }
  96.  
  97.  
  98. Node* deleteNode (Node *root, Node *x) {
  99.     Node *par = x->parent;
  100.  
  101.     if (x->left != NULL && x->right != NULL) {
  102.         Node* z = findSuccessor(x);
  103.         x->info = z->info;
  104.         x = z;
  105.     }
  106.  
  107.     par = x->parent;
  108.  
  109.     if (x->left != NULL) {
  110.  
  111.         if (par) {
  112.             if (par->left == x) {
  113.                 par->left = x->left;
  114.             } else {
  115.                 par->right = x->left;
  116.             }
  117.         } else {
  118.             root = par->left;
  119.         }
  120.  
  121.         // To prevent memory leak
  122.         delete (x);
  123.     } else if (x->right != NULL) {
  124.  
  125.         if (par) {
  126.             if (par->left == x) {
  127.                 par->left = x->right;
  128.             } else {
  129.                 par->right = x->right;
  130.             }
  131.         } else {
  132.             root = par->right;
  133.         }
  134.  
  135.         // To prevent memory leak
  136.         delete (x);
  137.     } else {
  138.  
  139.         if (par) {
  140.             if (par->left == x) {
  141.                 par->left = NULL;
  142.             } else {
  143.                 par->right = NULL;
  144.             }
  145.         } else {
  146.             root = NULL;
  147.         }
  148.  
  149.         // To prevent memory leak
  150.         delete (x);
  151.     }
  152.  
  153.     return root;
  154. }
  155.  
  156.  
  157. int main() {
  158.     Node *root = createNode(5, NULL);
  159.     root = insert(root, 3, NULL);
  160.     root = insert(root, 2, NULL);
  161.     root = insert(root, 4, NULL);
  162.     root = insert(root, 7, NULL);
  163.  
  164.     //Searching 4 in the tree
  165.     if (search (root, 4)) {
  166.         cout<<"4 is present in the BST"<<endl;
  167.     } else {
  168.         cout<<"4 is not in the BST"<<endl;
  169.     }
  170.  
  171.     //Searching parent of node 3 in the tree
  172.     Node *node = search (root, 3);
  173.     if (node->parent) {
  174.         cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
  175.     } else {
  176.         cout<<"Parent of node 3 is NULL"<<endl;
  177.     }
  178.  
  179.     //Searching successor of node 2 in the tree
  180.     node = search (root, 2);
  181.     if (node) {
  182.         cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  183.     } else {
  184.         cout<<"Successor of node 2 is NULL"<<endl;
  185.     }
  186.  
  187.     //Deleting node 3 in the tree
  188.     cout<<"Deleting node 3"<<endl;
  189.     root = deleteNode(root, search (root, 3));
  190.  
  191.     // Checking if node 3 exists in the tree
  192.     if (search (root, 3)) {
  193.         cout<<"3 is present in the BST"<<endl;
  194.     } else {
  195.         cout<<"3 is not in the BST"<<endl;
  196.     }
  197.  
  198.     //Searching successor of node 2 in the tree
  199.     node = search (root, 2);
  200.     if (node) {
  201.         cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  202.     } else {
  203.         cout<<"Successor of node 2 is NULL"<<endl;
  204.     }
  205.  
  206.     //Searching successor of node 4 in the tree
  207.     node = search (root, 4);
  208.     if (node) {
  209.         cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
  210.     } else {
  211.         cout<<"Successor of node 4 is NULL"<<endl;
  212.     }
  213.  
  214.     return 0;
  215. }
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin 
Standard input is empty
stdout 
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/84pqxe
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!