Modify your C++ BST class and add the following functionality - Remove - Tree He
ID: 3863710 • Letter: M
Question
Modify your C++ BST class and add the following functionality
- Remove
- Tree Height
- FindMin
- FindMax
Your program will take in a command file called “cmd.txt” which will instruct your program on what operations to run
File Format
<command> <0 or 1 arguments>
Commands
- 1 insert
- 2 in order
- 3 post order
- 4 pre order
- 5 search
- 6 delete
- 7 findHeight
- 8 findMin
- 9 findMax
Example File
1 20
7
1 30
7
1 10
7
1 25
7
1 29
7
1 23
7
1 56
7
1 89
7
1 4
7
1 33
7
2
3
4
6 20
2
3
4
6 89
2
3
4
8
9
Expectations
You should not use any already implemented code such as a library for your linked list
Your code should be well formatted with proper spacing and proper naming
Your code should have well named variables. No a’s b’s or c’s as names unless it is for something like a loop counter
Your code must have the same output formatting you see below
#include<iostream>
using namespace std;
struct BSTNode
{
int data;
BSTNode *left;
BSTNode *right;
};
BSTNode* getnewnode(int data)
{
BSTNode* temp=new BSTNode();
temp->data=data;
temp->left=temp->right=NULL;
return temp;
}
BSTNode* insertnode(struct BSTNode *root,int data)
{
if(root==NULL)
{
root=getnewnode(data);
}
else if(data<=root->data)
{
root->left=insertnode(root->left,data);
}
else
{
root->right=insertnode(root->right,data);
}
return root;
}
bool search(BSTNode *root,int data)
{
if(root==NULL) return false;
else if(root->data==data) return true;
else if(data<root->data)
return search(root->left,data);
else
return search(root->right,data);
}
void preorder(BSTNode* root)
{
if(root==NULL)
return ;
else
{
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
void inorder(BSTNode* root)
{
if(root==NULL)
return ;
else
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
void postorder(BSTNode* root)
{
if(root==NULL)
return ;
else
{
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
int findmin(BSTNode* root) //itterative method
{
if(root==NULL)
{
cout<<" error: tree is empty ";
return -1;
}
BSTNode* current=root;
while(current->left)
current=current->left;
return current->data;
}
int findmax(BSTNode* root) //itterative method find the maximum element
{
if(root==NULL)
{
cout<<" error: tree is empty ";
return -1;
}
BSTNode* current=root;
while(current->right)
current=current->right;
return current->data;
}
int recursive_findMin(BSTNode* root)
{
if(root==NULL)
{
cout<<" error: tree is empty ";
return -1;
}
else if(root->left==NULL)
return root->data;
return recursive_findMin(root->left);
}
int recursive_findMax(BSTNode *root)
{
if(root==NULL)
{
cout<<" error: tree is empty ";
return -1;
}
else if(root->right==NULL)
return root->data;
return recursive_findMax(root->right);
}
int findHeight(BSTNode* root)
{
if(root==NULL)
return -1;
return max(findHeight(root->left),findHeight(root->right))+1;
}
int main()
{
int x;
struct BSTNode* root=NULL;
root=insertnode(root,10);
root=insertnode(root,15);
root=insertnode(root,9);
root=insertnode(root,8);
root=insertnode(root,7);
root=insertnode(root,6);
cout<<"enter the data to search ";
cin>>x;
if(search(root,x)==true)
cout<<" data is found ";
else
cout<<" data is not found";
cout<<" preorder traversal ";
preorder(root);
cout<<" inorder traversal ";
inorder(root);
cout<<" postorder traversal ";
postorder(root);
cout<<" height of tree= "<<findHeight(root);
cout<<" minimum element by itterative method: "<<findmin(root);
cout<<" maximum element by itterative method: "<<findmax(root);
cout<<" minimum element by recursive method : "<< recursive_findMin(root);
cout<<" maximum element by recursive method : "<< recursive_findMax(root);
return 0;
}
Explanation / Answer
Answer
Went through the provided code and found all the required function has been implemented except delete function.
For delete function, there are three cases:
case 1: when the node to be deleted is a leaf node
In such cases, simply delete the node and free the memory space
case 2: the node which you want to delete has only one child
In such cases, copy the chile to the node which you want to delete and then delete the node in which the child was previously in.
case 3: when the node that needs to be deleted has two children
In such cases, find the inorder successor of the node. Copy the content of the inorder successor to the node which needs to be deleted and delete the node in which the successor was previously in.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.