In c++ format, for each function in the code, please using the comments fill in

Question

In c++ format, for each function in the code, please using the comments fill in the code and write the whole program.

#include <cstddef>

#include <string>

using namespace std;

template <class bstdata>

class BST

{

private:

struct Node

{

bstdata data;

Node* left;

Node* right;

Node(bstdata newdata): data(newdata), left(NULL), right(NULL) {}

};

typedef struct Node* NodePtr;

NodePtr root;

/**Private helper functions*/

void insertHelper(NodePtr root, bstdata value);

//private helper function for insert

//recursively inserts a value into the BST

void destructorHelper(NodePtr root);

//private helper function for the destructor

//recursively frees the memory in the BST

void inOrderPrintHelper(NodePtr root);

//private helper function for inOrderPrint

//recursively prints tree values in order from smallest to largest

void preOrderPrintHelper(NodePtr root);

//private helper function for preOrderPrint

//recursively prints tree values in preorder

void postOrderPrintHelper(NodePtr root);

//private helper function for postOrderPrint

//recursively prints tree values in postorder

bstdata maximumHelper(NodePtr root);

       //recursively searches for the maximum value in the Binary Search Tree

       bstdata minimumHelper(NodePtr root);

       //recursively locates the minimum value in the tree

       //returns this value once it is located

       void getSizeHelper(Nodeptr root, int& size);

       //recursively calculates the size of the tree

       int getHeightHelper(NodePtr root);

       //recursively calculates the height of the tree

       bool findHelper(NodePtr root, bstdata value);

       //recursively searches for value in the tree

       void remove(NodePtr root, bstdata value);

       //recursively removes the specified value from the tree

       void copyHelper(NodePtr copy);

       //recursively makes a deep copy of a binary search tree

/**Public functions*/

public:

   add the constructor

BST();

//Instantiates a new Binary Search Tree

//post: a new Binary Search Tree object

Add the following copy constructor:

       BST(const BST& tree);

       //makes a deep copy of tree

       //Calls the copyHelper function to make a copy recursively

       destructor

~BST();

//frees the memory of the BST object

//All memory has been deallocated

bool isEmpty();

//determines whether the Binary Search Tree is empty

void insert(bstdata value);

//inserts a new value into the Binary Search Tree

//post: a new value inserted into the Binary Search Tree

bstdata getRoot();

//returns the value stored at the root of the Binary Search Tree

//pre: the Binary Search Tree is not empty

void inOrderPrint();

//calls the inOrderPrintHelper function to print out the values

//stored in the Binary Search Tree

//If the tree is empty, prints nothing

void preOrderPrint();

//calls the preOrderPrintHelper function to print out the values

//stored in the Binary Search Tree

//If the tree is empty, prints nothing

void postOrderPrint();

//calls the postOrderPrintHelper function to print out the values

//stored in the Binary Search Tree

//If the tree is empty, prints nothing

       bstdata maximum();

       //finds the maximum value in the Binary Search Tree and returns it

       //calls the maximumHelper function to search for the max recursively

       //pre: !isEmpty()

       bstdata minimum();

       //calls the minimumHelper function to return the minimum value in the tree

       //Pre: the tree is not empty

       int getSize();

       //returns the size of the tree

       //calls the getSizeHelper function to calculate the size recursively

       int getHeight();

       //recursively finds the height of the tree and returns it

       //calls the getHeight helper function to calculate the height recursively

       //returns -1 if the tree is empty

       bool find(bstdata value);

       //returns whether the value is in the tree

       //calls the findHelper function to search for the value recursively

       //Pre: !isEmpty()

       void remove(bstdata value);

       //removes the specified value from the tree

       //Pre: !isEmpty()

       //Pre: The value is contained in the Binary Search Tree

       //If the value is not in the Binary Search Tree, the tree is left unchanged

};

Explanation / Answer

