//Complete the functions for getHeight, postorder and preorder tree traversal in
ID: 3603357 • Letter: #
Question
//Complete the functions for getHeight, postorder and preorder tree traversal in the btree class below and show execution screen shot,
//also comment the new functions
//typed
//c++
using namespace std;
#include <iostream>
using namespace std;
//Node class
class Node{
int key;
Node* left;
Node* right;
public:
Node() //constructor
{ key = -1; left = NULL; right = NULL;}
void setKey(int item)
{ key = item;}
void setLeft(Node* lefty)
{ left = lefty;}
void setRight(Node* righty)
{ right = righty;}
int getKey()
{ return key;}
Node* getLeft()
{ return left;}
Node* getRight()
{ return right;}
}; //class Node
//tree class
class Tree{
Node* root;
public:
Tree(); //constructor
~Tree(); //destructor
Node* getRoot()
{ return root;}
void addNode(int key);
void inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
void addNode(int key, Node* leaf); //overloaded constructor
void freeNode(Node* leaf); //destructor
};
//Constructor
Tree::Tree()
{ root = NULL;}
//Destructor
Tree::~Tree()
{ freeNode(root);}
void Tree::freeNode(Node* leaf)
{
if(leaf !=NULL)
{
freeNode(leaf->getLeft());
freeNode(leaf->getRight());
delete leaf;
}
}//freeNode
//Add node
void Tree::addNode(int key)
{
if(root == NULL) //if empty tree
{
cout << "add a root node: " << key << endl;
Node* temp = new Node();
temp ->setKey(key);
root = temp;
}
else
{
addNode(key, root);
cout << "add new node: "<< key << endl;
}
}//addNode
void Tree::addNode(int key, Node* parent) //overloaded function
{
//if key < value at parent go left
if(key < parent->getKey())
{
if(parent -> getLeft() == NULL) //if left is empty
{
Node* n = new Node(); //create new node
n->setKey(key); //store it's key value
parent->setLeft(n); //have parent's left point to this node
}
else //if parent already has a left child
{
addNode(key, parent->getLeft()); //do the function again with this node as the parent
}
}
//if key >= value at parent go right
else
{
if(parent->getRight() == NULL) //if right child is empty
{
Node* n = new Node(); //create new node
n->setKey(key); //store it's key value
parent->setRight(n); //have parent's right point to this node
}
else //if parent has a right child
{
addNode(key, parent->getRight());
}
}
}//addNode
void Tree::inOrder(Node* n)
{
if(n) //keep going as long as there is a node available
{
inOrder(n->getLeft()); //grab key of left child
cout << n->getKey()<<" "; //print parent key
inOrder(n->getRight());//grab key of right child
}
}
int main() {
Tree* tree = new Tree();
tree->addNode(30);
tree->addNode(10);
tree->addNode(70);
tree->addNode(20);
tree->addNode(40);
tree->addNode(5);
tree->addNode(50);
tree->addNode(10);
cout<< " Tree height: " <<tree->getHeight(tree->getRoot()) << endl;
cout << "In order traversal" << endl;
tree->inOrder(tree->getRoot());
cout << endl;
cout << "Pre order traversal" << endl;
tree->preOrder(tree->getRoot());
cout << endl;
cout << "Post order traversal" << endl;
tree->postOrder(tree->getRoot());
cout << endl;
delete tree;
return 0;
}
Explanation / Answer
using namespace std;
#include <iostream>
using namespace std;
//Node class
class Node{
int key;
Node* left;
Node* right;
public:
Node() //constructor
{ key = -1; left = NULL; right = NULL;}
void setKey(int item)
{ key = item;}
void setLeft(Node* lefty)
{ left = lefty;}
void setRight(Node* righty)
{ right = righty;}
int getKey()
{ return key;}
Node* getLeft()
{ return left;}
Node* getRight()
{ return right;}
}; //class Node
//tree class
class Tree{
Node* root;
public:
Tree(); //constructor
~Tree(); //destructor
Node* getRoot()
{ return root;}
void addNode(int key);
void inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
void addNode(int key, Node* leaf); //overloaded constructor
void freeNode(Node* leaf); //destructor
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.