Implement a template binary tree class in C++. A binary tree is composed of nodes each of which has two children, left and right. Each tree has a calculated depth equal to the number of levels required to store the nodes in the tree. For example, a tree of 8 nodes would require 4 levels total, level 0 would have 1 node, level 1 would have 2 nodes (3 total now), level 2 would have 4 nodes (7 total) and the 8th node would land in the 4th level (n=3). The depth is a calculated value, not a stored one.
I was given the .h file and need to implement the code on .cpp file.
#ifndef MY_BTREE_H
#define MY_BTREE_H
// my_btree.h - binary tree class (no balancing)
usingnamespace std;
// forward declaration of classes defined in this header
template <class T> class btree;
template <class T> class node;
template <class T>
class btree
{
public:
// constructors
btree(); // no-arg constructor
btree(const btree & tree); // copy constructor
~btree(); // destructor
// operations
bool empty() const;
int size() const;
T & root() const;
// print in-order traversal of the tree
void print() const;
// insert x into tree (wherever it goes)
void add_element(const T & x);
// calculate height of tree
int height() const;
protected:
node<T> * rootnode;
unsignedint my_size();
// internal methods used recursively
private:
// calculate height of a tree rooted at n
int height(node<T> *n) const;
// print subtree rooted at n (recursive)
void print(node<T> *n);
// insert x in tree rooted at node n (keep in order!)
void insert(node<T> * n, const T & x);
};
template <class T>
class node
{
private:
node(const T & x); // private constructor
T x; // data
node<T> * left; // left child
node<T> * right; // right child
friendclass btree<T>;
};
#include "my_btree.cpp"
#endif