BinarySearchTree.h completed file:
#ifndef BINARYSEARCHTREE_H_
#define BINARYSEARCHTREE_H_
#include <cstddef>
#include <string>
#include <assert.h>
using namespace std;
template<class bstitem>
class BinarySearchTree {
private:
struct Node {
bstitem data;
Node* left;
Node* right;
Node(bstitem newdata) :
data(newdata), left(NULL), right(NULL) {
}
};
typedef struct Node* NodePtr;
NodePtr root;
/**Private helper functions*/
void insertHelper(NodePtr root, bstitem value);
//private helper function for insert
//recursively inserts a value into the BST
void inOrderPrintHelper(NodePtr root);
//private helper function for inOrderPrint
//recursively prints tree values in order from smallest to largest
void preOrderPrintHelper(NodePtr root);
//private helper function for preOrderPrint
//recursively prints tree values in preorder
void postOrderPrintHelper(NodePtr root);
//private helper function for postOrderPrint
//recursively prints tree values in postorder
bool findHelper(NodePtr root, bstitem value);
bstitem minimumHelper(NodePtr root);
bstitem maximumHelper(NodePtr root);
NodePtr removeHelper(NodePtr root, bstitem value);
int getSizeHelper(NodePtr root);
int getHeightHelper(NodePtr root);
void destructorHelper(NodePtr root);
Node& copyHelper(NodePtr root, const BinarySearchTree &binarysearchtree);
/**Public functions*/
public:
BinarySearchTree();
//Instantiates a new Binary Search Tree
//post: a new Binary Search Tree object
~BinarySearchTree();
BinarySearchTree(const BinarySearchTree &binarysearchtree);
//Access functions
bstitem minimum();
//finds the minimum value in the Binary Search Tree and returns it
//pre: !isEmpty()
bstitem maximum();
//finds the maximum value in the Binary Search Tree and returns it
//pre: !isEmpty()
bool isEmpty();
//returns whether the tree is empty
int getSize();
//returns the size of the tree
bstitem getRoot();
//returns the value stored at the root of the tree
//Pre: !isEmpty()
int getHeight();
//recursively finds the height of the tree and returns it
//Pre: !isEmpty()
bool find(bstitem value);
//returns whether the value is in the tree
//Pre: !isEmpty()
//Maniupulation functions
void insert(bstitem value);
//adds the specified value to the tree
void remove(bstitem value);
//removes the specified value from the tree
//Pre: !isEmpty()
//Pre: The value is contained in the Binary Search Tree
//Additional functions
void inOrderPrint();
// recursively prints the values contained in the Binary Search Tree
// according to an in order traversal
void preOrderPrint();
//recursively prints the values contained in the Binary Search Tree
// according to a pre order traversal
void postOrderPrint();
//recursively prints the values contained in the Binary Search Tree
// according to a post order traversal
};
template<class bstitem>
BinarySearchTree<bstitem>::BinarySearchTree() :
root(NULL) {
}
template<class bstitem>
void BinarySearchTree<bstitem>::destructorHelper(NodePtr root) {
if (root) {
if (root->left)
destructorHelper(root->left);
if (root->right)
destructorHelper(root->right);
delete root;
}
}
template<class bstitem>
BinarySearchTree<bstitem>::~BinarySearchTree() {
destructorHelper(root);
}
/*template<class bstitem>
Node& BinarySearchTree<bstitem>::copyHelper(NodePtr copyRoot, NodePtr root) {
if (root == NULL)
copyRoot = NULL;
else {
copyRoot = new Node(root->data);
copyRoot->left = copyHelper(copyRoot->left, root->left);
copyRoot->right = copyHelper(copyRoot->right, root->right);
}
}
template<class bstitem>
BinarySearchTree<bstitem>::BinarySearchTree(
const BinarySearchTree &binarysearchtree) {
root = copyHelper(root, &binarysearchtree);
}*/
template<class bstitem>
void BinarySearchTree<bstitem>::insert(bstitem value) {
{
if (root == NULL) {
root = new Node(value);
} else {
insertHelper(root, value);
}
}
}
template<class bstitem>
void BinarySearchTree<bstitem>::insertHelper(NodePtr root, bstitem value) {
if (value == root->data)
return;
else if (value < root->data) {
if (root->left == NULL)
root->left = new Node(value);
else
insertHelper(root->left, value);
} else {
if (root->right == NULL)
root->right = new Node(value);
else
insertHelper(root->right, value);
}
}
template<class bstitem>
void BinarySearchTree<bstitem>::inOrderPrintHelper(NodePtr root) {
if (root != NULL) {
inOrderPrintHelper(root->left);
cout << root->data << " ";
inOrderPrintHelper(root->right);
}
}
template<class bstitem>
void BinarySearchTree<bstitem>::inOrderPrint() {
inOrderPrintHelper(root);
cout << endl;
}
template<class bstitem>
void BinarySearchTree<bstitem>::preOrderPrintHelper(NodePtr root) {
if (root != NULL) {
cout << root->data << " ";
preOrderPrintHelper(root->left);
preOrderPrintHelper(root->right);
}
}
template<class bstitem>
void BinarySearchTree<bstitem>::preOrderPrint() {
preOrderPrintHelper(root);
cout << endl;
}
template<class bstitem>
void BinarySearchTree<bstitem>::postOrderPrintHelper(NodePtr root) {
if (root != NULL) {
postOrderPrintHelper(root->left);
postOrderPrintHelper(root->right);
cout << root->data << " ";
}
}
template<class bstitem>
void BinarySearchTree<bstitem>::postOrderPrint() {
postOrderPrintHelper(root);
cout << endl;
}
template<class bstitem>
bool BinarySearchTree<bstitem>::findHelper(NodePtr root, bstitem value) {
if (value == root->data)
return true;
else if (value < root->data) {
if (root->left == NULL)
return false;
else
findHelper(root->left, value);
} else {
if (root->right == NULL)
return false;
else
findHelper(root->right, value);
}
}
template<class bstitem>
bool BinarySearchTree<bstitem>::find(bstitem value) {
assert(!isEmpty());
if (value == root->data)
return true;
else
return findHelper(root, value);
}
template<class bstitem>
bstitem BinarySearchTree<bstitem>::minimumHelper(NodePtr root) {
while (root->left != NULL) {
root = root->left;
}
return root->data;
}
template<class bstitem>
bstitem BinarySearchTree<bstitem>::minimum() {
assert(!isEmpty());
return minimumHelper(root);
}
template<class bstitem>
bstitem BinarySearchTree<bstitem>::maximumHelper(NodePtr root) {
while (root->right != NULL) {
root = root->right;
}
return root->data;
}
template<class bstitem>
bstitem BinarySearchTree<bstitem>::maximum() {
assert(!isEmpty());
return maximumHelper(root);
}
template<class bstitem>
bool BinarySearchTree<bstitem>::isEmpty() {
return (root == NULL);
}
template<class bstitem>
bstitem BinarySearchTree<bstitem>::getRoot() {
assert(!isEmpty());
return root->data;
}
template<class bstitem>
int BinarySearchTree<bstitem>::getSizeHelper(NodePtr root) {
if (root == NULL) {
return 0;
} else {
return (1 + getSizeHelper(root->left) + getSizeHelper(root->right));
}
}
template<class bstitem>
int BinarySearchTree<bstitem>::getSize() {
return getSizeHelper(root);
}
template<class bstitem>
typename BinarySearchTree<bstitem>::NodePtr BinarySearchTree<bstitem>::removeHelper(
NodePtr root, bstitem value) {
if (root == NULL)
return root;
else if (value < root->data)
root->left = removeHelper(root->left, value);
else if (value > root->data)
root->right = removeHelper(root->right, value);
else {
if (root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
} else if (root->left != NULL && root->right == NULL) {
NodePtr temp = root;
root = root->left;
delete temp;
} else if (root->left == NULL && root->right != NULL) {
NodePtr temp = root;
root = root->right;
delete temp;
} else {
root->data = minimumHelper(root->right);
root->right = removeHelper(root->right, minimumHelper(root->right));
}
}
return root;
}
template<class bstitem>
void BinarySearchTree<bstitem>::remove(bstitem value) {
assert(!isEmpty());
assert(find(value));
root = removeHelper(root, value);
}
template<class bstitem>
int BinarySearchTree<bstitem>::getHeightHelper(NodePtr root) {
if (root == NULL) {
return -1;
} else {
return (max(getHeightHelper(root->left), getHeightHelper(root->right))
+ 1);
}
}
template<class bstitem>
int BinarySearchTree<bstitem>::getHeight() {
assert(!isEmpty());
return getHeightHelper(root);
}
#endif /* BINARYSEARCHTREE_H_ */

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.