Write the following functions and add them to the genBST.h file supplied in the
ID: 3842183 • Letter: W
Question
Write the following functions and add them to the genBST.h file supplied in the download link below. GenBST.h file is in the link http://s000.tinyupload.com/index.php?file_id=86544375185714297666. a) We need a function to count the number of nodes in a binary tree. b) A function to count the number of leaves. Create a program that uses this class as follows (The tree is used store strings – names). 1) The program should present the user with a menu as follows: 1. Add a new name 2. Delete a name 3. List the contents in ascending order 4. Display the number of nodes in the tree 5. Display the number of leafs 6. Exit the system Please enter your choice: 2. Create a function for each option on the menu to handle the request. 3. For choice # 1 (Add a new value), the function should prompt the user to enter a value (a string). If the value is already stored in the tree, you should display a message that indicates that. 4. For choice # 2 (Delete a value), the function should prompt the user to enter a value (a string). Display a message to indicate if the value is found and deleted or if it is not found. 5. Main() should call a function called menu() to display the menu and return user’s input. Main() should not handle any input or output other than reading and validating user’s input. 6. You need to submit the class files, main(), and the executable file. Note: The file downloaded from the publisher’s website contains a syntax error in deleteByCopying where a left “)” is missing in "if (node->left== 0). Also, make sure to include “using namespace std;” and “#include”. Otherwise, the code does not compile.
Explanation / Answer
Answer:
#include<iostream>
using namespace std;
struct treeNode
{
int info;
treeNode *before;
treeNode *previous;
};
treeNode* LocateMinimum(treeNode *node)
{
if(node==NULL)
{
return NULL;
}
if(node->before)
return LocateMinimum(node->before);
else
return node;
}
treeNode* LocateMaximum(treeNode *node)
{
if(node==NULL)
{
return NULL;
}
if(node->previous)
return(LocateMaximum(node->previous));
else
return node;
}
treeNode *Push(treeNode *node,int info)
{
if(node==NULL)
{
treeNode *support;
support=new treeNode;
support -> info = info;
support -> before = support -> previous = NULL;
return support;
}
if(info >(node->info))
{
node->previous = Push(node->previous,info);
}
else if(info < (node->info))
{
node->before = Push(node->before,info);
}
return node;
}
treeNode * Delete(treeNode *node, int info)
{
treeNode *support;
if(node==NULL)
{
cout<<"Element Not Found";
}
else if(info < node->info)
{
node->before = Delete(node->before, info);
}
else if(info > node->info)
{
node->previous = Delete(node->previous, info);
}
else
{
if(node->previous && node->before)
{
support = LocateMinimum(node->previous);
node -> info = support->info;
node -> previous = Delete(node->previous,support->info);
}
else
{
support = node;
if(node->before == NULL)
node = node->previous;
else if(node->previous == NULL)
node = node->before;
free(support);
}
}
return node;
}
treeNode * Search(treeNode *node, int info)
{
if(node==NULL)
{
return NULL;
}
if(info > node->info)
{
return Search(node->previous,info);
}
else if(info < node->info)
{
return Search(node->before,info);
}
else
{
return node;
}
}
void Inorder(treeNode *node)
{
if(node==NULL)
{
return;
}
Inorder(node->before);
cout<<node->info<<" ";
Inorder(node->previous);
}
void Preorder(treeNode *node)
{
if(node==NULL)
{
return;
}
cout<<node->info<<" ";
Preorder(node->before);
Preorder(node->previous);
}
void Postorder(treeNode *node)
{
if(node==NULL)
{
return;
}
Postorder(node->before);
Postorder(node->previous);
cout<<node->info<<" ";
}
int main()
{
treeNode *head = NULL,*support;
int ch;
while(1)
{
cout<<" 1.Push 2.Delete 3.Inorder 4.Preorder 5.Postorder 6.LocateMinimum 7.LocateMaximum 8.Search 9.Exit ";
cout<<"Enter ur choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<" Enter element to be Push:";
cin>>ch;
head = Push(head, ch);
cout<<" Elements in BST are:";
Inorder(head);
break;
case 2:
cout<<" Enter element to be Deleteed:";
cin>>ch;
head = Delete(head,ch);
cout<<" After Deleteion elements in BST are:";
Inorder(head);
break;
case 3:
cout<<" Inorder Travesals is:";
Inorder(head);
break;
case 4:
cout<<" Preorder Traversals is:";
Preorder(head);
break;
case 5:
cout<<" Postorder Traversals is:";
Postorder(head);
break;
case 6:
support = LocateMinimum(head);
cout<<" Minimum element is :"<<support->info;
break;
case 7:
support = LocateMaximum(head);
cout<<" Maximum element is :"<<support->info;
break;
case 8:
cout<<" Enter element to be searched:";
cin>>ch;
support = Search(head,ch);
if(support==NULL)
{
cout<<"Element is not foundn";
}
else
{
cout<<"Element "<<support->info<<" is Found ";
}
break;
case 9:
exit(0);
break;
default:
cout<<" Enter correct choice:";
break;
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.