can someone fix my code about tree in c++ to make it output like this: *******Ou
ID: 3807453 • Letter: C
Question
can someone fix my code about tree in c++ to make it output like this:
*******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 pointer
_________________________________
main.cpp:
#include
#include "BSTree.h"
using namespace std;
int main()
{
BSTree *obj = new BSTree();
obj->addNode(300);
obj->addNode(100);
obj->addNode(200);
obj->addNode(400);
obj->printPreorder(obj->Root());
cout<
obj->printInorder(obj->Root());
cout<
obj->printPostorder(obj->Root());
cout<
obj->findNode(100, obj->Root());
obj->findNode(200, obj->Root());
obj->findNode(300, obj->Root());
obj->findNode(500, obj->Root());
obj->findNode(600, obj->Root());
cout<<"MIN="<min(obj->Root())->Key()<
cout<<"MAX="<max(obj->Root())->Key()<
cout<<"Successor to 300="<successor(300, obj->Root())->Key()<
cout<<"Predecessorto 300="<predecessor(300, obj->Root())->Key()<
obj->deleteNode(300);
obj->printPreorder(obj->Root());
cout<
}
___________________________________
BSTree.h:
#ifndef BSTREE_
#define BSTREE_
#include
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 "BSTree.h"
// Constructor
BSTree::BSTree() {
root = nullptr;
}
// Destructor
BSTree::~BSTree() {
if (root !=nullptr)
freeNode(root);
}
// Free the node
void BSTree::freeNode(Node* leaf)
{
if ( this->Root() == leaf)
{
}
else if ( leaf != nullptr )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}
// Add a node
void BSTree::addNode(int key)
{
// No elements. Add the root
if ( root == nullptr ) {
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
std::cout<<"Adding "<
addNode(key, root);
}
}
// Add a node (private)
void BSTree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != nullptr )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != nullptr )
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)
{
if(node==NULL)
{
std::cout<<"Node "<
return NULL;
}
if( key == node->Key())
{
return node;
}
else if ( keyKey() )
{
if(node->Left()==NULL)
return NULL;
else
return this->findNode(key, node->Left());
}
else if(( key > node->Key() ))
{
if(node->Right()==NULL)
return NULL;
else
this->findNode(key, node->Right());
}
std::cout<<"Node "<
return NULL;
}
// Print the BSTree
void BSTree::printPreorder(Node* node)
{
std::cout<<"Preorder Print: ";
if ( node != nullptr)
{
std::cout<Key()<<" ";
this->printPreorder(node->Left());
this->printPreorder(node->Right());
}
}
void BSTree::printInorder(Node* node)
{
std::cout<<"Inorder Print: ";
if ( node != nullptr)
{
this->printInorder(node->Left());
std::cout<Key()<<" ";
this->printInorder(node->Right());
}
}
void BSTree::printPostorder(Node* node)
{
std::cout<<"Postorder Print: ";
if ( node != nullptr)
{
this->printPostorder(node->Left());
this->printPostorder(node->Right());
std::cout<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 == nullptr )
tempNode = nullptr;
else if ( node->Left() )
{
tempNode = min(node->Left());
}
else
tempNode = node;
//std::cout<<"MIN="<Key()<
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 == nullptr )
tempNode = nullptr;
else if ( node->Right() )
tempNode = max(node->Right());
else
tempNode = node;
// std::cout<<"MAX="<Key()<
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 = nullptr;
Node *current = root;
if(root == nullptr)
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 == nullptr)
{ return nullptr; }
if (current->Left() !=nullptr)
{
return max(current->Left());
} else
{
Node *tempParent = current->Parent();
while (tempParent !=nullptr) {
if (current == tempParent->Right() ){
break;
}
current = tempParent;
tempParent = current->Parent();
}
return tempParent;
}
}
void BSTree::deleteNode(int key)
{
if (deleteNode(Root(), key) == nullptr)
setRoot(nullptr);
else
std::cout<<"Deleting "<
}
//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 == nullptr) 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() == nullptr && root->Right() == nullptr){
delete root;
root = nullptr;
// Case 2: one child
} else if(root->Left() == nullptr){
Node *temp = root;
root = root->Right();
delete temp;
} else if(root->Right() == nullptr){
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;
}
________________________________
Node.h:
#ifndef NODE_
#define NODE_
#include
using namespace std;
#define nullptr NULL
// 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=nullptr; right=nullptr; parent = nullptr;};
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
________________
please only make changes to printPreorder, printInorder, printPostorder, and findNode member functions and main.cpp.
thanks for the help in advance!
will thump up.
Explanation / Answer
#include
#include "BSTree.h"
using namespace std;
int main()
{
BSTree *obj = new BSTree();
obj->addNode(300);
obj->addNode(100);
obj->addNode(200);
obj->addNode(400);
obj->printPreorder(obj->Root());
cout<
obj->printInorder(obj->Root());
cout<
obj->printPostorder(obj->Root());
cout<
obj->findNode(100, obj->Root());
obj->findNode(200, obj->Root());
obj->findNode(300, obj->Root());
obj->findNode(500, obj->Root());
obj->findNode(600, obj->Root());
cout<<"MIN="<min(obj->Root())->Key()<
cout<<"MAX="<max(obj->Root())->Key()<
cout<<"Successor to 300="<successor(300, obj->Root())->Key()<
cout<<"Predecessorto 300="<predecessor(300, obj->Root())->Key()<
obj->deleteNode(300);
obj->printPreorder(obj->Root());
cout<
}
___________________________________
BSTree.h:
#ifndef BSTREE_
#define BSTREE_
#include
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 "BSTree.h"
// Constructor
BSTree::BSTree() {
root = nullptr;
}
// Destructor
BSTree::~BSTree() {
if (root !=nullptr)
freeNode(root);
}
// Free the node
void BSTree::freeNode(Node* leaf)
{
if ( this->Root() == leaf)
{
}
else if ( leaf != nullptr )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}
// Add a node
void BSTree::addNode(int key)
{
// No elements. Add the root
if ( root == nullptr ) {
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
std::cout<<"Adding "<
addNode(key, root);
}
}
// Add a node (private)
void BSTree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != nullptr )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != nullptr )
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)
{
if(node==NULL)
{
std::cout<<"Node "<
return NULL;
}
if( key == node->Key())
{
return node;
}
else if ( keyKey() )
{
if(node->Left()==NULL)
return NULL;
else
return this->findNode(key, node->Left());
}
else if(( key > node->Key() ))
{
if(node->Right()==NULL)
return NULL;
else
this->findNode(key, node->Right());
}
std::cout<<"Node "<
return NULL;
}
// Print the BSTree
void BSTree::printPreorder(Node* node)
{
std::cout<<"Preorder Print: ";
if ( node != nullptr)
{
std::cout<Key()<<" ";
this->printPreorder(node->Left());
this->printPreorder(node->Right());
}
}
void BSTree::printInorder(Node* node)
{
std::cout<<"Inorder Print: ";
if ( node != nullptr)
{
this->printInorder(node->Left());
std::cout<Key()<<" ";
this->printInorder(node->Right());
}
}
void BSTree::printPostorder(Node* node)
{
std::cout<<"Postorder Print: ";
if ( node != nullptr)
{
this->printPostorder(node->Left());
this->printPostorder(node->Right());
std::cout<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 == nullptr )
tempNode = nullptr;
else if ( node->Left() )
{
tempNode = min(node->Left());
}
else
tempNode = node;
//std::cout<<"MIN="<Key()<
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 == nullptr )
tempNode = nullptr;
else if ( node->Right() )
tempNode = max(node->Right());
else
tempNode = node;
// std::cout<<"MAX="<Key()<
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 = nullptr;
Node *current = root;
if(root == nullptr)
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 == nullptr)
{ return nullptr; }
if (current->Left() !=nullptr)
{
return max(current->Left());
} else
{
Node *tempParent = current->Parent();
while (tempParent !=nullptr) {
if (current == tempParent->Right() ){
break;
}
current = tempParent;
tempParent = current->Parent();
}
return tempParent;
}
}
void BSTree::deleteNode(int key)
{
if (deleteNode(Root(), key) == nullptr)
setRoot(nullptr);
else
std::cout<<"Deleting "<
}
//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 == nullptr) 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() == nullptr && root->Right() == nullptr){
delete root;
root = nullptr;
// Case 2: one child
} else if(root->Left() == nullptr){
Node *temp = root;
root = root->Right();
delete temp;
} else if(root->Right() == nullptr){
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.