For this assignment you are to create a C class that will im

For this assignment you are to create a C++ class that will implement a binary search tree. Your class should implement the following functions

-          Insert

-          In order

-          Post order

-          Pre Order

-          Search

Your program will take in a command file called “cmd.txt” which will instruct your program on what operations to run

File Format

<command> <0 or 1 arguments>

Commands

-          1              insert

-          2              in order

-          3              post order

-          4              pre order

-          5              search

Example File

1 20

1 30

1 10

1 25

1 29

1 23

1 56

1 89

1 4

1 33

2

3

4

5 20

5 56

5 10

5 99

Expectations

You should not use any already implemented code such as a library for your linked list

Your code should be well formatted with proper spacing and proper naming

Your code should have well named variables. No a’s b’s or c’s as names unless it is for something like a loop counter

Your code MUST have the same output formatting you see below

Your file MUST be named a5.cpp

In order A 10 20 23 25 29 30 33 56 89 Post order: A 10 23 29 25 33 89 56 30 20 Pre order: 20 10 4 30 25 23 29 56 33 89 We did not find 5 56 We found We found 10 We did not find 99

Solution

# include <iostream>
# include <cstdlib>
using namespace std;

struct node
{
int info;
struct node *left;
struct node *right;
}*root;

class BST
{
public:
void find(int, node **, node **);
void insert(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 *);
BST()
{
root = NULL;
}
};

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.Inorder Traversal\"<<endl;
cout<<\"3.Preorder Traversal\"<<endl;
cout<<\"4.Postorder Traversal\"<<endl;
cout<<\"5.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:
cout<<\"Inorder Traversal of BST:\"<<endl;
bst.inorder(root);
cout<<endl;
break;
   case 3:
cout<<\"Preorder Traversal of BST:\"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 4:
cout<<\"Postorder Traversal of BST:\"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 5:
exit(1);
default:
cout<<\"Wrong choice\"<<endl;
}
}
}

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;
}
//*************insert*************
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;
}  
}
}


/*
* 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<<\" \";
}
}