Binary Search Tree . Code ( in .txt ): [ http://goo.gl/ctUVso ] Write a program
ID: 3685292 • Letter: B
Question
Binary Search Tree.
Code (in .txt): [http://goo.gl/ctUVso]
Write a program that a company can use to keep up with the efficiency of its employees. The company keeps a record of mistakes made by each employee. If five mistakes are made by an employee, the employee is fired. The company has a maximum of 20 employees. Each employee has a unique identification number between 10 and 40. An employee is represented by an ID number and a counter to count the number of mistakes that the employee has made. Write a program to simulate this process by using the following guide lines. Allow your program to randomly generate the identifications for each employee between 10 and 30. The first time an identifications number is generated the person is lined with a count of zero mistakes. If the same identification number is generated again, increment the counter for the employee's mistakes. Once the person makes 5 mistakes fire the person. Use binary search trees to keep up with the employees. A person is hired by placing the information about the person (identification number and zero mistakes) on an employee binary search tree. A person is fired by removing the information about the person from the employee binary search tree and placing the information on a fired binary search tree. Both binary search trees are ordered by the employee's identification number. Allow your program to randomly generate ID numbers 100 times. (Use the C++ rand() function) Output: Your program should do the following: Print out a numerically ordered list of all identification numbers of employees along with the number of mistakes of each employee from the employee binary search tree. Remove all employees from the employees binary search tree with 5 or more mistakes Print out the content of the employees binary search tree after the fired employees have been removed. Print out a numerically ordered list of the identification numbers of the fired employees along with the number of mistakes for each employee on the fired binary search tree. Use one of the following definitions for your binary search tree: The following definition for the binary search tree modifies the node class to hold the two values: The following definition for the binary search tree using a struct to hold the two values:Explanation / Answer
# include <cstdlib>
#include<iostream>
#include <ctime>
using namespace std;
/*
* nod Declaration
*/
int i=0;
class nod
{
friend class bst;
public:
int ID;
int counter;
nod *left;
nod *right;
}*root;
class bst
{
public:
void tfind(int, nod **, nod **);
void tinsert(nod *,nod *);
void tdel(int);
void cond_a(nod *,nod *);
void cond_b(nod *,nod *);
void cond_c(nod *,nod *);
void preo(nod *);
void ino(nod *);
void posto(nod *);
void disp(nod *, int);
bst()
{
root = NULL;
}
};
int main()
{
int ch, num1,max,min;
bst bst;
nod *temp;
int randNum=0;
max=30;
min=10;
while (1)
{
cout<<"1.tinsert"<<endl;
cout<<"2.disp"<<endl;
cout<<"3.Quit"<<endl;
cout<<"Input the ch : ";
cin>>ch;
switch(ch)
{
case 1:
while(i<20)
{
temp = new nod;
randNum = rand()%(max-min + 1) + min;
temp->ID=randNum;
bst.tinsert(root, temp);
}
if (root == NULL)
{
cout<<"Tree empty"<<endl;
continue;
}
break;
case 2:
cout<<"disp bst:"<<endl;
bst.disp(root,1);
cout<<endl;
break;
case 3:
exit(1);
default:
cout<<"Wrong ch"<<endl;
}
}
}
/*
* tfind Element in the Tree
*/
void bst::tfind(int item, nod **par, nod **loc)
{
nod *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->ID)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->ID)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->ID)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->ID)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
/*
* tinserting Element into the Tree
*/
void bst::tinsert(nod *tree, nod *newnod)
{
if (root == NULL)
{
root = new nod;
root->ID = newnod->ID;
root->counter=0;
root->left = NULL;
root->right = NULL;
cout<<"Root node Added"<<endl;
i++;
return;
}
if (tree->ID == newnod->ID)
{
cout<<"Element already there in the tree"<<endl;
tree->counter++;
if(tree->counter>5)
tdel(tree->ID);
return;
}
if (tree->ID > newnod->ID)
{
if (tree->left != NULL)
{
tinsert(tree->left, newnod);
}
else
{
tree->left = newnod;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
i++;
cout<<"nod Added Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
tinsert(tree->right, newnod);
}
else
{
tree->right = newnod;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
i++;
cout<<"nod Added Right"<<endl;
return;
}
}
}
/*
* tdelete Element from the tree
*/
void bst::tdel(int item)
{
nod *par, *loc;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
tfind(item, &par, &loc);
if (loc == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (loc->left == NULL && loc->right == NULL)
cond_a(par, loc);
if (loc->left != NULL && loc->right == NULL)
cond_b(par, loc);
if (loc->left == NULL && loc->right != NULL)
cond_b(par, loc);
if (loc->left != NULL && loc->right != NULL)
cond_c(par, loc);
free(loc);
}
/*
* Case A
*/
void bst::cond_a(nod *par, nod *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
/*
* Case B
*/
void bst::cond_b(nod *par, nod *loc)
{
nod *lchild;
if (loc->left != NULL)
lchild = loc->left;
else
lchild = loc->right;
if (par == NULL)
{
root = lchild;
}
else
{
if (loc == par->left)
par->left = lchild;
else
par->right = lchild;
}
}
/*
* Case C
*/
void bst::cond_c(nod *par, nod *loc)
{
nod *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
cond_a(parsuc, suc);
else
cond_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
void bst::preo(nod *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->ID<<" ";
preo(ptr->left);
preo(ptr->right);
}
}
void bst::ino(nod *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
ino(ptr->left);
cout<<ptr->ID<<" ";
ino(ptr->right);
}
}
void bst::posto(nod *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
posto(ptr->left);
posto(ptr->right);
cout<<ptr->ID<<" ";
}
}
/*
* disp Tree Structure
*/
void bst::disp(nod *ptr, int level)
{
int i;
if (ptr != NULL)
{
disp(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->ID;
disp(ptr->left, level+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.