fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template <class T>
  4. class BST;
  5.  
  6. template <class T>
  7. class BSTNode {
  8.     T key;
  9.     BSTNode* left;
  10.     BSTNode* right;
  11.  
  12. public:
  13.     BSTNode() : left(nullptr), right(nullptr){}
  14.     BSTNode(const T& el, BSTNode* l = nullptr, BSTNode* r = nullptr) {
  15.         key = el;
  16.         left = l;
  17.         right = r;
  18.     }
  19.     BSTNode* getLeft() const {return left;}
  20.     BSTNode* getRight() const {return right;}
  21.     T& getKey() { return key; }
  22.     friend class BST<T>;
  23. };
  24.  
  25. template <class T>
  26. class BST {
  27. protected:
  28.     BSTNode<T>* root;
  29. public:
  30.     BST() {root = nullptr;}
  31.     void clear() {root = nullptr;}
  32.     bool isEmpty() {return root == nullptr;}
  33.  
  34.     T* search(const T& el) {
  35.         BSTNode<T>* p = root;
  36.         while (p != nullptr) {
  37.             if (p->getKey() == el) {
  38.                 return &(p->key);
  39.             }
  40.             if (p->getKey() < el) {
  41.                 p = p->getRight();
  42.             }else p = p->getLeft();
  43.         }
  44.         return nullptr;
  45.     }
  46.  
  47.     void insert(const T& el) {
  48.         BSTNode<T> *p = root, *prev = nullptr;
  49.  
  50.         //finding a place to insert the new node
  51.         while (p != nullptr) {
  52.             prev = p;
  53.             if (p->key < el) p = p->right;
  54.             else p = p->left;
  55.         }
  56.  
  57.         //inserting the new node
  58.         if (root == nullptr) root = new BSTNode<T>(el);
  59.         else if (prev->key < el) {
  60.             prev->right = new BSTNode<T>(el);
  61.         }else prev->left = new BSTNode<T>(el);
  62.     }
  63. };
  64.  
  65.  
  66.  
  67. int main() {
  68.     BST<int> binary;
  69.     binary.insert(15);
  70.     binary.insert(20);
  71.     int* found = binary.search(15);
  72.     cout << *found;
  73.  
  74.     return 0;
  75. }
  76.  
  77.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
15
https://ideone.com/9QDs61
language:
C++ (gcc 8.3)
created:
11 days 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!