#include<iostream.h>
# define false 0
# define true 1
template<class T>
class Node
{
public:
Node(Node<T> *the_parent = NULL );
T item;
int number_of_items;
Node<T> *parent;
Node<T> *left_child;
Node<T> *right_child;
};
template<class T>
Node<T>::Node(Node<T> *the_parent):number_of_items(0)
,parent(the_parent), left_child(NULL)
,right_child(NULL){}
template<class T>
class BTree
{
public:
BTree();
~BTree();
void Insert(T item);
void List_PreOrder();
void List_InOrder();
void List_PostOrder();
private:
bool r, l;
Node<T> *root;
int node_count;
void Insert(T item, Node<T> *tree, Node<T> *parent);
void List_PreOrder(Node<T> *tree, Node<T> *parent);
void List_InOrder(Node<T> *tree, Node<T> *parent);
void List_PostOrder(Node<T> *tree, Node<T> *parent);
void Delete_Tree(Node<T> *tree);
void Visit(Node<T> *the_node);
void List_PreOrder(Node<T> *tree);
void List_InOrder(Node<T> *tree);
void List_PostOrder(Node<T> *tree);
};
template<class T>
BTree<T>::BTree():node_count(0), root(NULL){}
template<class T>
BTree<T>::~BTree()
{
Delete_Tree(root);
}
template<class T>
void BTree<T>::Delete_Tree(Node<T> *tree)
{
if(tree)
{
Delete_Tree(tree->left_child);
Delete_Tree(tree->right_child);
delete tree;
}
}
template<class T>
void BTree<T>::Insert(T item)
{
Insert(item, root, root);
}
template<class T>
void BTree<T>::Insert(T item, Node<T> *tree, Node<T> *parent)
{
if(node_count == 0)
{
root = new Node<T>(parent);
root->item = item;
root->number_of_items++;
node_count++;
}
else if(!tree)
{
tree = new Node<T>(parent);
tree->item = item;
tree->number_of_items++;
if(r) parent->right_child = tree;
else if(l) parent->left_child = tree;
node_count++;
}
else if(item == tree->item)
tree->number_of_items++;
else if(item < tree->item)
{
r = false;
l = true;
Insert(item, tree->left_child, tree);
}
else if(item > tree->item)
{
r = true;
l = false;
Insert(item, tree->right_child, tree);
}
}
template<class T>
void BTree<T>::Visit(Node<T> *the_node)
{
cout<<the_node->item;
}
template<class T>
void BTree<T>::List_PreOrder(){ List_PreOrder(root);}
template<class T>
void BTree<T>::List_InOrder(){List_InOrder(root);}
template<class T>
void BTree<T>::List_PostOrder(){List_PostOrder(root);}
template<class T>
void BTree<T>::List_PreOrder(Node<T> *tree)
{
if(tree)
{
Visit(tree);
List_PreOrder(tree->left_child);
List_PreOrder(tree->right_child);
}
}
template<class T>
void BTree<T>::List_InOrder(Node<T> *tree)
{
if(tree)
{
List_InOrder(tree->left_child);
Visit(tree);
List_InOrder(tree->right_child);
}
}
template<class T>
void BTree<T>::List_PostOrder(Node<T> *tree)
{
if(tree)
{
List_PostOrder(tree->left_child);
List_PostOrder(tree->right_child);
Visit(tree);
}
}
int main( void )
{
BTree<char> char_tree;
cout<<"\n\nbinary tree using template :";
char_tree.Insert('d');
char_tree.Insert('b');
char_tree.Insert('f');
char_tree.Insert('a');
char_tree.Insert('c');
char_tree.Insert('e');
char_tree.Insert('g');
cout<<"\n\n Preorder :";
char_tree.List_PreOrder();
cout<<"\n\n inorder :";
char_tree.List_InOrder();
cout<<"\n\npostorder :";
char_tree.List_PostOrder();
cin.get();
return 0;
}