fork download 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4.  
  5. class BTree {
  6.  
  7.   // types:
  8.   protected:
  9.     struct Node {
  10.       int value;
  11.       Node *pLeft, *pRight;
  12.  
  13.       // constructor.
  14.       Node(int value): value(value), pLeft(nullptr), pRight(nullptr) { }
  15.       // destructor.
  16.       virtual ~Node() { delete pLeft; delete pRight; }
  17.       // disabled:
  18.       Node(const Node&) = delete;
  19.       Node& operator=(const Node&) = delete;
  20.  
  21.       // prints node.
  22.       virtual void print(std::ostream &out)
  23.       {
  24.         out << "Node " << value;
  25.       }
  26.     };
  27.  
  28.   // variables:
  29.   protected:
  30.     Node *_pRoot;
  31.  
  32.   // methods:
  33.   public:
  34.     // constructor.
  35.     BTree(): _pRoot(nullptr) { }
  36.     // destructor.
  37.     ~BTree() { delete _pRoot; }
  38.     // disabled:
  39.     BTree(const BTree&) = delete;
  40.     BTree& operator=(const BTree&) = delete;
  41.  
  42.     // inserts a node.
  43.     bool insert(int value) { return insert(_pRoot, value); }
  44.     // prints the tree.
  45.     void print(std::ostream &out, bool inOrder)
  46.     {
  47.       if (_pRoot) {
  48.         if (inOrder) printInfix(out, _pRoot, 0);
  49.         else print(out, _pRoot, 0);
  50.       } else out << "EMPTY." << std::endl;
  51.     }
  52.  
  53.   // internal methods:
  54.   protected:
  55.     // creates and inserts a node.
  56.     bool insert(Node *&pNode, int value);
  57.     // prints a sub-tree.
  58.     void print(std::ostream &out, Node *pNode, int indent);
  59.     // prints a sub-tree in order.
  60.     void printInfix(std::ostream &out, Node *pNode, int indent);
  61.  
  62. };
  63.  
  64. bool BTree::insert(Node *&pNode, int value)
  65. {
  66.   if (!pNode) {
  67.     pNode = new Node(value);
  68.     return true;
  69.   }
  70.   if (value == pNode->value) return false; // ERROR!
  71.   return insert(
  72.     value < pNode->value ? pNode->pLeft : pNode->pRight, value);
  73. }
  74.  
  75. void BTree::print(std::ostream &out, Node *pNode, int indent)
  76. {
  77.   out << std::setw(indent) << "";
  78.   pNode->print(out);
  79.   out << std::endl;
  80.   indent += 2;
  81.   if (pNode->pLeft) print(out, pNode->pLeft, indent);
  82.   if (pNode->pRight) print(out, pNode->pRight, indent);
  83. }
  84.  
  85. void BTree::printInfix(std::ostream &out, Node *pNode, int indent)
  86. {
  87.   if (pNode->pLeft) printInfix(out, pNode->pLeft, indent + 2);
  88.   out << std::setw(indent) << "";
  89.   pNode->print(out);
  90.   out << std::endl;
  91.   if (pNode->pRight) printInfix(out, pNode->pRight, indent + 2);
  92. }
  93.  
  94. class BTree2: public BTree {
  95.   // types:
  96.   protected:
  97.     struct Node: public BTree::Node {
  98.       int height;
  99.  
  100.       // constructor.
  101.       Node(int value, int height):
  102.         BTree::Node(value), height(height)
  103.       { }
  104.       virtual ~Node() = default;
  105.       // disabled:
  106.       Node(const Node&) = delete;
  107.       Node& operator=(const Node&) = delete;
  108.  
  109.       // prints node.
  110.       virtual void print(std::ostream &out)
  111.       {
  112.         out << "Node " << value << " (height: " << height << ")";
  113.       }
  114.     };
  115.  
  116.   // methods:
  117.   public:
  118.     // constructor.
  119.     BTree2(): BTree() { }
  120.     // destructor.
  121.     ~BTree2() = default;
  122.     // disabled:
  123.     BTree2(const BTree2&) = delete;
  124.     BTree2& operator=(const BTree2&) = delete;
  125.  
  126.     // inserts a node.
  127.     bool insert(int value)
  128.     {
  129.       return insert((Node*&)_pRoot, value, 0);
  130.     }
  131.  
  132.   // internal methods:
  133.   protected:
  134.     // creates and inserts a node.
  135.     bool insert(Node *&pNode, int value, int height);
  136. };
  137.  
  138. bool BTree2::insert(Node *&pNode, int value, int height)
  139. {
  140.   if (!pNode) {
  141.     pNode = new Node(value, height);
  142.     return true;
  143.   }
  144.   if (value == pNode->value) return false; // ERROR!
  145.   return insert(
  146.     (Node*&)(value < pNode->value ? pNode->pLeft : pNode->pRight),
  147.     value, pNode->height + 1);
  148. }
  149.  
  150. // main function
  151. int main()
  152. {
  153.   // some test data
  154.   int data[] = { 3, 7, 21, 2, 12, 1, 104, 13 };
  155.   enum { nData = sizeof data / sizeof data[0] };
  156.   // binary tree
  157.   { std::cout << "Binary Tree:" << std::endl;
  158.     BTree bTree;
  159.     std::cout << "Build..." << std::endl;
  160.     for (int value : data) bTree.insert(value);
  161.     std::cout << "Print Hierarchy..." << std::endl;
  162.     bTree.print(std::cout, false);
  163.     std::cout << "Print Sorted..." << std::endl;
  164.     bTree.print(std::cout, true);
  165.     std::cout << "Destroy..." << std::endl;
  166.     std::cout << std::endl;
  167.   }
  168.   // derived binary tree
  169.   { std::cout << "Derived Binary Tree:" << std::endl;
  170.     BTree2 bTree;
  171.     std::cout << "Build..." << std::endl;
  172.     for (int value : data) bTree.insert(value);
  173.     std::cout << "Print Hierarchy..." << std::endl;
  174.     bTree.print(std::cout, false);
  175.     std::cout << "Print Sorted..." << std::endl;
  176.     bTree.print(std::cout, true);
  177.     std::cout << "Destroy..." << std::endl;
  178.     std::cout << std::endl;
  179.   }
  180.   // done
  181.   return 0;
  182. }
  183.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin 
Standard input is empty
stdout 
Binary Tree:
Build...
Print Hierarchy...
Node 3
  Node 2
    Node 1
  Node 7
    Node 21
      Node 12
        Node 13
      Node 104
Print Sorted...
    Node 1
  Node 2
Node 3
  Node 7
      Node 12
        Node 13
    Node 21
      Node 104
Destroy...

Derived Binary Tree:
Build...
Print Hierarchy...
Node 3 (height: 0)
  Node 2 (height: 1)
    Node 1 (height: 2)
  Node 7 (height: 1)
    Node 21 (height: 2)
      Node 12 (height: 3)
        Node 13 (height: 4)
      Node 104 (height: 3)
Print Sorted...
    Node 1 (height: 2)
  Node 2 (height: 1)
Node 3 (height: 0)
  Node 7 (height: 1)
      Node 12 (height: 3)
        Node 13 (height: 4)
    Node 21 (height: 2)
      Node 104 (height: 3)
Destroy...
https://ideone.com/3AEG0P
language:
C++ (gcc 8.3)
created:
8 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!