Write a C++ program to implement a binary search tree and operate on the binary
ID: 3602420 • Letter: W
Question
Write a C++ program to implement a binary search tree and operate on the binary search tree, which to hold integers with no duplicate starting root = null. All of base code is given, need to add all necessary code. Program need to be run as same as the sample run.
Each line should have an explanation.
# include <iostream>
# include <cstdlib>
# include <cctype>
# include <string>
# include <vector>
# include <iterator>
# include <algorithm>
using namespace std;
struct node
{
//Define
}*root;
Class BST
{
Public:
find
insert
del
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
string command;
BST bst;
node *temp;
cout<<"-----------------"<
cout<<"Operations on BST"<
cout<<"-----------------"<
cout<<"INSERT "<
cout<<"DELETE "<
cout<<"FIND "<
cout<<"PRINT "<
cout<<"EXIT "<
cout<<"Continue to enter your choice, type EXIT when you are done.";
while (1)
{
vector data;
copy(istream_iterator(cin), istream_iterator(), back_inserter(data));
command = data[0];
transform(command.begin(), command.end(), command.begin(), ::toupper);
if (command == “INSERT”)
{
}
else if (command == “DELETE”)
{
}
else if (command == “FIND”)
{
}
else if (command == “PRINT”)
{
}
else if (command == “EXIT”)
{
exit(1);
}
else
{
cout<<”Wrong choice”<
}
}
}
INSERT <int value>
Output : SUCCESS or DUPLICATE or ERROR
DELETE <int value>
Output : SUCCESS or NOTFOUND or ERROR
FIND <int value>
Output : SUCCESS or NOTFOUND or ERROR
Output : PRINT NULL, if the tree is empty, otherwise print the numbers in sorted order(one per line) and print BEGIN at the start and END at the end(last line).
EXIT
The program is terminated.
Here is sample run:
Sample input
Sample output
NULL
INSERT 7
SUCCESS
INSERT 10
SUCCESS
INSERT 98
SUCCESS
INSERT 6
SUCCESS
INSERT 10
DUPLICATE
FIND 98
SUCCESS
FIND 34
NOTFOUND
DELETE 10
SUCCESS
BEGIN
6
7
98
END
EXIT
N/A (Program exits)
Sample input
Sample output
NULL
INSERT 7
SUCCESS
INSERT 10
SUCCESS
INSERT 98
SUCCESS
INSERT 6
SUCCESS
INSERT 10
DUPLICATE
FIND 98
SUCCESS
FIND 34
NOTFOUND
DELETE 10
SUCCESS
BEGIN
6
7
98
END
EXIT
N/A (Program exits)
Explanation / Answer
#include <iostream>
#include <cmath>
#include "plant.h"
#include "planttree.h"
using namespace std;
void showResults(planttree pt)
{
pt.display();
const plant* bestPlant;
cout << endl;
cout << "Best growth rate: " << endl;
bestPlant = pt.findBestGrowth();
if (bestPlant != nullptr)
cout << (*bestPlant) << endl;
else
cout << "ERROR: null best plant" << endl;
cout << "Best nutritional value: " << endl;
bestPlant = pt.findBestNutrition();
if (bestPlant != nullptr)
cout << (*bestPlant) << endl;
else
cout << "ERROR: null best plant" << endl;
cout << "Best water requirement: " << endl;
bestPlant = pt.findBestWater();
if (bestPlant != nullptr)
cout << (*bestPlant) << endl;
else
cout << "ERROR: null best plant" << endl;
}
plant getChildPlant(plant parent,int co[])
{
int gx = parent.getGrowth() - 50;
int nx = parent.getNutrition() - 50;
int wx = parent.getWater() - 50;
gx = abs(co[0] * (gx * gx * gx) + co[1] * ( gx * gx ) + co[2] * gx + co[3]);
gx = gx % 100;
nx = abs(co[4] * (nx * nx * nx) + co[5] * ( nx * nx ) + co[6] * nx + co[7]);
nx = nx % 100;
wx = abs(co[8] * (wx * wx * wx) + co[9] * ( wx * wx ) + co[10] * wx + co[11]);
wx = wx % 100;
char* plantId = new char[15]; // max size ==> Plant ??-??-?? == 15 chars
sprintf(plantId,"Plant %d-%d-%d",gx,nx,wx);
plant plant(plantId,gx,nx,wx);
delete [] plantId;
return(plant);
}
void runSingleExperiment(planttree& pt,int depth,plant& parentPlant)
{
if (depth > 0)
{
int leftCoeffs[] = {13,3,11,7,2,23,5,29,3,37,11,13};
int rightCoeffs[] = {128,16,64,2,32,8,2,128,256,16,16,64};
plant leftPlant = getChildPlant(parentPlant,leftCoeffs);
plant rightPlant = getChildPlant(parentPlant,rightCoeffs);
pt.addChildren(parentPlant,leftPlant,rightPlant);
runSingleExperiment(pt,depth-1,leftPlant);
runSingleExperiment(pt,depth-1,rightPlant);
}
}
void runExperiment(const char* title, plant startingPlant, int depth)
{
planttree pt;
pt.setRoot(startingPlant);
runSingleExperiment(pt,depth,startingPlant);
cout << "===================================" << endl;
cout << title << endl;
cout << "===================================" << endl;
showResults(pt);
cout << endl;
cout << endl;
}
int main()
{
runExperiment("Experiment 1",plant("Plant 1-1-1",1,1,1),5);
runExperiment("Experiment 2",plant("Plant 11-17-33",11,17,33),5);
return(0);
}
----------------------------------------------------------------------------
plant.cpp
------------------------------------------------
#include <cstring>
#include "plant.h"
plant::plant(): m_id(nullptr), m_growth_rate(0), m_nutritional_value(0), m_water_requirement(0) {}
plant::plant(const char* id, const int growth_rate, const int nutritional_value, const int water_requirement):
m_growth_rate(growth_rate),
m_nutritional_value(nutritional_value),
m_water_requirement(water_requirement)
{
m_id = new char[std::strlen(id)+1];
std::strncpy(m_id, id, std::strlen(id)+1);
}
plant::~plant()
{
delete[] m_id;
}
plant::plant(const plant& p):
m_growth_rate(p.getGrowth()),
m_nutritional_value(p.getNutrition()),
m_water_requirement(p.getWater())
{
if (p.getId() != nullptr) {
m_id = new char[std::strlen(p.getId())+1];
std::strncpy(m_id, p.getId(), std::strlen(p.getId())+1);
} else {
m_id = nullptr;
}
}
plant& plant::operator=(const plant& p)
{
if (this != &p) {
if (m_id != nullptr) {
delete[] m_id;
}
if (p.getId() != nullptr) {
m_id = new char[std::strlen(p.getId())+1];
std::strncpy(m_id, p.getId(), std::strlen(p.getId())+1);
} else {
m_id = nullptr;
}
m_growth_rate = p.getGrowth();
m_nutritional_value = p.getNutrition();
m_water_requirement = p.getWater();
}
return *this;
}
char* plant::getId() const
{
return m_id;
}
int plant::getGrowth() const
{
return m_growth_rate;
}
int plant::getNutrition() const
{
return m_nutritional_value;
}
int plant::getWater() const
{
return m_water_requirement;
}
--------------------------------------------------------------------------------
plant.h
-----------------------------------------
#ifndef PLANT_H
#define PLANT_H
#include <ostream>
class plant {
private:
char* m_id;
int m_growth_rate;
int m_nutritional_value;
int m_water_requirement;
public:
plant();
plant(const char*, const int, const int, const int);
~plant();
plant(const plant&);
plant& operator=(const plant&);
char* getId() const;
int getGrowth() const;
int getNutrition() const;
int getWater() const;
friend std::ostream& operator<<(std::ostream& os, const plant& p);
};
inline std::ostream& operator<<(std::ostream& os, const plant& p)
{
os << "Plant ID: " << p.getId() << " (";
os << "G: " << p.getGrowth() << " ";
os << "N: " << p.getNutrition() << " ";
os << "W: " << p.getWater() << ")";
}
#endif
-----------------------------------------------------------------------------------------------------------
planttree.cpp
-----------------------------------------
#include "planttree.h"
#include <iostream>
#include <algorithm>
planttree::planttree(): m_root(nullptr) {}
planttree::~planttree()
{
delete m_root;
}
planttree::planttree(const planttree& copy): m_root(nullptr)
{
m_root = copyHelper(copy.m_root);
}
planttree& planttree::operator=(const planttree&)
{
// @todo
}
void planttree::setRoot(const plant& root)
{
m_root = new node(root);
}
void planttree::addChildren(const plant& parent, const plant& left, const plant& right)
{
node* curr = search(m_root, parent.getId());
if (curr != nullptr) {
curr->left = new node(left);
curr->right = new node(right);
}
}
void planttree::display()
{
preOrderPrint(m_root, 0);
}
void planttree::preOrderPrint(node* root, int height)
{
if ( root != nullptr ) {
int currentHeight = height;
while (currentHeight > 0) {
std::cout << " ";
currentHeight--;
}
std::cout << root->p << std::endl;
preOrderPrint(root->left, ++height);
preOrderPrint(root->right, height);
}
}
plant* planttree::findBestGrowth() const
{
return fbg(m_root);
}
plant* planttree::fbg(node* root) const
{
if (root == nullptr) {
return nullptr;
} else {
plant* left = (fbg(root->left) == nullptr) ? &(root->p) : fbg(root->left);
plant* right = (fbg(root->right) == nullptr) ? &(root->p) : fbg(root->right);
if (root->p.getGrowth() > left->getGrowth() && root->p.getGrowth() > right->getGrowth()) {
return &(root->p);
} else {
return (left->getGrowth() >= right->getGrowth()) ? left : right;
}
}
}
plant* planttree::findBestNutrition() const
{
return fbn(m_root);
}
plant* planttree::fbn(node* root) const
{
if (root == nullptr) {
return nullptr;
} else {
plant* left = (fbn(root->left) == nullptr) ? &(root->p) : fbn(root->left);
plant* right = (fbn(root->right) == nullptr) ? &(root->p) : fbn(root->right);
if (root->p.getNutrition() > left->getNutrition() && root->p.getNutrition() > right->getNutrition()) {
return &(root->p);
} else {
return (left->getNutrition() >= right->getNutrition()) ? left : right;
}
}
}
plant* planttree::findBestWater() const
{
return fbw(m_root);
}
plant* planttree::fbw(node* root) const
{
if (root == nullptr) {
return nullptr;
} else {
plant* left = (fbw(root->left) == nullptr) ? &(root->p) : fbw(root->left);
plant* right = (fbw(root->right) == nullptr) ? &(root->p) : fbw(root->right);
if (root->p.getWater() > left->getWater() && root->p.getWater() > right->getWater()) {
return &(root->p);
} else {
return (left->getWater() >= right->getWater()) ? left : right;
}
}
}
-----------------------------------------------------------------------------
planttree.h
----------------------------------------
#ifndef PLANTTREE_H
#define PLANTTREE_H
#include "plant.h"
#include <cstring>
class planttree {
private:
struct node {
plant p;
node* left;
node* right;
node(const plant& pl): left(nullptr), right(nullptr), p(pl) {}
~node() {
delete left;
delete right;
}
};
node* m_root;
void preOrderPrint(node*, int);
plant* fbg(node*) const;
plant* fbn(node*) const;
plant* fbw(node*) const;
node* copyHelper(node* root)
{
if (root == nullptr) {
return nullptr;
} else {
node* n = new node(root->p);
n->left = copyHelper(root->left);
n->right = copyHelper(root->right);
return n;
}
}
node* search(node* root, char* id)
{
if (root != nullptr) {
if (std::strncmp(root->p.getId(), id, strlen(id)+1) == 0) {
return root;
}
return (search(root->left, id) != nullptr) ? search(root->left, id) : search(root->right, id);
}
return nullptr;
}
public:
planttree();
~planttree();
planttree(const planttree&);
planttree& operator=(const planttree&);
void setRoot(const plant&);
void addChildren(const plant&, const plant&, const plant&);
void display();
plant* findBestGrowth() const;
plant* findBestNutrition() const;
plant* findBestWater() const;
};
#endif
--------------------------------------------------------------------------------------------------
testplant.cpp
-----------------------------------
#include <iostream>
#include "plant.h"
using namespace std;
void doSomething(plant p1)
{
cout << p1;
}
int main()
{
plant p1("001",1,1,1);
doSomething(p1);
return(0);
}
------------------------------------------------------------------------------------
testtree.cpp
----------------------------------------
#include <iostream>
#include "planttree.h"
using namespace std;
void testCopyConstructor(planttree pt)
{
cout << "-- Duplicate tree -- " << endl;
pt.display();
}
int main()
{
planttree* pt = new planttree();
plant p1("001",1,1,1);
plant p2("002",2,2,2);
plant p3("003",3,4,5);
pt->setRoot(p1);
pt->addChildren(p1,p2,p3);
plant p4("004",17,18,19);
plant p5("005",25,22,20);
plant p6("006",30,50,40);
plant p7("007",33,44,55);
pt->addChildren(p2,p4,p5);
pt->addChildren(p3,p6,p7);
pt->display();
testCopyConstructor(*pt);
const plant* bestPlant;
cout << "Best growth rate: " << endl;
bestPlant = pt->findBestGrowth();
cout << (*bestPlant) << endl;
cout << "Best nutritional value: " << endl;
bestPlant = pt->findBestNutrition();
cout << (*bestPlant) << endl;
cout << "Best water requirement: " << endl;
bestPlant = pt->findBestWater();
cout << (*bestPlant) << endl;
delete pt;
return(0);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.