C++ BINARY SEARCH TREE Write your own version of a class template that will crea
ID: 3831760 • Letter: C
Question
C++ BINARY SEARCH TREE
Write your own version of a class template that will create a binary tree that can hold values of any data type. Then, design an Employeelnfo class that holds the following employee information: Employee ID Number: an integer Employee Name: a string Next, use the template you designed to implement a binary tree whose nodes hold an instance of the EmployeeInfo class. The nodes should be sorted on the Employee ID number. Test the binary tree by inserting nodes with the following information. Your program should allow the user to enter an ID number, then search the tree for the number. If the number is found, it should display the employee's name. If the node is not found, it should display a message indicating so. The following is a small example of a subset of a run of this program:Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
class EmployeeInfo
{
public :
string name;
int id;
EmployeeInfo(int i,string n){
name = n;
id = i;
}
bool operator <(const EmployeeInfo& e) {
if(id < e.id) {
return true;
}
return false;
}
bool operator >(const EmployeeInfo& e) {
if(id > e.id) {
return true;
}
return false;
}
bool operator ==(const EmployeeInfo& e) {
if(id == e.id) {
return true;
}
return false;
}
};
ostream& operator<<(ostream& os, const EmployeeInfo& e)
{
os << "Employee ID : "<<e.id << " Employee Name : " << e.name << endl;
return os;
}
template <class T>
class Tree
{
// Internal class which stores only Node related information.
struct TreeNode
{
T data;
TreeNode * left;
TreeNode * right;
TreeNode(T val):data(val),left(NULL),right(NULL)
{
}
};
TreeNode * root;
void print(TreeNode*);
void freeMemory(TreeNode*);
bool search(TreeNode*,T id);
public:
Tree();
~Tree();
void insert(T);
void print();
void search(T emp);
};
template <class T>
Tree<T>::Tree():root(NULL){}
template <class T>
Tree<T>::~Tree()
{
freeMemory(root);
}
template <class T>
void Tree<T>::freeMemory(Tree::TreeNode *node)
{
if (node==NULL)
return;
if (node->left)
freeMemory(node->left);
if (root->right)
freeMemory(node->right);
delete node;
}
template <class T>
//make it return value?
void Tree<T>::insert(T val)
{
TreeNode * treeNode = NULL;
try
{
treeNode = new TreeNode(val); // handle exception necessary?
} catch (std::bad_alloc &exception)
{
std::cerr << "bad_alloc caught: " << exception.what() << std::endl;
EXIT_FAILURE;
}
TreeNode *temp=NULL;
TreeNode *prev=NULL;
temp = root;
while(temp)
{
prev = temp;
if (temp->data < treeNode->data)
temp = temp->right;
else
temp = temp->left;
}
if (prev==NULL)
root = treeNode;
else
{
if (prev->data<treeNode->data)
prev->right = treeNode; // use setter function?
else
prev->left = treeNode;
}
}
template <class T>
void Tree<T>::print(TreeNode *root)
{
if (root==NULL)
return ;
print(root->left);
std::cout << root->data << std::endl;
print(root->right);
}
template <class T>
void Tree<T>::print()
{
print(root);
}
template <class T>
bool Tree<T>::search(TreeNode *root,T id)
{
if (root==NULL)
return false;
if(root->data==id){
cout << "Employee was Found ";
cout << root->data;
return true;
}
else if(search(root->left,id))
return true;
else if(search(root->right,id))
return true;
else
return false;
}
template <class T>
void Tree<T>::search(T emp)
{
search(root,emp);
}
int main()
{
Tree<EmployeeInfo> tree;
tree.insert(EmployeeInfo(1021,"Jhon Williams"));
tree.insert(EmployeeInfo(1075,"Bill Witherspoon"));
tree.insert(EmployeeInfo(2487,"jenifer Twine"));
tree.insert(EmployeeInfo(3769,"Sophia Lancaster"));
tree.insert(EmployeeInfo(1017,"Debbie Reece"));
tree.insert(EmployeeInfo(1275,"George McMullin"));
tree.insert(EmployeeInfo(1899,"Ashley Smith"));
tree.insert(EmployeeInfo(4218,"Josh Plemmons"));
tree.print();
int id;
cout <<"Enter an Employee Number :";
cin >>id;
EmployeeInfo emp(id,"");
tree.search(emp);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.