Introduction In this assignment you will modify the program written in the previ
ID: 3748417 • Letter: I
Question
Introduction
In this assignment you will modify the program written in the previous assignment (bribe program) to use a binary search tree.
The application will look the same to the user as the application you created for Assignment #4, and have the same sample output, with one exception. In Assignment #4, if if the user entered a bribe amount that someone already in the list paid, then you "broke the tie" by "first come, first served." However, binary search trees cannot contain duplicate values. Therefore, in this assignment, if the user enters a bribe amount that someone already in the list paid, then you will not add a new person to the list. Instead, you just will advise the user that this bribe amount has already been paid, after which the application continues by displaying the menu to add, view or exit.
You will be creating a multi-file project with the following three files:
As with Assignment #4, you have been given all the code except for the implementation of the CTree class. The code for the driver file is given below. The accompanying Module gives you all the member variables and functions of the CTree class and the member variables and constructor of the PersonRec structure, so writing the tree.h file should be a no-brainer. Your task is to implement, in tree.cpp, the CTree member functions. There also is a PowerPoint presentation on recursion that you can download.
NOTE: As with Assignment #4, you do not need to do any error checking to determine if the user typed in a legal menu choice (1, 2 or 3), a name, or a positive whole number for a bribe.
Same rules as before for turning in your assignment, late assignments, doing your own work, etc.
Code for test.cpp file
// test.cpp
#include <iostream>
using namespace std;
#include <cstdlib>
#include "tree.h"
int displayMenu (void);
void processChoice(int, CTree&);
int main (void)
{
int num;
CTree ct;
do
{
num = displayMenu();
if (num != 3)
processChoice(num, ct);
} while (num != 3);
return 0;
}
int displayMenu (void)
{
int choice;
cout << " Menu ";
cout << "============================== ";
cout << "1. Add student to waiting list ";
cout << "2. View waiting list ";
cout << "3. Exit program ";
cout << "Please enter choice: ";
cin >> choice;
return choice;
}
void processChoice(int choice, CTree& myTree)
{
switch (choice)
{
case 1: myTree.Add (); break;
case 2: myTree.View (); break;
}
}
Explanation / Answer
test.cpp
#include <iostream>
using namespace std;
#include <cstdlib>
#include "tree.h"
int displayMenu(void);
void processChoice(int, CTree&);
int main(void)
{
int num;
CTree ct;
do
{
num = displayMenu();
if (num != 3)
processChoice(num, ct);
} while (num != 3);
return 0;
}
int displayMenu(void)
{
int choice;
cout << " Menu ";
cout << "============================== ";
cout << "1. Add student to waiting list ";
cout << "2. View waiting list ";
cout << "3. Exit program ";
cout << "Please enter choice: ";
cin >> choice;
return choice;
}
void processChoice(int choice, CTree& myTree)
{
switch (choice)
{
case 1: myTree.Add(); break;
case 2: myTree.View(); break;
}
}
tree.cpp
#include<iostream>
using namespace std;
#include"tree.h"
CTree::CTree(){
root = NULL;
}
CTree::~CTree(){
DeleteTree(root);
}
void CTree::View(){
if (!isEmpty()) {
cout << endl << "Name Contribution ";
cout << "======================================= " << endl;
}
DisplayTree(root);
}
void CTree::Add(){
char aName[40];
int aBribe;
cout << "Enter the person's name: ";
cin >> aName; //assumes no embedded spaces
cout << "Enter the person's contribution: ";
cin >> aBribe;
if (isEmpty())
BuildRoot(aName, aBribe);
else if (!isFull())
AddItem(root, aName, aBribe);
}
bool CTree::isEmpty(){
if (root == NULL)
return true;
else
return false;
}
bool CTree::isFull(){
PersonRec* temp;
try
{
temp = new PersonRec("temp", 0, NULL, NULL);
delete temp;
return false;
}
catch (bad_alloc exception)
{
return true;
}
}
void CTree::BuildRoot(char* name, int bribe){
root = new PersonRec(name, bribe, NULL, NULL);
}
void CTree::AddItem(PersonRec*& ptr, char* name, int bribe){
if (ptr != NULL)
{
if (bribe > ptr->bribe) {
AddItem(ptr->rChild, name, bribe);
}
else if (bribe < ptr->bribe) {
AddItem(ptr->lChild, name, bribe);
}
else
{
cout << " This bribe amount has already been paid. ";
return;
}
}
else //ptr == NULL
{
ptr = new PersonRec(name, bribe, NULL, NULL);
}
}
void CTree::DisplayTree(PersonRec* ptr){
if (isEmpty())
cout << " List is empty ";
else
{
if (ptr != NULL) {
DisplayTree(ptr->rChild);
cout << ptr->name << " $" << ptr->bribe << endl;
DisplayTree(ptr->lChild);
}
}
}
void CTree::DeleteTree(PersonRec*& ptr) {
if (ptr != NULL) {
DeleteTree(ptr->lChild);
DeleteTree(ptr->rChild);
delete ptr;
}
}
tree.h
#ifndef TREE_H
#define TREE_H
struct PersonRec {
char name[20];
int bribe;
PersonRec* lChild;
PersonRec* rChild;
//4-arg constructor
PersonRec(char* n, int b, PersonRec* left, PersonRec* right)
{
strcpy_s(name, sizeof(name), n);
bribe = b;
lChild = left;
rChild = right;
}
};
class CTree {
public:
CTree();
~CTree();
void View();
void Add();
private:
PersonRec* root;
bool isEmpty();
bool isFull();
void BuildRoot(char*, int);
void AddItem(PersonRec*&, char*, int);
void DisplayTree(PersonRec*);
void DeleteTree(PersonRec*&);
};
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.