Write a C++ program which allows the ‘showMenu()’ function below to work. You sh
ID: 3741539 • Letter: W
Question
Write a C++ program which allows the ‘showMenu()’ function below to work. You should add (menu option #1) at least 5 items in the BST, before you select any other options. Run you program to show all options on the menu work correct
int showMenu( )
{
do
{
cout<<"================================="<<endl;
cout<<"Binary Tree Operations Menu"<<endl;
cout<<"================================="<<endl;
cout<<"1.Add a new item"<<endl;
cout<<"2.Delete an item"<<endl;
cout<<"3.Show min node"<<endl;
cout<<"4.List current height of tree"<<endl;
cout<<"5.Find a node and report its depth"<<endl;
cout<<"6.Print all nodes"<<endl;
cout<<”7. Quit”<<endl;
cout<<”Enter your section” <<endl;
cin>>selection;
} while ( (selection < 1) || (selection > 7) );
return selection;
}
Must use “binaryTree” data structure
Be sure to include comments
Use meaningful identifier names (constants where appropriate)
Do not work together; no two people should have identical work!?!?
Turn in .cpp and .h files
Explanation / Answer
Comments are included in every file.
Place all the files in the same directory. Compile using the following line in gnu c++ compiler
g++ main.cpp binaryTree.cpp
Please upvote :)
binaryTree.h
#ifndef binaryTree_H
#define binaryTree_H
#include <iostream>
using namespace std;
struct binaryTreeNode
{
int Key;
binaryTreeNode *left;
binaryTreeNode *right;
};
class binaryTree
{
public:
bool delItem(int Key);
bool addItem(int Key);
int minNodekey();
int TreeHeight();
int FindTreeNodeDepth(int Key); //returns 0 if node not found
void PrintAllNodes(); //prints the inorder traversal
binaryTree();
~binaryTree();
void freeMemory(); //deallocates all the memory allocated
private:
binaryTreeNode *root;
binaryTreeNode *newNode(int Key);
bool delNode(binaryTreeNode*& root, int Key) ;
binaryTreeNode* minNodekey(binaryTreeNode* node);
int TreeHeight(binaryTreeNode* node);
int FindTreeNodeDepth(binaryTreeNode* node, int Key);
void PrintAllNodes(binaryTreeNode *subtreeroot);
};
#endif
binaryTree.cpp
// binaryTree.cpp
#include <iostream>
#include "binaryTree.h"
bool binaryTree::addItem(int Key) {
binaryTreeNode *temp;
temp = this->root;
if(temp == NULL){
//add to the root
this->root = newNode(Key);
return this->root != NULL;
}
// Loop till temp falls out of the tree
while (temp != NULL) {
if (Key < temp->Key){
//temp should go to tree left
if(temp->left)
temp = temp->left;
else{
//the part is NULL so this is where new Node goes
temp->left = newNode(Key);
return temp->left != NULL; //if its non NULL then the process was successful
}
}
else{ //just the vice versa
if(temp->right)
temp = temp->right;
else{
temp->right = newNode(Key);
return temp->right != NULL; //if its non NULL then the process was successful
}
}
}
}
//returns the minValueNode in the subtree described through subtreeroot
binaryTreeNode* binaryTree::minNodekey(binaryTreeNode* subtreeroot) {
binaryTreeNode* itr = subtreeroot;
while (itr->left != NULL)
itr = itr->left;
return itr;
}
//returns the minValueNode in the whole tree
int binaryTree::minNodekey() {
binaryTreeNode* ret;
if(ret = minNodekey(this->root)){
return ret->Key;
}
return 0; //tree is empty
}
//root might need to change, thus it is passed as a reference
bool binaryTree::delNode(binaryTreeNode*& root, int Key) {
//subtreeroot not found
if (root == NULL) return false;
// it must lie in left subtree
if (Key < root->Key)
delNode(root->left, Key);
else if (Key > root->Key)
delNode(root->right, Key);
//this subtreeroot is to be deleted
else {
// one or no child
if (root->left == NULL) {
delete root;
root = root->right;
return true;
}
else if (root->right == NULL) {
delete root;
root = root->left;
return true;
}
// two child: Get the inorder successor (smallest // in the right subtree)
binaryTreeNode* temp = minNodekey(root->right);
root->Key = temp->Key;
// Delete the inorder successor
return delNode(root->right, temp->Key);
}
}
bool binaryTree::delItem(int Key){
return delNode(this->root, Key);
}
binaryTreeNode* binaryTree::newNode(int Key) {
try{
binaryTreeNode *ret = new binaryTreeNode;
ret->left = ret->right = NULL;
ret->Key = Key;
return ret;
}
catch(int e){
//couldnt allocate space for a new subtreeroot
return NULL;
}
}
//get the height of the subtree starting from subtreeroot
int binaryTree::TreeHeight(binaryTreeNode* subtreeroot){
if(subtreeroot == NULL) //doesnt exist
return 0;
else{
//the max height would be this subtreeroot and the max height of left and right subtree
return 1 + max(TreeHeight(subtreeroot->right), TreeHeight(subtreeroot->left));
}
}
int binaryTree::TreeHeight(){
return TreeHeight(this->root);
}
int binaryTree::FindTreeNodeDepth(int Key){
return FindTreeNodeDepth(this->root , Key);
}
int binaryTree::FindTreeNodeDepth(binaryTreeNode* subtreeroot, int Key){
if(subtreeroot == NULL) return 0; //subtreeroot not found
else if(subtreeroot->Key == Key) return 1;
else if(subtreeroot->Key > Key){
int found = FindTreeNodeDepth(subtreeroot->left, Key);
if(found) return 1 + found;
else return 0; //not found
}
else if(subtreeroot->Key < Key){
int found = FindTreeNodeDepth(subtreeroot->right, Key);
if(found) return 1 + found;
else return 0; //not found
}
}
void binaryTree::PrintAllNodes(){
if(this->root){
PrintAllNodes(this->root);
cout << endl;
}
else
cout << "Tree is empty." << endl;
}
void binaryTree::PrintAllNodes(binaryTreeNode *subtreeroot){
if(subtreeroot == NULL) return;
PrintAllNodes(subtreeroot->left);
cout << subtreeroot->Key << " ";
PrintAllNodes(subtreeroot->right);
}
binaryTree::binaryTree(){
this->root = NULL;
}
binaryTree::~binaryTree(){
//the root would get deleted and replaced by the inorder successor
//we keep doing this until root becomes null
while(this->root)
delItem(this->root->Key);
}
main.cpp
#include <iostream>
#include "binaryTree.h"
int showMenu( ) {
int selection;
do {
cout << "=================================" << endl;
cout << "Binary Tree Operations Menu" << endl;
cout << "=================================" << endl;
cout << "1.Add a new item" << endl;
cout << "2.Delete an item" << endl;
cout << "3.Show min node" << endl;
cout << "4.List current height of tree" << endl;
cout << "5.Find a node and report its depth" << endl;
cout << "6.Print all nodes" << endl;
cout << "7. Quit" << endl;
cout << "Enter your selection: " ;
cin >> selection;
} while ( (selection < 1) || (selection > 7) );
return selection;
}
int main() {
binaryTree myTree;
int sel;
do{
sel = showMenu();
if(sel == 1){
int key;
cout << "Enter the key: ";
cin >> key;
if(myTree.addItem(key))
cout << "Successfully added new node." << endl;
else
cout << "Memory allocation failure." << endl;
}
else if(sel == 2){
int key;
cout << "Enter the key: ";
cin >> key;
if(myTree.delItem(key))
cout << "Successfully deleted the node." << endl;
else
cout << "Node not found." << endl;
}
else if(sel == 3){
int key;
if(key = myTree.minNodekey())
cout << "Min node key : " << key << endl;
else
cout << "Tree is empty" << endl;
}
else if(sel == 4){
cout << "Tree Height : " << myTree.TreeHeight() << endl;
}
else if(sel == 5){
int key, depth;
cout << "Enter the key: ";
cin >> key;
if(depth = myTree.FindTreeNodeDepth(key))
cout << "Found at depth : " << depth << endl;
else
cout << "Node not found." << endl;
}
else if(sel == 6){
myTree.PrintAllNodes();
}
}while(sel != 7);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.