fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. struct Node 
  5. {
  6.     int id;
  7.     std::string data;
  8.     Node *left;
  9.     Node *right;
  10.  
  11.     Node(int n) 
  12.         : id(n)
  13.         , data(std::to_string(n))
  14.         , left(nullptr)
  15.         , right(nullptr)
  16.     {
  17.         std::cout << "Creating Node(" << id << ")\n";
  18.     }
  19.  
  20.     ~Node()
  21.     {
  22.         std::cout << "Destroying Node(" << id << ")\n";
  23.     }
  24. };
  25.  
  26. class BST
  27. {
  28. private:
  29.     Node *root;
  30.  
  31. protected:
  32.     // provided for recursion. 
  33.     std::string getEntry(Node const *p, int id) const
  34.     {
  35.         // nowhere else to go; return empty string
  36.         if (p == nullptr)
  37.             return "";
  38.  
  39.         // walk down left tree if needed
  40.         if (id < p->id)
  41.             return getEntry(p->left, id);
  42.  
  43.         // walk down right tree if needed
  44.         if (p->id < id)
  45.             return getEntry(p->right, id);
  46.  
  47.         // neither left nor right needed; must be this.
  48.         return p->data;
  49.     }
  50.  
  51.     // provided for recursion
  52.     void addNode(Node *& rp, int id)
  53.     {
  54.         if (rp == nullptr)
  55.         {
  56.             rp = new Node(id);
  57.             return;
  58.         }
  59.  
  60.         if (id < rp->id)
  61.             addNode(rp->left, id);
  62.         else if (rp->id < id) // note: remove if-condition to allow duplicate insertions
  63.             addNode(rp->right, id);
  64.     }
  65.  
  66.     // provided for recursion
  67.     void clear(Node *& rp)
  68.     {
  69.         if (rp)
  70.         {
  71.             clear(rp->left);
  72.             clear(rp->right);
  73.             delete rp;
  74.             rp = nullptr;
  75.         }
  76.     }
  77.  
  78. public:
  79.     BST() : root(nullptr) {}
  80.  
  81.     // delete these for rule of three/five compliance
  82.     BST(BST const&) = delete;
  83.     BST& operator =(BST const&) = delete;
  84.  
  85.     virtual ~BST()
  86.     {
  87.         clear(root);
  88.     }
  89.  
  90.     // invokes the recursive member with root pointer as starting point.
  91.     void addNode(int id)
  92.     {
  93.         addNode(root, id);
  94.     }
  95.  
  96.     // invokes the recursive member with root pointer as starting point.
  97.     std::string getEntry(int id) const
  98.     {
  99.         return getEntry(root, id);
  100.     }
  101. };
  102.  
  103.  
  104. int main()
  105. {
  106.     BST bst;
  107.  
  108.     // add some sample numbers
  109.     bst.addNode(42);
  110.     bst.addNode(5);
  111.     bst.addNode(100);
  112.     bst.addNode(16);
  113.  
  114.     // tests:
  115.     std::cout << bst.getEntry(1) << '\n';   // blank line
  116.     std::cout << bst.getEntry(5) << '\n';   // 5
  117.     std::cout << bst.getEntry(6) << '\n';   // blank line
  118.     std::cout << bst.getEntry(41) << '\n';  // blank line
  119.     std::cout << bst.getEntry(42) << '\n';  // 42
  120.     std::cout << bst.getEntry(43) << '\n';  // blank line
  121.     std::cout << bst.getEntry(99) << '\n';  // blank line
  122.     std::cout << bst.getEntry(100) << '\n'; // 100
  123.     std::cout << bst.getEntry(101) << '\n'; // blank line
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Creating Node(42)
Creating Node(5)
Creating Node(100)
Creating Node(16)

5


42


100

Destroying Node(16)
Destroying Node(5)
Destroying Node(100)
Destroying Node(42)
https://ideone.com/PaBdoV
language:
C++14 (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!