C++ Binary Tree Template Write your own version of a class template that will cr
ID: 2247042 • Letter: C
Question
C++
Binary Tree Template
Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program. Be sure to include methods for insertion, removal, and searching of nodes.
Include a method for printing the tree out in order.
You'll need public and private versions of these methods. The public versions will call the private versions. The private versions will use recursion.
To be explicit, the type of binary tree is a binary search tree.
Explanation / Answer
#include <iostream>
#include <cstdlib>
using namespace std;
template<class T>
class BST
{
private:
struct t_node
{
t_node* left;
t_node* right;
T data;
};
t_node* root;
void inorder(t_node*);
void preorder(t_node*);
void postorder(t_node*);
public:
BST()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void insert(T);
void remove(T);
bool search(T);
void disp_inorder();
void disp_preorder();
void disp_postorder();
};
template <class T>
void BST<T>::insert(T d)
{
t_node* t = new t_node;
t_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
t_node* current;
current = root;
// Find the Node's parent
while(current)
{
parent = current;
if(t->data > current->data) current = current->right;
else current = current->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
template <class T>
bool BST<T>::search(T d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return false;
}
t_node* current;
t_node* parent;
current = root;
parent = (t_node*)NULL;
while(current != NULL)
{
if(current->data == d)
{
found = true;
break;
}
else
{
parent = current;
if(d>current->data) current = current->right;
else current = current->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
}
else
{
cout<<" Data found! "<<endl;
}
return found;
}
template <class T>
void BST<T>::remove(T d)
{
bool found = false;
if(isEmpty())
{
cout<<" The tree is empty"<<endl;
return;
}
t_node* current;
t_node* parent;
current = root;
parent = (t_node*)NULL;
while(current != NULL)
{
if(current->data == d)
{
found = true;
break;
}
else
{
parent = current;
if(d>current->data) current = current->right;
else current = current->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
if((current->left == NULL && current->right != NULL)|| (current->left != NULL
&& current->right == NULL))
{
if(current->left == NULL && current->right != NULL)
{
if(parent->left == current)
{
parent->left = current->right;
delete current;
}
else
{
parent->right = current->right;
delete current;
}
}
else
{
if(parent->left == current)
{
parent->left = current->left;
delete current;
}
else
{
parent->right = current->left;
delete current;
}
}
return;
}
if( current->left == NULL && current->right == NULL)
{
if (parent == NULL)
{
delete current;
} else
if(parent->left == current) parent->left = NULL;
else parent->right = NULL;
delete current;
return;
}
if (current->left != NULL && current->right != NULL)
{
t_node* chkr;
chkr = current->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
current = chkr;
delete chkr;
current->right = NULL;
}
else
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((current->right)->left != NULL)
{
t_node* lcurrent;
t_node* lcurrentp;
lcurrentp = current->right;
lcurrent = (current->right)->left;
while(lcurrent->left != NULL)
{
lcurrentp = lcurrent;
lcurrent = lcurrent->left;
}
current->data = lcurrent->data;
delete lcurrent;
lcurrentp->left = NULL;
}
else
{
t_node* t1;
t1 = current->right;
current->data = t1->data;
current->right = t1->right;
delete t1;
}
}
return;
}
}
template<class T>
void BST<T>::disp_inorder()
{
inorder(root);
}
template<class T>
void BST<T>::inorder(t_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}
template<class T>
void BST<T>::disp_preorder()
{
preorder(root);
}
template<class T>
void BST<T>::preorder(t_node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
template<class T>
void BST<T>::disp_postorder()
{
postorder(root);
}
template<class T>
void BST<T>::postorder(t_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<" ";
}
else return;
}
int main()
{
BST<int> b;
int ch;
int t1,t11;
while(1)
{
cout<<endl<<endl;
cout<<" BST Operations "<<endl;
cout<<" 1. Insert"<<endl;
cout<<" 2. Removal "<<endl;
cout<<" 3. Search "<<endl;
cout<<" 4. Postorder Traversal "<<endl;
cout<<" 5. Inorder Traversal"<<endl;
cout<<" 6. Preorder Traversal "<<endl;
cout<<" 7. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter data to be inserted : ";
cin.ignore(1);
cin>>t1;
b.insert(t1);
break;
case 2 : cout<<" Enter data to be deleted : ";
cin.clear();
cin.ignore(1);
cin>>t11;
b.remove(t11);
break;
case 3 : cout<<" Enter data to be searched : ";
cin.ignore(1);
cin>>t1;
b.search(t1);
break;
case 4 : cout<<endl;
cout<<" Postorder Traversal "<<endl;
b.disp_postorder();
break;
case 5 : cout<<endl;
cout<<" Inorder Traversal "<<endl;
b.disp_inorder();
break;
case 6 : cout<<endl;
cout<<" Preorder Traversal "<<endl;
b.disp_preorder();
break;
case 7 :
return 0;
break;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.