Language: C++ Use this code Node.hPreview the documentView in a new window, BSTr
ID: 3806962 • Letter: L
Question
Language: C++
Use this code Node.hPreview the documentView in a new window, BSTree.hPreview the documentView in a new window, BSTree.cppView in a new window to implement a binary search tree. Specifically, you will implement a printPreorder, printInorder, printPostorder, and findNode member functions. Do not make other changes to the Node.h or the BSTree.h. Ensure that you document any changes that you make in BSTree.cpp with your name at the top. We left the member function headers in the code, so you just need to fill in the code.
Demonstrate that you did this correctly by building a main program that uses these functions to build an output that looks very similar to HW08 Output.pngView in a new window. If you modified these on a Windows System, make sure to move to the csegrid and run dos2unix, before zipping and submitting to canvas. Make sure that you have a working/tested makefile and readme.txt file.
Node.h
----------------------------------------------------------------------------------------------------------------------------------------
BSTree.h
BSTree.cpp
Output:
Adding 100 Adding 200 Adding 400 Preorder print 300 100 200 400 Inorder print: 100 200 300 400 Postorder print 100 200 400 300 Node 500 not found Node 600 not found Min-100 Max 400 Successor to 300-400 Predecessor to 300-200 Deleting 300 Preorder print: 200 100 400 Deleting entire tree pointerExplanation / Answer
Node.h:
#ifndef NODE_
#define NODE_
#include <iostream>
using namespace std;
// A generic tree node class
//Placeholder for a composite data type
class Datatype{
private:
int number;
};
//Binary Tree Node
class Node {
private:
int key;
Datatype data;
Node* left;
Node* right;
Node* parent;
public:
Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
void setParent(Node* aParent) { parent = aParent; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
Node* Parent() { return parent; };
};
#endif
BSTree.h:
#ifndef BSTREE_
#define BSTREE_
#include <iostream>
using namespace std;
#include "Node.h"
// Binary Search Tree class
class BSTree {
private:
Node* root;
void addNode(int key, Node* leaf);
Node* deleteNode(Node* node, int key);
void freeNode(Node* leaf);
public:
BSTree();
~BSTree();
Node* Root() { return root; }
void setRoot(Node * _root) {root = _root;}
void addNode(int key);
Node* findNode(int key, Node* parent);
void printPreorder(Node* node);
void printInorder(Node* node);
void printPostorder(Node* node);
void deleteNode(int key);
Node* min(Node* node);
Node* max(Node* node);
Node* successor(int key, Node* parent);
Node* predecessor(int key, Node* parent);
};
#endif //BST
BSTree.cpp
#include <iostream>
#include "BSTree.h"
using namespace std;
// Constructor
BSTree::BSTree() {
root = NULL;
}
// Destructor
BSTree::~BSTree() {
if (root !=NULL)
freeNode(root);
}
// Free the node
void BSTree::freeNode(Node* leaf)
{
if ( this->Root() == leaf)
{
}
else if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}
// Add a node
void BSTree::addNode(int key)
{
// No elements. Add the root
if ( root == NULL) {
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
addNode(key, root);
}
}
// Add a node (private)
void BSTree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != NULL )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != NULL )
addNode(key, leaf->Right());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setRight(n);
}
}
}
// Find a node
Node* BSTree::findNode(int key, Node* node)
{
while(node!=NULL){
if(key==(node->Key()))
{
return node;
}else if(key<(node->Key())){
node=node->Left();
}else{
node=node->Right();
}
}
return NULL;
}
// Print the BSTree
void BSTree::printPreorder(Node* node)
{
if(node!=NULL){
std::cout<<node->Key()<<" ";
printPreorder(node->Left());
printPreorder(node->Right());
}
}
void BSTree::printInorder(Node* node)
{
if(node!=NULL){
printInorder(node->Left());
std::cout<<node->Key()<<" ";
printInorder(node->Right());
}
}
void BSTree::printPostorder(Node* node)
{
if ( node != NULL)
{
printPostorder(node->Left());
printPostorder(node->Right());
std::cout<<node->Key()<<" ";
}
}
// Find the node with min key
// Traverse the left sub-BSTree recursively
// till left sub-BSTree is empty to get min
Node* BSTree::min(Node* node)
{
Node* tempNode = node;
if ( node == NULL )
tempNode = NULL;
else if ( node->Left() )
{
tempNode = min(node->Left());
}
else
tempNode = node;
return tempNode;
}
// Find the node with max key
// Traverse the right sub-BSTree recursively
// till right sub-BSTree is empty to get max
Node* BSTree::max(Node* node)
{
Node * tempNode = node;
if ( node == NULL )
tempNode = NULL;
else if ( node->Right() )
tempNode = max(node->Right());
else
tempNode = node;
return tempNode;
}
// Find successor to a node
// Find the node, get the node with max value
// for the right sub-BSTree to get the successor
Node* BSTree::successor(int key, Node *node)
{
Node *successor = NULL;
Node *current = root;
if(root == NULL)
return NULL;
while(current->Key() != key){
/* If node value is greater than the node which are looking for, then go to left sub tree
Also when we move left, update the successor pointer to keep track of lst left turn */
if(current->Key() >key){
successor = current;
current= current->Left();
}
/* Else take right turn and no need to update successor pointer */
else
current = current->Right();
}
/*Once we reached at the node for which inorder successor is to be found, check if it has right sub tree, if yes then find the minimum in that right sub tree and return that node
Else last left turn taken node is already stored in successor pointer and will be returned*/
if(current && current->Right()){
successor = min(current->Right());
}
return successor;
}
// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-BSTree to get the predecessor
Node* BSTree::predecessor(int key, Node *node)
{
Node* current = findNode(key, node);
if (current == NULL)
{ return NULL; }
if (current->Left() !=NULL)
{
return max(current->Left());
} else
{
Node *tempParent = current->Parent();
while (tempParent !=NULL) {
if (current == tempParent->Right() ){
break;
}
current = tempParent;
tempParent = current->Parent();
}
return tempParent;
}
}
void BSTree::deleteNode(int key)
{
if (deleteNode(Root(), key) == NULL)
setRoot(NULL);
}
//deleteNode (Private)
Node* BSTree::deleteNode(Node* root,int key)
{
/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
if(root == NULL) return root;
else if(key < root->Key())
root->setLeft( deleteNode(root->Left(),key));
else if(key > root->Key())
root->setRight( deleteNode(root->Right(), key) );
else {
// Case 1: No Child
if(root->Left() == NULL && root->Right() == NULL){
delete root;
root = NULL;
// Case 2: one child
} else if(root->Left() == NULL){
Node *temp = root;
root = root->Right();
delete temp;
} else if(root->Right() == NULL){
Node *temp = root;
root = root->Left();
delete temp;
} else{
Node *temp = min(root->Right());
root->setKey(temp->Key() );
root->setRight( deleteNode(root->Right(), temp->Key() ) );
}
}
return root;
}
int main()
{
BSTree tree;
cout<<"Adding 300"<<endl;
tree.addNode(300);
cout<<"Adding 100"<<endl;
tree.addNode(100);
cout<<"Adding 200"<<endl;
tree.addNode(200);
cout<<"Adding 400"<<endl;
tree.addNode(400);
cout<<endl<<endl;
cout<<"Preorder Print:"<<endl;
tree.printPreorder(tree.Root());
cout<<endl<<endl<<"Inorder Print:"<<endl;
tree.printInorder(tree.Root());
cout<<endl<<endl<<"Postorder Print:"<<endl;
tree.printPostorder(tree.Root());
if(tree.findNode(500,tree.Root())==NULL)
cout<<endl<<endl<<"Node 500 not found!"<<endl;
if(tree.findNode(600,tree.Root())==NULL)
cout<<"Node 600 not found!"<<endl;
cout<<endl<<endl<<"Min = "<<tree.min(tree.Root())->Key()<<endl;
cout<<"Max = "<<tree.max(tree.Root())->Key()<<endl;
cout<<endl<<endl<<"Successor to 300: "<<tree.successor(300,tree.Root())->Key()<<endl;
cout<<"predecessor to 300: "<<tree.predecessor(300,tree.Root())->Key()<<endl;
cout<<"Deleting 300"<<endl;
tree.deleteNode(300);
cout<<endl<<"Preorder Print:"<<endl;
tree.printPreorder(tree.Root());
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.