In c++ format please, for each function in the code, using the comments fill in
ID: 3794854 • Letter: I
Question
In c++ format please, for each function in the code, using the comments fill in the function to 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
/**Public functions*/
public:
BST();
//Instantiates a new Binary Search Tree
//post: a new Binary Search Tree object
~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
};
Explanation / Answer
Below code is completed with the function prototypes :
#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){
if(root==NULL)
{
NodePtr *newnode=new node;
newnode->data=value;
root=newnode;
}
else{
if(value<root->data)
insertHelper(value,root->left);
else
insertHelper(value,root->right);
}
}
//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){
if (root != NULL)
{
inorder(root->left);
cout<<root->data<<endl;
inorder(root->right);
}
}
//private helper function for inOrderPrint
//recursively prints tree values in order from smallest to largest
void preOrderPrintHelper(NodePtr root){
if (root != NULL)
{
cout<<root->data<<endl;
inorder(root->left);
inorder(root->right);
}
}
//private helper function for preOrderPrint
//recursively prints tree values in preorder
void postOrderPrintHelper(NodePtr root){
if (root != NULL)
{
inorder(root->left);
inorder(root->right);
cout<<root->data<<endl;
}
}
//private helper function for postOrderPrint
//recursively prints tree values in postorder
/**Public functions*/
public:
BST(){
Node node= new Node();
}
//Instantiates a new Binary Search Tree
//post: a new Binary Search Tree object
~BST(){
delete left;
delete right;
}
//frees the memory of the BST object
//All memory has been deallocated
bool isEmpty(){
if(root==NULL)
return 1;
return 0;
}
//determines whether the Binary Search Tree is empty
void insert(bstdata value){
if( root == NULL ) // if tree is empty
{
root = new Node(value);
}
else
{
Node *ptr = root;
Node *prev = NULL;
while( ptr != NULL )
{
prev = ptr;
if( ptr->data == value )//no duplicates allowed in BST
return false;
else if( ptr->data < value )
{
ptr = ptr->right;
}
else
{
ptr = ptr->left;
}
}
if( prev->data < value ) //to be added as right child?
prev->right= new Node(value) ;
else
prev->left= new Node(value) ;
}
}
//inserts a new value into the Binary Search Tree
//post: a new value inserted into the Binary Search Tree
bstdata getRoot(){
return root->data;
}
//returns the value stored at the root of the Binary Search Tree
//pre: the Binary Search Tree is not empty
void inOrderPrint(){
inOrderPrint(NodePtr root);
}
//calls the inOrderPrintHelper function to print out the values
//stored in the Binary Search Tree
//If the tree is empty, prints nothing
void preOrderPrint(){
preOrderPrintHelper(NodePtr root);
}
//calls the preOrderPrintHelper function to print out the values
//stored in the Binary Search Tree
//If the tree is empty, prints nothing
void postOrderPrint(){
postOrderPrintHelper(NodePtr root);
}
//calls the postOrderPrintHelper function to print out the values
//stored in the Binary Search Tree
//If the tree is empty, prints nothing
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.