BinaryTree.h template type class containing functionalities of binary tree

C++ : BinaryTree.h

#include <iostream>
#include <conio.h>
using namespace std;

/*******************************************************************************************************/
/*******************************************************************************************************/
/********************************    Node of Template Type  ********************************************/
/*******************************************************************************************************/
/*******************************************************************************************************/
template<typename T>
class node{
public:
	T data;
	node<T>* left,*right;
	node(T in,node<T>* l=0,node<T>* r=0){
		data=in;
		left=l;
		right=r;
	}
	~node(void){}
};

/*******************************************************************************************************/
/*******************************************************************************************************/
/********************************    Binary BinaryTree Implementation ****************************************/
/*******************************************************************************************************/
/*******************************************************************************************************/

template<typename T>
class BinaryTree{
	/* Declaring Root */
	node<T>* root;
	int size;
	
	/*Private Functions Done By Recursion */
	void _Inorder(node<T>*);
	void _Preorder(node<T>*);
	void _Postorder(node<T>*);
	void _Insert(const T&,node<T>*);
	bool _Search(const T&,node<T>*);
	void _Successor(node<T>*&,node<T>*&);
	bool _DeleteIt(const T&,node<T>*&,node<T>*);
public:
	/*Usable Functions of BinaryTree*/
	BinaryTree(void);
	void RecursiveInsert(const T&);
	void IterativeInsert(const T&);
	bool RecursiveSearch(const T&);
	bool IterativeSearch(const T&);
	bool RecursiveDeleteIt(const T&);
	bool IterativeDeleteIt(const T&);
	bool Update(const T&,const T&);
	void Inorder(void);
	bool GetRootValue(T&);
	~BinaryTree(void);
};


/********************************    All Recursive Fuctions ****************************************/
/***************************************************************************************************/
/***************************************************************************************************/

template<typename T> void BinaryTree<T>::_Inorder(node<T>* r){
	if(r==0){return;}
	_Inorder(r->left);
	cout<<r->data<<"\n";
	_Inorder(r->right);
}
template<typename T> void BinaryTree<T>::_Preorder(node<T>* r){
	if(r==0){return;}
	cout<<r->data<<"\n";
	_Preorder(r->left);
	_Preorder(r->right);
}
template<typename T> void BinaryTree<T>::_Postorder(node<T>* r){
	if(r==0){return;}
	_Postorder(r->left);
	_Postorder(r->right);
	cout<<r->data<<"\n";
}
template<typename T> void BinaryTree<T>::_Insert(const T& t,node<T>* r){
	if(!root){
		root=new node<T>(t);
		size++;
	}else if(r->data>t){
		if(r->left){
			_Insert(t,r->left);
		}else{
			size++;
			r->left=new node<T>(t);
		}
	}else{
		if(r->right){
			_Insert(t,r->right);
		}else{
			size++;
			r->right=new node<T>(t);
		}
	}
}
template<typename T> bool BinaryTree<T>::_Search(const T& t,node<T>* r){
	if(root == NULL || r == NULL){
		return false;
	}else if(r->data>t){
		if(r->data==t){
			return true;
		}
		return _Search(t,r->left);
	}else{
		if(r->data==t){
			return true;
		}
		return _Search(t,r->right);
	}
}
template<typename T> void BinaryTree<T>::_Successor(node<T>*& temp,node<T>*& p){
	if(temp == NULL){
		return;
	}
	p=temp;
	temp=temp->right;
	if(temp == NULL){
		return;
	}
	while(temp->left){
		p=temp;temp=temp->left;
	}
}
template<typename T> bool BinaryTree<T>::_DeleteIt(const T& t,node<T>*& r,node<T>* p){
	if(r == NULL){
		return false;
	}else if(t < r->data){
		return _DeleteIt(t,r->left,r);
	}else if(t > r->data){
		return _DeleteIt(t,r->right,r);
	}else{
		if(r->left == NULL && r->right == NULL){//__________ LEAF
			if(p==NULL){root=0;}
			else{
				if(p->data>t){
					delete p->left;
					p->left=0;
				}
				else{
					delete p->right;
					p->right=0;
				}
			}
			return true;
		}else if(r->left == NULL || r->right == NULL){//____ 1 node BinaryTree
			node<T>* temp=r;
			if(r->left == NULL){//___________________ right subBinaryTree
				if(p==NULL){
					root=r->right;
				}
				else{
					if(p->data  < r->right->data){
						p->right=r->right;
					}
					else{
						p->left=r->right;
					}
				}
			}else{//__________________________ left subBinaryTree
				if(p==NULL){
					root=r->left;
				}
				else{
					if(p->data < r->left->data){
						p->right=r->left;
					}
					else{
						p->left=r->left;
					}
				}
			}
			delete temp;temp=0;
			return true;
		}else{//______________________________ Two Nodes BinaryTree
			node<T>*s=r,*sp=p;
			_Successor(s,sp);
			r->data=s->data;
			return _DeleteIt(s->data,s,sp);
		}
	}
}

/********************************    Public Functions   ********************************************/
/***************************************************************************************************/
/***************************************************************************************************/

template<typename T> BinaryTree<T>::BinaryTree(void){
	size=0;
	root=NULL;
}

template<typename T> void BinaryTree<T>::RecursiveInsert(const T& t){
	_Insert(t,root);
}

