The main goal is to implement two recursive methods, each is built to manipulate
ID: 3802243 • Letter: T
Question
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes.
1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class
Generic implementation not needed, the nodes will store integer values
The standard methods will not be needed in this exercise except the constructor
2.) Add a toString( ) method to the BinaryNode class. The method creates a String description of the tree.
3.) Add a method named BSTFactory () to the class. This method is static returns, for any given N, the root reference of a full binary search tree of depth N such that the nodes store the integers 1, 2, 3, …, 2 N+1 – 1
must be recursive. More precisely double recursive, the method calls itself with decreased depth with respect to the left link and right link of the caller node
takes parameter(s), depth is naturally the control parameter, and it may be helpful to add another parameter, the “top” number stored in the root of the current sub-tree
may also benefit of a private helper method which computes the power of 2 of a given exponent
Hints:
Construct and draw the BST solutions on a piece of paper for depth values
N = 0, 1, 2, 3.
Note that the solution is always unique, there is only one way to fill in the numbers
Observe the values in the root nodes, deduct and verify a rule for the root values
Observe the values in the children of the root, deduct and verify a rule how to express the children values in terms of the root value.
The rules you found will help to parametrize correct the BSTFactory( ) method in the recursive algorithm
4.) Add another class SimpleNode to you project (this class is independent of the previous BinaryNode class). SimpleNode is a (non-generic) representative of any Node class . As in the above case, none of the standard methods but the constructor will be used in this demonstration. You will need however the toString( ) method and the getTail( ) method from your previous assignments. The type of the data stored in the nodes has no relevance to this application, choose String values at will
5.) Add a method named reverse () to the class. This method is static
takes the head of the original list for parameter
given the head reference of a linked list, returns the head reference of the linked list in reversed order; that is the method has to reverse all the links of the original list, the original tail will be the head and the original head will be the new tail. Note that the nodes are not cloned and the data stored in the nodes are not moved or changed
must be recursive, applied on shorter and shorter lists
Choose carefully the base case(s)
6.) Add an Application class to the project to test and demonstrate the work of the methods. Print all output to the console
7.) Test BSTFactory for all values N = 0, 1, 2, 3, 4, 5
8.) Test reverse( ) for lists of length 0, 1, 5 and 10
9.) Use the toString() method of your classes to create output messages. Design your display such that it gives clear explanation about the output data.
Explanation / Answer
Answer:
# include <iostream>
# include <cstdlib>
using namespace std;
struct node
{
int value;
struct node *first;
struct node *second;
}*root;
class BST
{
public:
void search(int, node **, node **);
void push(int);
void del(int);
void function_one(node *,node *);
void function_two(node *,node *);
void function_three(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
int main()
{
int option, num;
BST bst;
node *value;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.push Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your option : ";
cin>>option;
switch(option)
{
case 1:
value = new node;
cout<<"Enter the number to be pushed : ";
cin>>value->value;
bst.push(root, value);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong option"<<endl;
}
}
}
void BST::search(int input, node **pointer, node **places)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*places = NULL;
*pointer = NULL;
return;
}
if (input == root->value)
{
*places = root;
*pointer = NULL;
return;
}
if (input < root->value)
ptr = root->first;
else
ptr = root->second;
ptrsave = root;
while (ptr != NULL)
{
if (input == ptr->value)
{
*places = ptr;
*pointer = ptrsave;
return;
}
ptrsave = ptr;
if (input < ptr->value)
ptr = ptr->first;
else
ptr = ptr->second;
}
*places = NULL;
*pointer = ptrsave;
}
void BST::push(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->value = newnode->value;
root->first = NULL;
root->second = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->value == newnode->value)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->value > newnode->value)
{
if (tree->first != NULL)
{
push(tree->first, newnode);
}
else
{
tree->first = newnode;
(tree->first)->first = NULL;
(tree->first)->second = NULL;
cout<<"Node Added To first"<<endl;
return;
}
}
else
{
if (tree->second != NULL)
{
push(tree->second, newnode);
}
else
{
tree->second = newnode;
(tree->second)->first = NULL;
(tree->second)->second = NULL;
cout<<"Node Added To second"<<endl;
return;
}
}
}
void BST::del(int input)
{
node *pointerent, *place;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
search(input, &pointerent, &place);
if (place == NULL)
{
cout<<"input not present in tree"<<endl;
return;
}
if (place->first == NULL && place->second == NULL)
function_one(pointerent, place);
if (place->first != NULL && place->second == NULL)
function_two(pointerent, place);
if (place->first == NULL && place->second != NULL)
function_two(pointerent, place);
if (place->first != NULL && place->second != NULL)
function_three(pointerent, place);
free(place);
}
void BST::function_one(node *pointer, node *places )
{
if (pointer == NULL)
{
root = NULL;
}
else
{
if (places == pointer->first)
pointer->first = NULL;
else
pointer->second = NULL;
}
}
void BST::function_two(node *pointer, node *places)
{
node *child;
if (places->first != NULL)
child = places->first;
else
child = places->second;
if (pointer == NULL)
{
root = child;
}
else
{
if (places == pointer->first)
pointer->first = child;
else
pointer->second = child;
}
}
void BST::function_three(node *pointer, node *places)
{
node *ptr, *ptrsave, *suc, *pointersuc;
ptrsave = places;
ptr = places->second;
while (ptr->first != NULL)
{
ptrsave = ptr;
ptr = ptr->first;
}
suc = ptr;
pointersuc = ptrsave;
if (suc->first == NULL && suc->second == NULL)
function_one(pointersuc, suc);
else
function_two(pointersuc, suc);
if (pointer == NULL)
{
root = suc;
}
else
{
if (places == pointer->first)
pointer->first = suc;
else
pointer->second = suc;
}
suc->first = places->first;
suc->second = places->second;
}
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->value<<" ";
preorder(ptr->first);
preorder(ptr->second);
}
}
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->first);
cout<<ptr->value<<" ";
inorder(ptr->second);
}
}
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->first);
postorder(ptr->second);
cout<<ptr->value<<" ";
}
}
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->second, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->value;
display(ptr->first, level+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.