This is fairly old but I wrote this in my second year of college which was about 8 years ago :). It may help you out in some way or another...
//JHermiz
//Implementation File with def's
//tree.h
#include<stdlib.h>
#include"xcept.h" //file for exceptions that may be thrown
//BinaryTreeNode class
template<class T>
class BinaryTreeNode {
public:
BinaryTreeNode() {LeftChild=RightChild=NULL;}
BinaryTreeNode(const T&e)
{
data=e;
LeftChild=RightChild=NULL;
}
BinaryTreeNode(const T&e, BinaryTreeNode *l,
BinaryTreeNode *r)
{
data=e;
LeftChild=l;
RightChild=r;
}
BinaryTreeNode<T> *LeftChild; //left subtree
BinaryTreeNode<T> *RightChild; //right subtree
T data;
};
//BinaryTree Class
template<class T>
class BinaryTree{
public:
BinaryTree(){root=NULL;}
~BinaryTree(){Delete();}
void Delete(){PostOrder(Free, root); root=0;}
static void Free(BinaryTreeNode<T>* t){delete t;}
int IsEmpty()const
{return ((root) ? 0 : 1);}
int Root(T& x)const;
void MakeTree(const T& element, BinaryTree<T>& left,
BinaryTree<T>& right);
void BreakTree(T& element, BinaryTree<T>& left,
BinaryTree<T>& right);
void PreOrder(void(*Visit)(BinaryTreeNode<T> *u))
{PreOrder(Visit, root);}
void InOrder(void(*Visit)(BinaryTreeNode<T> *u))
{InOrder(Visit, root);}
void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))
{PostOrder(Visit, root);}
BinaryTreeNode<T>* root; //root pointer
//traversal methods
void PreOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
void InOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
void PostOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
static void Output(BinaryTreeNode<T> *t)
{
cout << t->data << " ";
}
void PreOutput()
{
PreOrder(Output, root);
cout << endl;
}
void InOutput()
{
InOrder(Output, root);
cout << endl;
}
void PostOutput()
{
PostOrder(Output, root);
cout << endl;
}
};
//base class is BinaryTree - BSTree is the derived class
template<class E, class K>
class BSTree : public BinaryTree<E>{
public:
int Search(const K& k, E& e)const;
BSTree<E,K>& Insert(const E& e);
BSTree<E,K>& Delete(const K& k, E& e);
//stores the maximum element of the tree in e
void MaxNode(E& e)const;
};
/*---------------------BinaryTree Methods()-------------------------*/
template<class T>
int BinaryTree<T>::Root(T& x) const
{ //Set x to root->data
//return false if no root
if(root)
{
x=root->data;
return 1;
}
else return 0; //no root
}
template<class T>
void BinaryTree<T>::MakeTree(const T& element,
BinaryTree<T>& left, BinaryTree<T>& right)
{//Combine left, right, and element to make new tree.
//left, right, and this must be different trees.
//create combined tree
root=new BinaryTreeNode<T>(element, left.root, right.root);
//deny access from trees left and right
left.root=right.root=0;
}
template<class T>
void BinaryTree<T>::BreakTree(T& element,
BinaryTree<T>& left, BinaryTree<T>& right)
{//left, right, and this must be of different trees.
//check if empty
if(!root) //empty tree
throw BadInput();
//break the tree
element=root->data;
left.root=root->LeftChild;
right.root=root->RightChild;
delete root;
root=0;
}
template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)
(BinaryTreeNode<T>* u), BinaryTreeNode<T>* t)
{//preorder traversal
if(t)
{
Visit(t);
PreOrder(Visit, t->LeftChild);
PreOrder(Visit, t->RightChild);
}
}
template<class T>
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T>* u),
BinaryTreeNode<T>* t)
{//inorder traversal
if(t)
{
InOrder(Visit, t->LeftChild);
Visit(t);
InOrder(Visit, t->RightChild);
}
}
template<class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T>* u),
BinaryTreeNode<T>* t)
{//postorder traversal
if(t)
{
PostOrder(Visit, t->LeftChild);
PostOrder(Visit, t->RightChild);
Visit(t);
}
}
/*----------------------End of BinaryTree Methods()------------------*/
/*------------------------BSTree Methods()---------------------------*/
template<class E, class K>
int BSTree<E,K>::Search(const K& k, E& e) const
{//Search for element that matches k.
//Pointer p starts at the root and moves through
//the tree looking for an element with key k.
BinaryTreeNode<E> *p=root;
while(p) //examine p if >, <, or ==
{
if(k<p->data)
p=p->LeftChild;
else if(k>p->data)
p=p->RightChild;
else{ //element is found
e=p->data;
return 1;
}
}
return 0;
}
template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
{ //Insert e if not duplicate
BinaryTreeNode<E> *p=NULL; //search pointer
BinaryTreeNode<E> *pp=NULL; //parent of p
//find place to insert throw BadInput if a duplicate element
p=root; //p is now the root
while(p)
{
pp=p;
//move p to a child depending if p is > or <
if(e<p->data)
p=p->LeftChild;
else if(e>p->data)
p=p->RightChild;
else
throw BadInput(); //a duplicate element
}
//Get a node (memory) for e and attach to pp
BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e);
if(root)
{//tree not empty
if(e<pp->data)
pp->LeftChild=r;
else if(e>pp->data)
pp->RightChild=r;
}
else //we need a root first!
root=r;
return *this;
}
template<class E, class K>
BSTree<E,K>& BSTree<E,K>:: Delete(const K& k, E& e)
{//Delete element with key k and put it in e.
//set p to point to node with key k
BinaryTreeNode<E> *p=NULL; //a search pointer
BinaryTreeNode<E> *pp=NULL; //parent of p
p=root;
while(p && p->data != k)
{//move to a child of p
pp=p;
if(k < p->data)
p=p->LeftChild;
else
p=p->RightChild;
}
if(!p) //no element with key k
throw NoElement();
e=p->data; //save element to delete
//restructure the tree so it remains a BSTree
if(p->LeftChild && p->RightChild) //handle the node with 2 children if any
{//convert it to point to NULL or one child case
//find largest element in left subtree of p
BinaryTreeNode<E> *s=p->LeftChild;
BinaryTreeNode<E> *ps=p; //parent of s which is actually p
while(s->RightChild)
{//move to the larger element
ps=s;
s=s->RightChild;
}//end while
//move largest from s to p
p->data=s->data;
p=s;
pp=ps;
}//end all if
//p only had one child
//save child pointer in c
BinaryTreeNode<E> *c;
if(p->LeftChild)
c=p->LeftChild;
else
c=p->RightChild;
//delete p
if(p==root)
root=c;
else{
//is p left or right child of pp?
if(p==pp->LeftChild)
pp->LeftChild=c;
else
pp->RightChild=c;
}//end else
delete p;
return *this;
}
template<class E, class K>
void BSTree<E,K>::MaxNode(E &e)const
{//function returns max. value of tree (rightmost value)
BinaryTreeNode<E>* p=NULL; //root node
BinaryTreeNode<E>* pp=NULL; //parent of p
p=root;
while(p)
{
pp=p;
p=p->RightChild;
}
//p points to NULL, pp points to node before NULL
e=pp->data; //max. value stored
}
char Menu()
{
char choice;
//a menu
cout << "\n\t\tBST TREE MENU\n";
cout << "\t********************************\n";
cout << "\t* 1)Type 1 to insert an element*\n";
cout << "\t* 2)Type 2 to delete an element*\n";
cout << "\t* 3)Type 3 to output pre-order *\n";
cout << "\t* 4)Type 4 to output in-order *\n";
cout << "\t* 5)Type 5 to output post-order*\n";
cout << "\t* 6)Type 6 for maximum element *\n";
cout << "\t* 7)Type 7 to output root *\n";
cout << "\t* 8)Type 8 to search for a # *\n";
cout << "\t* 9)Type 9 to exit program. *\n";
cout << "\t********************************\n";
cout << "Input your choice: ";
cin >> choice;
while(choice!='1' && choice!='2' && choice!='3'
&& choice!='4' && choice!='5' && choice!='6'
&& choice!='7' && choice!='8' && choice!='9')
{//user typed in wrong key
cout << "\nType choice as 1-9: ";
cin >> choice;
}
return choice;
}