Build a Binary Search Tree in C++. Do not use an STL. Allow the user to enter an

Question

Build a Binary Search Tree in C++. 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 of imforation. Make sure you can deal with the situation where the key is not found.

Explanation / Answer

// C++ program to demonstrate insert operation in binary search tree
#include<iostream>
#include<stdlib.h>
#include<string.h>

using namespace std;
  
struct node
{
int key;
char name[15];
float balancedue;
struct node *left, *right;
};
  
// A utility function to create a new BST node
struct node *newNode(int item,char n[],float balance)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
//temp->name = n;
//(temp->name).assign(n);
strcpy(temp->name , n);
temp->balancedue = balance;
temp->left = temp->right = NULL;
return temp;
}
  
// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
cout<<"("<<root->key<<", "<<root->name<<","<<root->balancedue<<")"<<endl;;
inorder(root->right);
}
}
  
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* root, int key,char name[], float balance)
{
/* If the tree is empty, return a new node */
if (root == NULL) return newNode(key,name,balance);

/* Otherwise, recur down the tree */
if (key < root->key)
root->left = insert(root->left, key,name,balance);
else if (key > root->key)
root->right = insert(root->right, key,name,balance);   

/* return the (unchanged) node pointer */
return root;
}

// C function to search a given key in a given BST
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
  
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);

// Key is smaller than root's key
return search(root->left, key);
}

// Driver Program to test above functions
int main()
{
  
char c = 'y';
int key;
char name[15];
float balance;
  
struct node *root = NULL;
  
while(c=='y'){
       cout<<"Enter key, name, due balance(in order): ";
       cin>>key>>name>>balance;
       root = insert(root, key, name, balance);
      
       cout<<"Do you want to insert more? (y/n): ";
       cin>>c;
   }
  
  
// print inoder traversal of the BST
inorder(root);
  
cout<<"Enter search key: ";
cin>>key;
  
struct node *temp = search(root, key);
if(temp == NULL)
       cout<<"Key is not available"<<endl;
   else{
           cout<<"Key: "<<temp->key<<", Name: "<<temp->name<<", and Balance due: "<<temp->balancedue<<endl;
   }
  
return 0;
}

/*

Output:

Enter key, name, due balance(in order): 1
qw
12
Do you want to insert more? (y/n): y
Enter key, name, due balance(in order): 2
we
13
Do you want to insert more? (y/n): y
Enter key, name, due balance(in order): 3
er
14
Do you want to insert more? (y/n): y
Enter key, name, due balance(in order): 4
ty
15
Do you want to insert more? (y/n): y
Enter key, name, due balance(in order): 5
yu
16
Do you want to insert more? (y/n): n
(1, qw,12)
(2, we,13)
(3, er,14)
(4, ty,15)
(5, yu,16)
Enter search key: 4
Key: 4, Name: ty, and Balance due: 15

*/

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.