Binary Search Tree Your program should take the following inputs: 1. Student ID
ID: 3715107 • Letter: B
Question
Binary Search Tree
Your program should take the following inputs:
1. Student ID (any value between 1000 to 1100) – NO DUPLICAT ES
2. Student first name (max. 20 characters)
3. Student last name, (max. 20 characters)
4. Student scores (float/double), eg. 85.4
5. Zip code (may be a string)
You have to create a structure Student with above information. Then create a Binary Search Tree where each node in the BST contains a Student.
Note1: Student ID (left child) < Student ID (parent) < Student ID (right) Your program should be able to take records of a minimum of 5 students. After taking the records, you should provide 7 functionalities to the user.
1. Print records – prints records of all students.
2. Add a new record - take a new record from the user for a new student. Create a node for the new student and add it to the BST (Student ID value must satisfy the BST property as provided in Note1).
3. Delete record(s) – to delete a record, ask for the last name of the student from the user. If there are multiple students with same last name, you must delete all of their records ( you have to delete corresponding nodes and adjust the BST accordingly).
4. S earch by Zip code – prints records of all students with a given zip code.
5. Search by score range – take two scores max, min; and then print records of all students who have scores between [max, min] (inclusive).
6. Find the median score – compute the median score and print it. Also, print how many students are above this median score (do not forget to sort the values in the nodes to compute median) .
7. Exit the program – terminate on a specific input from the user. Let that specific input be an integer of value 0.
You should print the record in the following format:
First Name: firstname1, Last Name: lastname1, Score: score1 Zip code: code1
First Name: firstname2, Last Name: lastname2, Score: score2 Zip code: code2 . . .
You should write each functional ity from 1 - 7 in separate functions. You should provide a menu to the user as following:
For inputs: Please indicate number of records you want to enter (min 5): #of records After user gives the number of records, you should inform the user how to enter the records: Please input records of students (enter a new line after each record), with following format first name last name score zip code After user gives the inputs for the records, inform the user about the functionalities:
Print records (press 1 ) Add a new record (press 2) Delete record(s) (press 3) Search by zip code (press 4) Search by score range (press5) Find median score (press 7) Exit the program (press 0) After user chooses functionality, your program performs that and provides this menu again to select another option. This goes on until user presses 0.
Instruction: Do not forget to use - malloc for a new node - free to delete it.
Explanation / Answer
//main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// create node:
struct Node{
int id;
char fn[20];
char ln[20];
char zc[5];
double s;
struct Node *left;
struct Node *right;
};
int records;
void printMenu();
struct Node* insert(struct Node *root,int id,char fn[20],char ln[20],double s,char zc[5]);
struct Node* getNewNode(int id,char fn[20],char ln[20],double s,char zc[5]);
void printDB(struct Node *root);
void searchZip(struct Node *root, char zc[20]);
void searchRange(struct Node *root, double min, double max);
double findMedian(struct Node *root);
void sortScores(double* s,int n);
void aboveMedian(struct Node *root, double med);
int count;
int aboveMed = 0;
double medVal;
double *scores;
int main(){
int iRec,id,i,choice;
double minScore,maxScore;
char fn[20];
char ln[20];
char zc[5];
double s, medVal;
struct Node *root = NULL;
printf("WELCOME TO THE STUDENT RECORD MANAGER 100 V 1.0! ");
printf("Please indicate the number of student records you want to enter (min 5): ");
scanf("%d",&iRec);
if(iRec < 5){
printf("You must enter more than five... terminating. ");
return 0;
}
printf("Please enter the values for each student (id(1000-11000) firstName lastName score zipcode) pressing enter after each: ");
for(i = 0; i < iRec; i ++){
// add record
printf("%d > ",i+1);
scanf("%d %s %s %lf %s",&id,&fn,&ln,&s,&zc);
root = insert(root,id,fn,ln,s, zc);
}
do{
printMenu();
scanf("%d",&choice);
switch(choice){
case 1:
printDB(root);
break;
case 2:
printf("Please enter the values for the student (id(1000-11000) firstName lastName score zipcode) pressing enter after each: ");
scanf("%d %s %s %lf %s",&id,&fn,&ln,&s,&zc);
root = insert(root,id,fn,ln,s, zc);
break;
case 4:
printf("Please enter the zip code you would like to search for: ");
scanf("%s",&zc);
searchZip(root, zc);
break;
case 5:
printf("Please enter the score range you would like to search from(min max): ");
scanf("%lf %lf",&minScore,&maxScore);
searchRange(root,minScore,maxScore);
break;
case 6:
medVal = findMedian(root);
aboveMedian(root,medVal);
printf(" > MEDIAN SCORE: %0.3lf > STUDENTS ABOVE: %d ",medVal,aboveMed);
count = 0;
break;
case 7:
return 0;
break;
case 0:
return 0;
}
}
while(1);
return 0;
// search
/*
int num;
scanf("%d",&num);
if(search(root,))
*/
}
// Print user menu
void printMenu(){
printf(" Main Menu "
"============================ "
" > Print records (press 1) "
" > Add a new record (press 2) "
" > Search by zip code (press 4) "
" > Search by score range (press 5) "
" > Find median score (press 6) "
" > Exit the program (press 0) "
"============================ "
"Please select an option: ");
}
struct Node* insert(struct Node *root,int id,char fn[20],char ln[20],double s,char zc[5]){
if(root == NULL){
root = getNewNode(id,fn,ln,s,zc);
}
else if(id <= root->id){
// tree is not empty
root->left = insert(root->left,id,fn,ln,s,zc);
// will go back through, root will be null then will get a new node and put it in
}
else { // means data > root->data
// tree is not empty
root->right = insert(root->right,id,fn,ln,s,zc);
}
return root;
}
struct Node* getNewNode(int id,char fn[20],char ln[20],double s,char zc[5]){
// Create root node using malloc and a temp variable
struct Node* temp = (struct Node*) malloc(sizeof(struct Node));
temp->id = id;
strcpy(temp->fn,fn);
strcpy(temp->ln,ln);
temp->s = s;
strcpy(temp->zc,zc);
temp->left = temp->right = NULL;
records++;
return temp;
}
void printDB(struct Node *root){
if(root){
printf("> %d %s %s %0.2lf %s ",root->id,root->fn,root->ln,root->s,root->zc);
printDB(root->left);
printDB(root->right);
}
}
void searchZip(struct Node *root, char zc[20]){
// first check if it is empty
if(root == NULL){
// list empty
}
else{
if(strcmp(root->zc,zc) == 0){
// value found
printf("> %d %s %s %0.2lf %s ",root->id,root->fn,root->ln,root->s,root->zc);
}
if(zc < root->zc){
// left
searchZip(root->left, zc);
}
else{
searchZip(root->right, zc);
}
}
}
void searchRange(struct Node *root, double min, double max){
if(root){
if(root->s < max && root->s > min)
printf("> %d %s %s %0.2lf %s ",root->id,root->fn,root->ln,root->s,root->zc);
searchRange(root->left,min,max);
searchRange(root->right,min,max);
}
}
double findMedian(struct Node *root){
if(count == 0)
scores = malloc(records);
// create dynamic array
if(root){
scores[count] = root->s;
count++;
findMedian(root->left);
findMedian(root->right);
sortScores(scores, records);
medVal = records / 2;
medVal = scores[(int)medVal];
return medVal;
}
}
// Recursive bubble sort for score
void sortScores(double* s,int n){
int i;
double tempF;
if(n == 1)
return;
for(i=0;i<n-1;i++){
if(s[i+1] > s[i]){
tempF = *(s+i+1);
*(s+i+1) = *(s+i);
*(s+i) = tempF;
}
}
sortScores(s,n-1);
}
void aboveMedian(struct Node *root, double med){
if(root){
if(root->s > med)
aboveMed++;
aboveMedian(root->left,med);
aboveMedian(root->right,med);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.