#ifndef BST_H #define BST_H // Representation of an element in the tree struct N
ID: 3586399 • Letter: #
Question
#ifndef BST_H
#define BST_H
// Representation of an element in the tree
struct Node {
int val; // Value of the node
Node *left; // Pointer to the left node
Node *right; // Pointer to the right node
Node *parent; // Pointer to the parent node
};
class BST {
// Public Definitions
public:
enum TraversalOrder { InOrderTrav, PreOrderTrav, PostOrderTrav };
// Public Functions/Variables
public:
BST(); // Constructor
virtual ~BST(); // Destructor
void Insert(int toInsert);
void Delete(int toDelete);
void Print(enum TraversalOrder);
// Private Functions/Variables
private:
Node *root;
Node* Search(int toFind); // Searche for a node in the tree
Node* Successor(Node *curr); // Find the successor of the given node
Node* Minimum(Node *curr); // Find the minimum node of the given subtree
Node* Maximum(Node *curr); // Find the minimum node of the given subtree
void Transplant(Node *u, Node *v); // Replace the subtree rooted at node u with the subtree rooted at node v
void InOrder(Node *curr); // Inorder traversal
void PreOrder(Node *curr); // Preorder traversal
void PostOrder(Node *curr); // Postorder traversal
};
#endif
--------------------------------------------------------------------
cpp file:
#include <iostream>
#include <string>
#include "BST.h"
using namespace std;
/****************************************************************
* CONSTRUCTOR
* Creates an empty binary tree
****************************************************************/
BST::BST() {
}
/****************************************************************
* DESTRUCTOR
* Free all memory used by current tree
****************************************************************/
BST::~BST() {
// Write code to remove and deallocate all nodes in the tree
}
void BST::Insert(int toInsert) {
// Write your code here
}
void BST::Delete(int toDelete) {
// Write your code here
}
void BST::Transplant(Node *u, Node *v) {
// Write your code here
}
Node *BST::Successor(Node *x) {
// Write your code here
}
Node *BST::Minimum(Node *x) {
// Write your code here
}
Node *BST::Maximum(Node *x) {
// Write your code here
}
Node *BST::Search(int toFind) {
// Write your code here
}
void BST::Print(TraversalOrder Order) {
if(Order==InOrderTrav)
InOrder(root);
else if(Order==PreOrderTrav)
PreOrder(root);
else if(Order==PostOrderTrav)
PostOrder(root);
}
void BST::PreOrder(Node *x) {
// Write your code here
}
void BST::InOrder(Node *x) {
// Write your code here
}
void BST::PostOrder(Node *x) {
// Write your code here
}
-------------------------------------------
main.cpp
#include <sstream>
#include <iostream>
#include "BST.h"
using namespace std;
int main(int argc,char **argv) {
// Create an empty Binary Search Tree
BST Tree;
// Using a fixed size buffer for reading content is not always safe,
// but ok here because we know how our input has to be:
char line[100];
// Main loop
while ( std::cin.getline(line,100) ) {
string str(line);
if ( str.size()==0 ) continue;
if ( str[0]=='e' ) return 0;
// Use cerr if you want to always print to the console, because cout
// will be redirected to the output file when calling the Grade05 script:
// cerr<<line<<endl;
if ( str.substr(0,2)=="in" ) {
Tree.Print(BST::InOrderTrav);
cout << "++++++++++++++++++++" << endl;
}
else {
if ( str.substr(0,3)=="pre" ) {
Tree.Print ( BST::PreOrderTrav );
cout << "++++++++++++++++++++" << endl;
}
else {
if (str.substr(0,4) == "post") {
Tree.Print(BST::PostOrderTrav);
cout << "++++++++++++++++++++" << endl;
}
else {
int key;
stringstream convert_stm(str.substr(2, str.size()-1));
if ( !(convert_stm>>key) ) key = -1;
if (str.substr(0,1) == "i") Tree.Insert(key);
else if (str.substr(0,1) == "d") Tree.Delete(key);
}
}
}
}
return 0;
}
Description In this lab your goal is to implement standard operations on binary search trees, including insert and delete. See section 12.3 in the textbook. A sample class structure with empty methods, is given in the support code. You can either use the given class structure or create your own. In this assignment the keys are integers. You will use Grade04 to test your code. Your execution file name must be "BST.exe". Refer to the previous lab assignments for instructions on how to use the grading tool The input contains one of the following commands on a line » i key: Insert key into the BST. For example, "i 2" means "Insert key 2 into the BST" » d key: Delete key from the BST. For example, "d 2" means "Delete key 2 from the BST" Do nothing if the BST does not contain the key Output all keys in preorder » post: Output all keys in postorder in: Output all keys in inorder Finish your program Examples of input and output Input 1 i 5 i 7 d 7 d 7 pre d 1 postExplanation / Answer
main.cpp
-----------------------------------------------------------
#include <sstream>
#include <iostream>
#include "BST.h"
using namespace std;
int main(int argc,char **argv) {
// Create an empty Binary Search Tree
BST Tree;
// Using a fixed size buffer for reading content is not always safe,
// but ok here because we know how our input has to be:
char line[100];
// Main loop
while ( std::cin.getline(line,100) ) {
string str(line);
if ( str.size()==0 ) continue;
if ( str[0]=='e' ) return 0;
// Use cerr if you want to always print to the console, because cout
// will be redirected to the output file when calling the Grade05 script:
// cerr<<line<<endl;
if ( str.substr(0,2)=="in" ) {
Tree.Print(BST::InOrderTrav);
cout << "++++++++++++++++++++" << endl;
}
else {
if ( str.substr(0,3)=="pre" ) {
Tree.Print ( BST::PreOrderTrav );
cout << "++++++++++++++++++++" << endl;
}
else {
if (str.substr(0,4) == "post") {
Tree.Print(BST::PostOrderTrav);
cout << "++++++++++++++++++++" << endl;
}
else {
int key;
stringstream convert_stm(str.substr(2, str.size()-1));
if ( !(convert_stm>>key) ) key = -1;
if (str.substr(0,1) == "i") Tree.Insert(key);
else if (str.substr(0,1) == "d") Tree.Delete(key);
}
}
}
}
return 0;
}
----------------------------------------------------------------------------
BST.cpp
-------------------------------------------------
#include <iostream>
#include <string>
#include "BST.h"
using namespace std;
/****************************************************************
* CONSTRUCTOR
* Creates an empty binary tree
****************************************************************/
BST::BST() {
root->left == NULL;
root->right == NULL;
root->parent == NULL;
}
/****************************************************************
* DESTRUCTOR
* Free all memory used by current tree
****************************************************************/
BST::~BST() {
delete root;
}
void BST::Insert(int toInsert) {
Node *x = new Node;
Node *y = new Node;
Node *z = new Node;
y = NULL;
x = root;
z->val = toInsert;
z->left = NULL;
z->right = NULL;
while (x != NULL){
y = x;
if (toInsert < x->val)
x = x->left;
else x = x->right;
}
z->parent = y;
if (y == NULL)
root = z;
else if (z->val < y->val)
y->left = z;
else y->right = z;
}
void BST::Delete(int toDelete) {
Node *x = new Node;
Node *y = new Node;
x = Search(toDelete);
if (x->left == NULL)
Transplant(x, x->right);
else if (x->right == NULL)
Transplant(x, x->left);
else{
y = Minimum(x->right);
if (y->parent != x){
Transplant(y, y->right);
y->right = x->right;
y->right->parent = y;
}
Transplant(x, y);
y->left = x->left;
y->left->parent = y;
}
}
void BST::Transplant(Node *u, Node *v) {
if (u->parent == NULL){
root = v;
}
else if (u == u->parent->left){
u->parent->left = v;
}
else u->parent->right = v;
if (v != NULL)
v->parent = u->parent;
}
Node *BST::Successor(Node *x) {
if (x->right != NULL)
return Minimum(x->right);
Node *y = new Node;
y = x->parent;
while (y != NULL && x == y->right){
x = y;
y = y->parent;
}
return y;
}
Node *BST::Minimum(Node *x) {
while (x->left != NULL){
x = x->left;
}
return x;
}
Node *BST::Maximum(Node *x) {
while (x->right != NULL){
x = x->right;
}
return x;
}
Node *BST::Search(int toFind) {
Node* x = new Node;
x = root;
while (x != NULL && toFind != x->val){
if (toFind < x->val)
x = x->left;
else x = x->right;
}
return x;
}
void BST::Print(TraversalOrder Order) {
if(Order==InOrderTrav)
InOrder(root);
else if(Order==PreOrderTrav)
PreOrder(root);
else if(Order==PostOrderTrav)
PostOrder(root);
}
void BST::PreOrder(Node *x) {
if (x != NULL){
cout << x->val << endl;
PreOrder(x->left);
PreOrder(x->right);
}
}
void BST::InOrder(Node *x) {
if (x != NULL){
InOrder(x->left);
cout << x->val << endl;
InOrder(x->right);
}
}
void BST::PostOrder(Node *x) {
if (x != NULL){
PostOrder(x->left);
PostOrder(x->right);
cout << x->val << endl;
}
}
--------------------------------------------------------------------------------------------
BST.h
-----------------------------------------------------
#ifndef BST_H
#define BST_H
// Representation of an element in the tree
struct Node {
int val; // Value of the node
Node *left; // Pointer to the left node
Node *right; // Pointer to the right node
Node *parent; // Pointer to the parent node
};
class BST {
// Public Definitions
public:
enum TraversalOrder { InOrderTrav, PreOrderTrav, PostOrderTrav };
// Public Functions/Variables
public:
BST(); // Constructor
virtual ~BST(); // Destructor
void Insert(int toInsert);
void Delete(int toDelete);
void Print(enum TraversalOrder);
// Private Functions/Variables
private:
Node *root;
Node* Search(int toFind); // Searche for a node in the tree
Node* Successor(Node *curr); // Find the successor of the given node
Node* Minimum(Node *curr); // Find the minimum node of the given subtree
Node* Maximum(Node *curr); // Find the minimum node of the given subtree
void Transplant(Node *u, Node *v); // Replace the subtree rooted at node u with the subtree rooted at node v
void InOrder(Node *curr); // Inorder traversal
void PreOrder(Node *curr); // Preorder traversal
void PostOrder(Node *curr); // Postorder traversal
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.