#include <iostream>
using namespace std; //introduces namespace std
#ifndef _BINARYTREE_H
#define _BINARYTREE_H
template <class T>
class BinaryTree
{
protected:
struct node
{
T data;
node * left;
node * right;
};
typedef node* ptr;
ptr root;
// helper functions
int recurheight(ptr root)const;
// precondition: none
//postcondition : none
//returns height of tree rotted at root
void recurinsert(ptr &root,const T & x);
//precondition: none
// postcondition: inserts x into tree rooted at root
int recursize(ptr root) const;
//precondition: none
//postcondition: none
// returns number of nodes on tree rooted at root
void recurpreorder(ptr root);
//precondition : none
// postcondition : preorder traverses the tree rooted at root
void recurinorder(ptr root);
//precondition : none
// postcondition : inorder traverses the tree rooted at root
void recurpostorder(ptr root);
//precondition : none
// postcondition : postorder traverses the tree rooted at root
void recurclear(ptr &root);
//precondition: none
//postcondition : removes all nodes from tree rooted at root
ptr recurcopy(ptr root);
//precondition : none
//postcondition: the tree rooted at root is copied
// returns : a pointer to the root of the new copy
public:
BinaryTree();
// constructor : makes empty tree
~BinaryTree();
//destructor
BinaryTree(const BinaryTree & x);
//copy constructor
bool empty()const;
//precondition: none
//postcondition : none
//returns true if tree is empty
void preorder( );
// precondition none
//postcondition :
// traverses tree root->left->right
void inorder ();
// precondition none
//postcondition:
// traverses tree left->root->right
void postorder ();
// precondition none
//postcondition:
// traverses tree left->right->root
int size() const;
//precondition : none
//postcondition : none
//returns the number of nodes
int height() const;
//precondition : none
//postcondition : none
// returns height of tree (empty tree height 0)
void insert(const T& x);
//precondition: none
//postcondition : inserts x into tree
void clear();
//precondition : none
//postcondition : All nodes of tree are removed
};
template<class T>
BinaryTree<T>::BinaryTree()
{ root = NULL;
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
clear();
}
template <class T>
BinaryTree<T>::ptr BinaryTree<T>::recurcopy(ptr root)
{
if (root==NULL)
return NULL;
ptr temp = new node;
temp ->data = root ->data;
temp->left = recurcopy(root->left);
temp->right = recurcopy(root->right);
return temp;
}
template <class T>
BinaryTree<T>::BinaryTree(const BinaryTree<T> &x)
{
root= recurcopy(x.root);
}
template<class T>
bool BinaryTree<T>::empty()const
{
return root == NULL;
}
template <class T>
int BinaryTree<T>::recurheight(ptr root)const
{
if (root == NULL)
return -1 ;
else
{
int lefttree = recurheight(root->left);
int righttree = recurheight(root->right);
if (lefttree > righttree)
return lefttree + 1;
else return righttree + 1;
}
}
template <class T>
int BinaryTree<T>::height()const
{
return recurheight(root);
}
template <class T>
void BinaryTree<T>::recurinsert(ptr &root,const T & x)
{
if (root == NULL)
{
root= new node;
root ->left = NULL;
root ->right = NULL;
root ->data = x;
}
else
{
if (recurheight(root->right) < recurheight(root->left))
recurinsert(root->right,x);
else
recurinsert(root->left,x);
}
}
template< class T>
void BinaryTree<T>::insert(const T& x)
{
recurinsert(root,x);
}
template <class T>
int BinaryTree<T>::recursize(ptr root) const
{
if (root ==NULL)
return 0;
else
return recursize(root->left) + recursize(root->right) + 1;
}
template <class T>
int BinaryTree<T>::size()const
{
return recursize(root);
}
template<class T>
void BinaryTree<T>::recurpreorder(ptr root)
{
if( root != NULL)
{
cout<<(root->data)<<endl;
recurpreorder (root->left);
recurpreorder(root->right);
}
}
template<class T>
void BinaryTree<T>::preorder()
{
recurpreorder(root);
}
template<class T>
void BinaryTree<T>::recurinorder(ptr root)
{
if( root != NULL)
{
recurinorder (root->left);
cout<<(root->data)<<endl;
recurinorder(root->right);
}
}
template<class T>
void BinaryTree<T>::inorder()
{
recurinorder(root);
}
template<class T>
void BinaryTree<T>::recurpostorder(ptr root)
{
if( root != NULL)
{
recurpostorder (root->left);
recurpostorder(root->right);
cout<<(root->data)<<endl;
}
}
template<class T>
void BinaryTree<T>::postorder()
{
recurpostorder(root);
}
template<class T>
void BinaryTree<T>::recurclear(ptr &root)
{
// ptr temp = root;
if(root != NULL)
{
recurclear(root->left);
recurclear(root->right);
delete root;
root = NULL;
}
}
template<class T>
void BinaryTree<T>::clear()
{
recurclear(root);
}
#endif