template<typename T> void BinaryTree<T>::IterativeInsert(const T& t){
	if(root == NULL){
		root=new node<T>(t);
		size++;
		return;
	}
	node<T>* temp = root,*pre;
	while(temp != NULL){
		
		if(temp->data>t){
			pre=temp;
			temp=temp->left;
		}else{
			pre=temp;
			temp=temp->right;
		}
	}
	if(temp == NULL){
		size++;
		if(pre->data>t){
			pre->left=new node<T>(t);
		}else{
			pre->right=new node<T>(t);
		}
		return;
	}
}

template<typename T> bool BinaryTree<T>::RecursiveSearch(const T& t){
	return _Search(t,root);
}
template<typename T> bool BinaryTree<T>::IterativeSearch(const T& t){
	if(root == NULL){
		return false;
	}
	node<T>* temp = root;
	while(temp != NULL){
		if(temp->data == t){
			return true;
		}
		else if(temp->data > t){
			temp=temp->left;
		}else{
			temp=temp->right;
		}
	}
	return false;
}

template<typename T> bool BinaryTree<T>::RecursiveDeleteIt(const T& t){
	return _DeleteIt(t,root,0);
}

template<typename T> bool BinaryTree<T>::IterativeDeleteIt(const T& t){
	/****ITERATIVE*****/
	bool g = false;
	node<T>* r = root,*p = NULL;
	T var = t;
	while(r != NULL && r->data != t){ //________________ till r is not null or contain address of node which should be deleted
		p = r;
		if(r->data>t){
			r = r->left;
		}else{
			r = r->right;
		}
	}
	if(r == NULL){
		return g;
	}

	do{
		if(r->left == NULL && r->right == NULL){//__________ LEAF
			if(p == NULL){
				root = NULL;
			}
			else{
				if(p->data > var){
					p->left = NULL;
				}
				else{
					p->right = NULL;
				}
			}
			delete r; r=0;
			g = true;
		}else if(r->left == NULL || r->right == NULL){//____ 1 node BinaryTree
			if(r->left == NULL){//___________________ right subBinaryTree
				if(p == NULL){
					root = r->right;
				}
				else{
					if(p->data < r->right->data){
						p->right = r->right;
					}
					else{
						p->left = r->right;
					}
				}
			}else{//__________________________ left subBinaryTree
				if(p == NULL){
					root = r->left;
				}
				else{
					if(p->data < r->left->data){
						p->right = r->left;
					}
					else{
						p->left = r->left;
					}
				}
			}
			delete r; r=0;
			g = true;
		}else{//______________________________ Two Nodes BinaryTree
			node<T>* s = r;
			_Successor(r,p);
			s->data = r->data;
			var = r->data;
		}
	}while(g == false);
	size--;
	return g;
}

template<typename T> bool BinaryTree<T>::Update(const T& t,const T& t1){
	if(RecursiveDeleteIt(t)){
		IterativeInsert(t1);
		return true;
	}
	return false;
}

template<typename T> bool BinaryTree<T>::GetRootValue(T& t){
	if(root == NULL){
		return false;
	}
	t=root->data;
	return true;
}

template<typename T> void BinaryTree<T>::Inorder(void){
	_Inorder(root);
}
template<typename T> BinaryTree<T>::~BinaryTree(void){
	while(RecursiveDeleteIt(root->data)){}
	root = NULL;
}

/* Main Function To Test This Class

/************************Coded By Zuqurnain jutt*********************/
#include "Tree.h"
#include <Windows.h>
int main(){
	BinaryTree<char> tree;
	char val,val1;
	while(true){
		cout<<"\n\t::Binary Search BinaryTree Menu::\t\n";
		cout<<"\t1 - Insert\n";
		cout<<"\t2 - Delete\n";
		cout<<"\t3 - Search\n";
		cout<<"\t4 - Get Root\n";
		cout<<"\t5 - Update\n";
		cout<<"\t6 - Print Status\n";
		cout<<"\t7 - Exit\n";
		cout<<"\tEnter Your Choice...";
		char sel=_getche();
		system("CLS");
		if(sel=='1'){
			cout<<"Enter Value to Insert:=:"; cin>>val; cout<<"\n";
			tree.RecursiveInsert(val);
		}
		else if(sel=='2'){
			cout<<"Enter Value To Delete :=:"; cin>>val; cout<<"\n";
			if(tree.RecursiveDeleteIt(val)){
				cout<<"\n::Values Deleted::\n";
			}else{cout<<"\n::Values Not Deleted::\n";}
		}
		else if(sel=='3'){
			cout<<"Enter Value to Find :=:"; cin>>val; cout<<"\n";
			if(tree.RecursiveSearch(val)){
				cout<<":: Element Found::\n";
			}else{
				cout<<"BinaryTree Is Empty or value not found\n";
			}
		}
		else if(sel=='4'){
			if(tree.GetRootValue(val)){
				cout<<"Value At Root :=:"<<val<<"\n";
			}
			else{
				cout<<"BinaryTree Is Empty or value not found\n";
			}
		}
		else if(sel=='5'){
			cout<<"Enter Value To Update :=:"; cin>>val; cout<<"\n";
			cout<<"Enter Updated Value :=:"; cin>>val1; cout<<"\n";
			if(tree.Update(val,val1)){
				cout<<"Value Updated Successfully\n";
			}else{cout<<"Value Not Found To Update\n";}
		}
		else if(sel=='6'){
			tree.Inorder();
		}
		else if(sel=='7'){
			break;
		}
		cout<<"Press Any Key To Continue...";
		_getch();
		system("CLS");
	}
	_getch();
	return 0;
}
  
*/