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.

Answer 1

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);
    }
}