USA: +1 725-224-8795 
Sign in
Hi there, please compile program in C++. It needs to be commented so someone non-technical can understand it. Please, show sample output screenshot of program working with sample data as required. Need to later integrate program with another. Thanks, and see below.
PROGRAM BELOW:
Create a class (BinaryTree) template that will create a binary tree that can hold values of any data type. The class should provide functions to insert a node, a function to delete a node, functions to display the tree In Order, Pre Order and Post Order. It should also provide a member function to search the tree for a value. The class should provide a function that counts the number of nodes in the tree, a function to count the number leaf nodes in the tree, and a function that determines the height of the tree. The height of a tree is the number of levels the tree has. Write a program that shows all these functions work.
Expert Answer
Answer
# include <iostream>
# include <cstdlib>
using namespace std;
// Node Declaration
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
// Class Declaration
class BST
{
public:
void find(int, node **, node **);
void insert(node*, node*);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
//main function
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<“—————–“<<endl;
cout<<“Operations on BST”<<endl;
cout<<“—————–“<<endl;
cout<<“1.Insert Element “<<endl;
cout<<“2.Delete Element “<<endl;
cout<<“3.Inorder Traversal”<<endl;
cout<<“4.Preorder Traversal”<<endl;
cout<<“5.Postorder Traversal”<<endl;
cout<<“6.Display”<<endl;
cout<<“7.Quit”<<endl;
cout<<“Enter your choice : “;
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<“Enter the number to be inserted : “;
cin>>temp->info;
bst.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<“Tree is empty, nothing to delete”<<endl;
continue;
}
cout<<“Enter the number to be deleted : “;
cin>>num;
bst.del(num);
break;
case 3:
cout<<“Inorder Traversal of BST:”<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<“Preorder Traversal of BST:”<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<“Postorder Traversal of BST:”<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<“Display BST:”<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<“Wrong choice”<<endl;
}
}
}
// Find Element in the Tree
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
//Inserting Element into the Tree
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<“Root Node is Added”<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<“Element already in the tree”<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<“Node Added To Left”<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<“Node Added To Right”<<endl;
return;
}
}
}
//Delete Element from the tree
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<“Tree empty”<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<“Item not present in tree”<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
//Case a
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
// Case _b
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
//Case_c
void BST::case_c(node *par, node *loc)
{
node *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)
case_a(parsuc, suc);
else
case_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;
}
// Pre Order Traversal
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<“Tree is empty”<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<” “;
preorder(ptr->left);
preorder(ptr->right);
}
}
// In Order Traversal
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<“Tree is empty”<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<” “;
inorder(ptr->right);
}
}
// Postorder Traversal
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<“Tree is empty”<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<” “;
}
}
// Display Tree Structure
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<“Root->: “;
else
{
for (i = 0;i < level;i++)
cout<<” “;
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
run code using command g++ bst.cpp
check ouput in file ./a.out OR best way to run code in c++shell
output:
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 3
Inorder Traversal of BST: Tree is empty
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Root Node is Added
Enter the number to be deleted : 0 Item not present in tree
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Right
Enter the number to be deleted : 0 Item not present in tree
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
Enter the number to be deleted : 0 Item not present in tree
Operations on BST
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 3
Inorder Traversal of BST: 4 5 7
