fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class BinarySearchTree {
  6.  
  7.       struct Node {
  8.  
  9.              int data;
  10.  
  11.              Node *left;
  12.  
  13.              Node *right;
  14.       };
  15.  
  16.       Node *root;
  17.  
  18.       Node *insert( int value, Node *t) {
  19.  
  20.             if(t == NULL) {
  21.  
  22.                t = new Node;
  23.  
  24.                t->data = value;
  25.  
  26.                t->left = t->right = NULL;
  27.  
  28.             } else if( value < t->data ) {
  29.  
  30.                t->left = insert( value, t->left );
  31.  
  32.             } else if( value > t->data ) {
  33.  
  34.                t->right = insert(value, t->right);
  35.             }
  36.  
  37.           return t;
  38.       }
  39.  
  40.       Node *findMin(Node *t) {
  41.  
  42.            if(t == NULL) {
  43.  
  44.               return NULL;
  45.  
  46.            } else if( t-> left == NULL ) {
  47.  
  48.               return t;
  49.  
  50.            } else {
  51.  
  52.              return findMin( t->left );
  53.            }
  54.       }
  55.  
  56.       Node *findMax(Node *t) {
  57.  
  58.            if(t == NULL) {
  59.  
  60.               return NULL;
  61.  
  62.            } else if( t-> right == NULL ) {
  63.  
  64.               return t;
  65.  
  66.            } else {
  67.  
  68.              return findMax( t->right );
  69.            }
  70.       }
  71.  
  72.       Node* remove(int value, Node *t) {
  73.  
  74.             Node *temp;
  75.  
  76.             if(t == NULL) {
  77.  
  78.                return NULL;
  79.  
  80.             } else if(value < t->data) {
  81.  
  82.                t->left = remove(value, t->left);
  83.  
  84.             } else if(value > t->data) {
  85.  
  86.               t->right = remove(value, t->right);
  87.  
  88.             } else if(t->left != NULL && t->right != NULL) {
  89.  
  90.                 temp = findMin(t->right);
  91.  
  92.                 t->data = temp->data;
  93.  
  94.                 t->right = remove(t->data, t->right);
  95.  
  96.             } else {
  97.  
  98.                 temp = t;
  99.  
  100.                 if(t->left == NULL) {
  101.  
  102.                    t = t->right;
  103.  
  104.                 } else if(t->right == NULL) {
  105.  
  106.                    t = t->left;
  107.                 }
  108.  
  109.                 delete temp;
  110.             }
  111.  
  112.             return t;
  113.       }
  114.  
  115.       void inorder(Node *t) {
  116.  
  117.            if(t == NULL) return;
  118.  
  119.            inorder(t->left);
  120.  
  121.            cout<<t->data<<" ";
  122.  
  123.            inorder(t->right);
  124.       }
  125.  
  126.       bool find(int value, Node *t) {
  127.  
  128.            if(t == NULL) {
  129.              return false;
  130.            } else if(value < t->data) {
  131.              return find(value, t->left);
  132.            } else if(value > t->data) {
  133.              return find(value, t->right);
  134.            } else {
  135.              return true;
  136.            }
  137.       }
  138.  
  139.       public:
  140.  
  141.          //constructor
  142.          BinarySearchTree() {
  143.  
  144.              root = NULL;
  145.          }
  146.  
  147.          //destructor
  148.          ~BinarySearchTree() {
  149.          }
  150.  
  151.          void insert(int value) {
  152.  
  153.              root = insert(value, root);
  154.          }
  155.  
  156.          void remove(int value) {
  157.  
  158.              root = remove(value, root);
  159.          }
  160.  
  161.          bool search( int value ) {
  162.  
  163.               return find(value, root);
  164.          }
  165.  
  166.          void display() {
  167.  
  168.               inorder( root );
  169.  
  170.               cout<<"\n";
  171.          }
  172. };
  173.  
  174. int main(int argc, char const *argv[]) {
  175.  
  176.    BinarySearchTree bst;
  177.  
  178.         bst.insert(-8);
  179.         bst.insert(-71);
  180.         bst.insert(117);
  181.         bst.insert(-1);
  182.         bst.insert(2);
  183.         bst.insert(13);
  184.         bst.insert(7);
  185.         bst.insert(8);
  186.         bst.insert(17);
  187.         bst.display();
  188.         cout<<bst.search(8);
  189.  
  190.   return 0;
  191. }
  192.  
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-71 -8 -1 2 7 8 13 17 117 
1
https://ideone.com/2OuwoN
Binary Search Tree Data Structure in c++
language:
C++ (gcc 8.3)
created:
4 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!