In-Class Assignment 5 - Binary Search Tree Build a binary search tree. Do not us
ID: 3738447 • Letter: I
Question
In-Class Assignment 5 - Binary Search Tree Build a binary search tree. Do not use an STL. Allow the user to enter any numerical key and store it properly in the tree. Along with the key there are 2 fields called name and balance due. 1. Let the user enter the 3 pieces of information for as many keys as desired. 2. Let the user see the results of having built the tree by providing an in-order search. 3. Let the user retrieve one node based on entry of a key. Return the key and the additional 2 fields. Make sure you can deal with the situation where the key is not found.Explanation / Answer
# include <iostream.h>
# include <cstdlib.h>
using namespace std;
struct node
{
int key;
String name;
double balance_due;
struct node *left;
struct node *right;
}*root;
class BST
{
public:
void insert(node *, node *);
void inorder_display(node *);
node search(node*, int)
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
BST bst;
char ch;
node *temp, *temp1;
while (1)
{
cout<<"1.Insert Element "<<endl;
cout<<"2.Inorder Traversal Dislay"<<endl;
cout<<"3.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the key to be inserted : ";
cin>>temp->key;
cout<<"Enter the name and balance due : ";
cin>>temp->name;
cin>>temp->balance_due;
bst.insert(root, temp);
break;
case 2:
bst.inorder(root);
cout<<endl;
break;
case 3:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
up:
cout<<" Enter the Element to be searched: ";
cin>>num;
temp1=Search(root, num);
cout<<" Do you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->key= newnode->key;
root->name= newnode->name;
root->balance_due= newnode->balance_due;
root->left = NULL;
root->right = NULL;
return;
}
if (tree->key== newnode->key)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->key> newnode->key)
{
if (tree->left != NULL)
insert(tree->left, newnode);
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
return;
}
}
else
{
if (tree->right != NULL)
insert(tree->right, newnode);
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
return;
}
}
}
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);
}
}
node BST::Search(node *root, int data)
{
node *temp = new node;
temp = root;
while(temp != NULL)
{
if(temp->key == data)
{
cout<<" Name:" temp->name;
cout<<" Balance Due:" temp->balance_due;
return temp;
}
else if(temp->key> data)
temp = temp->left;
else
temp = temp->right;
}
cout<<" Data not found";
return;
}