fork download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. using namespace std;
  4.  
  5. template <class T>
  6. struct Node {
  7.     T value;
  8.     Node *left;
  9.     Node *right;
  10.  
  11.     Node(T val) {
  12.         this->value = val;
  13.     }
  14.  
  15.     Node(T val, Node<T> left, Node<T> right) {
  16.         this->value = val;
  17.         this->left = left;
  18.         this->right = right;
  19.     }
  20. };
  21.  
  22. template <class T>
  23. class BST {
  24.  
  25.     private:
  26.     Node<T> *root;
  27.  
  28.     void addHelper(Node<T> *root, T val) {
  29.         if (root->value > val) {
  30.             if (!root->left) {
  31.                 root->left = new Node<T>(val);
  32.             } else {
  33.                 addHelper(root->left, val);
  34.             }
  35.         } else {
  36.             if (!root->right) {
  37.                 root->right = new Node<T>(val);
  38.             } else {
  39.                 addHelper(root->right, val);
  40.             }
  41.         }
  42.     }
  43.  
  44.     void printHelper(Node<T> *root) {
  45.         if (!root) return;
  46.         printHelper(root->left);
  47.         cout<<root->value<<' ';
  48.         printHelper(root->right);
  49.     }
  50.  
  51.     int nodesCountHelper(Node<T> *root) {
  52.         if (!root) return 0;
  53.         else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right);
  54.     }
  55.  
  56.     int heightHelper(Node<T> *root) {
  57.         if (!root) return 0;
  58.         else return 1 + max(heightHelper(root->left), heightHelper(root->right));
  59.     }
  60.  
  61.     void printMaxPathHelper(Node<T> *root) {
  62.         if (!root) return;
  63.         cout<<root->value<<' ';
  64.         if (heightHelper(root->left) > heightHelper(root->right)) {
  65.             printMaxPathHelper(root->left);
  66.         } else {
  67.             printMaxPathHelper(root->right);
  68.         }
  69.     }
  70.  
  71.     bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
  72.         if (!current) return false;
  73.         if (current->value == value) {
  74.             if (current->left == NULL || current->right == NULL) {
  75.                 Node<T>* temp = current->left;
  76.                 if (current->right) temp = current->right;
  77.                 if (parent) {
  78.                     if (parent->left == current) {
  79.                         parent->left = temp;
  80.                     } else {
  81.                         parent->right = temp;
  82.                     }
  83.                 } else {
  84.                     this->root = temp;
  85.                 }
  86.             } else {
  87.                 Node<T>* validSubs = current->right;
  88.                 while (validSubs->left) {
  89.                     validSubs = validSubs->left;
  90.                 }
  91.                 T temp = current->value;
  92.                 current->value = validSubs->value;
  93.                 validSubs->value = temp;
  94.                 return deleteValueHelper(current, current->right, temp);
  95.             }
  96.             delete current;
  97.             return true;
  98.         }
  99.         return deleteValueHelper(current, current->left, value) ||
  100.                deleteValueHelper(current, current->right, value);
  101.     }
  102.  
  103.     public:
  104.     void add(T val) {
  105.         if (root) {
  106.             this->addHelper(root, val);
  107.         } else {
  108.             root = new Node<T>(val);
  109.         }
  110.     }
  111.  
  112.     void print() {
  113.         printHelper(this->root); 
  114.     }
  115.  
  116.     int nodesCount() {
  117.         return nodesCountHelper(root);
  118.     }
  119.  
  120.     int height() {
  121.         return heightHelper(this->root);
  122.     }
  123.  
  124.     void printMaxPath() {
  125.         printMaxPathHelper(this->root);
  126.     }
  127.  
  128.     bool deleteValue(T value) {
  129.         return this->deleteValueHelper(NULL, this->root, value);
  130.     }
  131. };
  132.  
  133. int main() {
  134.     BST<int> *bst = new BST<int>();
  135.     bst->add(11);
  136.     bst->add(1);
  137.     bst->add(6);
  138.     bst->add(-1);
  139.     bst->add(-10);
  140.     bst->add(100);
  141.     bst->print();
  142.     cout<<endl;
  143.     cout<<"Nodes count: "<<bst->nodesCount();
  144.     cout<<endl;
  145.     cout<<"Height: "<<bst->height();
  146.     cout<<endl;
  147.     cout<<"Max path: ";
  148.     bst->printMaxPath();
  149.     cout<<endl;
  150.     bst->deleteValue(11);
  151.     cout<<"11 removed: ";
  152.     bst->print();
  153.     cout<<endl;
  154.     cout<<"1 removed: ";
  155.     bst->deleteValue(1);
  156.     bst->print();
  157.     cout<<endl;
  158.     cout<<"-1 removed: ";
  159.     bst->deleteValue(-1);
  160.     bst->print();
  161.     cout<<endl;
  162.     cout<<"6 removed: ";
  163.     bst->deleteValue(6);
  164.     bst->print();
  165.     cout<<endl;
  166.     cout<<"-10 removed: ";
  167.     bst->deleteValue(-10);
  168.     bst->print();
  169.     cout<<endl;
  170.     cout<<"100 removed: ";
  171.     bst->deleteValue(100);
  172.     bst->print();
  173.     cout<<endl;
  174.     return 0;
  175. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-10 -1 1 6 11 100 
Nodes count: 6
Height: 4
Max path: 11 1 -1 -10 
11 removed: -10 -1 1 6 100 
1 removed: -10 -1 6 100 
-1 removed: -10 6 100 
6 removed: -10 100 
-10 removed: 100 
100 removed:
https://ideone.com/GleyOt
language:
C++ (gcc 8.3)
created:
7 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!