In-Class Assignment 5 - Binary Search Tree Build a binary search tree. Do not us
ID: 3734011 • 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<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int key;
char name;
int bal;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item, char n,int bal)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->name=n;
temp->bal=bal;
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);
printf(" ( %d ", root->key);
printf(" %c ", root->name);
printf(" %d )-->", root->bal);
inorder(root->right);
}
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key,char s,int bal)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key,s,bal);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key,s,bal);
else if (key > node->key)
node->right = insert(node->right, key,s,bal);
/* return the (unchanged) node pointer */
return node;
}
// 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()
{
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50,'A',100);
insert(root, 30,'B',200);
insert(root, 20,'C',600);
insert(root, 40,'D',60);
insert(root, 70,'E',6);
insert(root, 60,'F',6000);
insert(root, 80,'G',777);
// print inoder traversal of the BST
inorder(root);
struct node *res=search(root,80);
if(res!=NULL){
printf(" Search Successfull ");
printf(" ( %d ", res->key);
printf(" %c ", res->name);
printf(" %d )-->", res->bal);
}
else printf("Search Unsuccessful");
return 0;
}
OutPUT:-