Question:: Please implement the few functions ONLY TWO FILES: main.cpp and BST.h
ID: 3890466 • Letter: Q
Question
Question:: Please implement the few functions
ONLY TWO FILES: main.cpp and BST.h
-The big five for the BST, printLevelOrderHelper and returnLevelOrderHelper.
To ensure that it passes all the tests.
/*-------------------- BST.H ----------------------*/
#ifndef __BST_H
#endif
/* ---------------------main.cpp----------------- */
}
Question:: Please implement the few functions
ONLY TWO FILES: main.cpp and BST.h
-The big five for the BST, printLevelOrderHelper and returnLevelOrderHelper.
To ensure that it passes all the tests.
/*-------------------- BST.H ----------------------*/
#ifndef __BST_H
Explanation / Answer
#define BST_H_
#ifndef BST_H_
#include <iostream>
#include <stdexcept>
#include "bnode.h"
using namespace std;
//template class
template <typename T>
class BST
{
//pointer pointing to root node of BST
BinaryTreeNode<T>* rootnode;
public:
//default constructor
BST();
void insert_BST(T value);
bool search_BST(const T& nodevalue) const;
bool search_BST(BTNode<T>* node, const T& nodevalue) const;
void InOrder_BST() const;
void remove_BSTnode(const T& nodevalue);
void print_BST() const;
private:
//recursive function for print_BST
void print_BST(BTNode<T>* node,int depth_of_BST) const;
};
template <typename T>
BST<T>::BST()
{
rootnode = NULL;
}
template <typename T>
void BST<T>::insert_BST(T nodevalue)
{
BTNode<T>* newBSTNode = new BTNode<T>(nodevalue);
cout << newBSTNode->data;
if(rootnode == NULL)
{
rootnode= newBSTNode;
return;
}
BTNode<T>* currentnode = rootnode;
while(1)
{
if(currentnode->left == NULL && currentnode->right == NULL)
break;
if(currentnode->right != NULL && currentnode->left != NULL)
{
if(newBSTNode->data > currentnode->data)
currentnode = currentnode->right;
else if(newBSTNode->data < currentnode->data)
currentnode = currentnode->left;
}
else if(currentnode->right != NULL && currentnode->left == NULL)
{
if(newBSTNode->data < currentnode->data)
break;
else if(newBSTNode->data > currentnode->data)
currentnode = currentnode->right;
}
else if(currentnode->right == NULL && currentnode->left != NULL)
{
if(newBSTNode->data > currentnode->data)
break;
else if(newBSTNode->data < currentnode->data)
currentnode = currentnode->left;
}
}
if(currentnode->data > newBSTNode->data)
{
currentnode->left = newBSTNode;
cout << ¤tnode << "ADDITION" << endl;
cout << ¤tnode->left << "Left ADDITION" << endl;
cout << ¤tnode->right << "Right ADDITION" << endl;*/
}
else
{
currentnode->right = newBSTNode;
cout << ¤tnode << "ADDITION AT ROOT" << endl;
cout << ¤tnode->left << "LEFT ADDITION" << endl;
cout << ¤tnode->right << "RIGHT ADDITION" << endl;*/
}
return;
}
//public helper
template <typename T>
bool BST<T>::search_BST(const T& nodevalue) const
{
return(search_BST(rootnode,nodevalue)); //begins at root
}
//recursion function
template <typename T>
bool BST<T>::search_BST(BTNode<T>* cnode, const T& nodevalue) const
{
if(cnode == NULL || cnode->data == value)
return(cnode != NULL);
else if(nodevalue < cnode->data)
return search_BST(cnode->left,nodevalue); //searches the left subtree
else
return search_BST(cnode->right,nodevalue); //searches the right subtree
}
template <typename T>
void BST<T>::InOrder() const
{
//print values in inorder form
}
template <typename T>
void BST<T>::remove_BST(const T& nvalue)
{
if(rootnode == NULL)
{
cout << "Empty tree. "<<endl;
return;
}
if(!search_BST(nvalue))
{
cout << "Value not found in tree ,hence cannot remove anything" << endl;
return;
}
BTNode<T>* currentnode = rootnode;
BTNode<T>* parentnode;
cout << rootnode->data << " ROOT node" << endl;
cout << currentnode->data << "CURRENT node" << endl;
while(currentnode != NULL)
{
if(rootnode->data == nvalue)
{
delete currentnode;
return;
}
else if(nvalue > currentnode->data)
{
parentnode = currentnode;
currentnode = currentnode->right;
}
else
{
parentnode = currentnode;
currentnode = currentnode->left;
}
}
cout << currentnode->data << "AFTER CURRENT" << endl;
// Three cases :
if(currentnode->left == NULL && currentnode->right == NULL) // This is a leaf
{
if(parentnode== currentnode)
delete parentnode;
else if(parentnode->left == current)
{
parentnode->left = NULL;
delete currentnode;
}
else
{
parentnode->right = NULL;
delete currentnode;
}
cout << "Entered value " << value << " is removed." << “ ”;
return;
}
// Node having a single child
if((currentnode->left == NULL && currentnode->right != NULL) || (currentnode->left != NULL && currentnode->right == NULL))
{
if(currentnode->left == NULL && currentnode->right != NULL)
{
if(parentnode->left == currentnode)
{
parentnode->left = currentnode->right;
cout << "Input value " << nvalue << " is successfully removed." << endl;
delete currentnode;
}
else
{
parentnode->right = currentnode->right;
cout << "Desired value " << nvalue << " is successfully removed." << endl;
delete currentnode;
}
}
else // has only left child
{
if(parentnode->left == currentnode)
{
parentnode->left = currentnode->left;
cout << "Desired value " << nvalue << " is successfully removed." << endl;
delete currentnode;
}
else
{
parentnode->right = currentnode->left;
cout << "Desired value " << nvalue << " is successfully removed." << endl;
delete currentnode;
}
}
return;
}
//If a node having 2 children , Replace it with a node having least value in rightsubtree.
if (currentnode->left != NULL && currentnode->right != NULL)
{
BTNode<T>* checkBST;
check BST= currentnode->right;
if((checkBST->left == NULL) && (checkBST->right == NULL))
{
currentnode = checkBST;
delete checkBST;
currentnode->right = NULL;
cout << "Desired value " << nvalue << " was successfully removed." << “ ”;
}
else // when a right child is present
{
if((currentnode->right)->left != NULL)
{
BTNode<T>* leftCurrentnode;
BTNode<T>* leftParentnode;
leftParentnode = currentnode->right;
leftCurrentnode = (currentnode->right)->left;
while(leftCurrentnode->left != NULL)
{
leftParentnode = leftCurrentnode;
leftCurrentnode = leftCurrentnode->left;
}
currentnode->data = leftCurrentnode->data;
delete leftCurrentnode;
leftParentnode->left = NULL;
cout << "Desired value " << nvalue << " is successfully removed." << “ ”;
}
else
{
BTNode<T>* tempnode;
tempnode = currentnode->right;
currentnode->data = tempnode->data;
currentnode->right = tempnode->right;
delete tempnode;
cout << "Desired value " << nvalue << " is successfully removed." << “ ”;
}
}
return;
}
}
/*Sample output
25
19
18
11
9
4
2
1
*/
template <typename T>
void BST<T>::print_BST() const
{
print_BST(rootnode,0);
}
template <typename T>
void BST<T>::print_BST(BTNode<T>* bnode,int depthoftree) const
{
if(bnode == NULL)
{
std::cout << std::endl;
}
print(bnode->right,depthoftree+1);
for(int j=0; j < depthoftree; j++)
{
std::cout << " ";
}
std::cout <<bnode->data << std::endl;
print(bnode->left,depthoftree+1);
}
#endif
main.cpp
#include "bst.h"
#include <iostream.h>
int main()
{
BST<int> btree;
cout << “ ” << "BST IMPLEMENTATION" << “ ”;
cout << "----------------------------------------------------------" << endl;
// Insertion
cout << “ ” << "INSERTION TESTS BEGINS" << endl; // duplicates are never allowed.
tree.insert_BST(1);
tree.insert_BST(4);
tree.insert_BST(14);
tree.insert_BST(21);
tree.insert_BST(19);
// Searching BST
cout << “ ” << "BSTSEARCH TEST BEGINS" << endl;
int y = 1;
int z = 0;
if(tree.search_BST(y))
cout << "Value " << y << " is found in bst tree." << endl;
else
cout << "Value " << y << " is NOT found in BST tree." << endl;
if(tree.search_BST(z))
cout << "Value " << z << " is found in BST tree." << “ ”;
else
cout << "Value " <<z<< " is NOT found in BST tree." << “ ”;
// Remove function
cout << “ ”<< "REMOVE TEST BEGINS" << “ ”;
tree.remove_BST(1);
tree.remove_BST(4);
tree.remove_BST(14);
// Display function
cout << “ ” << “BINARY SEARCH TREE DIAGRAM" << “ ”;
cout << "----------------------------------------------------------" << “ ”;
tree.print_BST();
cout << “ ”<< "Program ends" << endl ;
}
BNode.h
#define BNODE_H_
#ifndef BNODE_H_
#include <iostream>
template <typename T>
class BNode
{
public:
//constructor
BNode(T da);
T data;
BNode<T>* left; BNode<T>* right;
};
template <typename T>
BNode<T>::BNode(T da)
: left(NULL), right(NULL)
{
data = da;
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.