Hi, I need help with this C++ programming homework. But please use CLASS to do t
ID: 3739476 • Letter: H
Question
Hi, I need help with this C++ programming homework. But please use CLASS to do this and don't copy anything from the internet. Thank you for the help.
-----------------------Use CLASS --------------------
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
Note : I considering data type for key int, for name string and for balance int. If anything confuses let me know.
Implementation of BST in C++ using Class:
# include <iostream>
# include <cstdlib>
# include <string>
using namespace std;
// Node Declaration
struct BstNode
{
int key; //to store key
string name; //to store name
int balancedue; //to store balance
BstNode *left;
BstNode *right;
}*root;
// Class Declaration for binary search tree
class BST
{
public:
BST(){
root = NULL;
}
void insertBstNode(BstNode *,BstNode *); //insert node in BST
void inorder(BstNode *); //for inorder search of BST
bool retrieveNode(BstNode *, int); //To retrieve a node if key is provided
};//end of class BST
// Main Contains Menu
int main()
{
int choice, num;
BST bst;
bool flag;
int key;
BstNode *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert a node "<<endl;
cout<<"2.Inorder Traversal of BST"<<endl;
cout<<"3.Retrieve a node"<<endl;
cout<<"4.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new BstNode;
cout<<"Enter the key: ";
cin>>temp->key;
cout<<"Enter the name: ";
cin>>temp->name;
cout<<"Enter the balance due: ";
cin>>temp->balancedue;
bst.insertBstNode(root, temp);
break;
case 2:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 3:
cout<<"Enter key: ";
cin>>key;
flag = bst.retrieveNode(root,key);
if(flag == false)
cout<<endl<<"Key not found"<<endl<<endl;
break;
case 4:
exit(0);
default:
cout<<"Wrong choice"<<endl;
}
}
}//end of main
// Inserting Element into the Tree
void BST::insertBstNode(BstNode *tree, BstNode *newnode)
{
if (root == NULL) //tree is empty creating first node.
{
root = new BstNode;
root->key = newnode->key;
root->name = newnode->name;
root->balancedue = newnode->balancedue;
root->left = NULL;
root->right = NULL;
cout<<endl<<"Root Node is Added to BST"<<endl;
return;
}
//checking if key already exist in tree.
if (tree->key == newnode->key)
{
cout<<endl<<"Key already exist in the BST"<<endl;
return;
}
//if key is less than current node's key it will be to it's leftSubtree
if (tree->key > newnode->key)
{
if (tree->left != NULL)
{
insertBstNode(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<endl<<"Node Added To Left "<<endl;
return;
}
}
else //else will be added to it's right subtree
{
if (tree->right != NULL)
{
insertBstNode(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<endl<<"Node Added To Right"<<endl;
return;
}
}
}//end of insertBstNode function
// In Order Traversal (Recursive Implementation)
void BST::inorder(BstNode *ptr)
{
if (root == NULL) //checking if BST is empty
{
cout<<"BST is empty"<<endl;
return;
}
cout<<endl; //printing extra newline.
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->key<<" "<<ptr->name<<" "<<ptr->balancedue<<", ";
inorder(ptr->right);
}
}//end of inorder function
//To retrieve a node information
bool BST::retrieveNode(BstNode* root, int key){
if(root == NULL) { //if BST empty then simply return false
return false;
}
//if key matches to any node key
else if(root->key == key) {
cout<<endl<<"key: "<<root->key<<" name: "<<root->name<<" balancedue: "<<root->balancedue<<endl;
return true;
}
//if key is lesser than current node , go to left subtree
else if(key <= root->key) {
return retrieveNode(root->left,key);
}
//else to right subtree
else {
return retrieveNode(root->right,key);
}
}//end of retrieveNode function
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.