Question

The main goal is to implement two recursive methods, each is built to manipulate linked data...

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.

Homework Answers

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
C++ Goals  Build single linked lists using pointers  Learn how to manipulate linked lists...
C++ Goals  Build single linked lists using pointers  Learn how to manipulate linked lists In this lab, you will create simple single linked structures consisting of Node objects. Each node will have a pointer to the next node. You will use a head pointer to keep track of the first node in the linked list, and a tail pointer to keep track of the last node in the linked list. Set both head and tail to NULL when...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
Given this definition of a generic Linked List node: public class LLNode {     private T...
Given this definition of a generic Linked List node: public class LLNode {     private T data;     private LLNode next;     public LLNode(T data, LLNode next) {           this.data = data;           this.next = next;     }     public void setNext(LLNode newNext){ next = newNext; }     public LLNode getNext(){ return next; }     public T getData() {return data;} } Write the findMinimumNode method body. This method returns the linked list node that contains the minimum value in the...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
In this code, I build a single-linked list using a node class that has been created....
In this code, I build a single-linked list using a node class that has been created. How could I change this code to take data of type T, rather than int. (PS: ignore the fact that IOHelper.getInt won't work for the type T... ie second half of main). Here's my code right now: public class SLList { public SLNode head = null; public SLNode tail = null; public void add(int a) {// add() method present for testing purposes SLNode newNode...
It is about C++linked list code. my assignment is making 1 function, in below circumstance,(some functions...
It is about C++linked list code. my assignment is making 1 function, in below circumstance,(some functions are suggested for easier procedure of making function.) void search_node(struct linked_list* list, int find_node_ value) (The function to make) This function finds the node from the list that value is same with find_node_value and count the order of the node. This function should print message “The order of (node_value) is (order).” and error message “Function search_node : There is no such node to search.”....
Data Structure in C++ I keep getting the same warning, and I cant seem to fix...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix it.. Can you explain to me what I am doing wrong? Warning: dlist.cc: In function 'std::ostream& operator<<(std::ostream&, dlist&)': dlist.cc:66:10: error: invalid initialization of reference of type 'std::ostream& {aka std::basic_ostream&}' from expression of type 'dlist::node*' dlist.cc: In function 'dlist operator+(dlist&, dlist&)': dlist.cc:93:8: error: invalid operands of types 'dlist::node*' and 'dlist::node*' to binary 'operator+' dlist.cc:97:8: error: could not convert 'result' from 'int' to 'dlist' My code:...
1- Use inheritance to implement the following classes: A: A Car that is a Vehicle and...
1- Use inheritance to implement the following classes: A: A Car that is a Vehicle and has a name, a max_speed value and an instance variable called the number_of_cylinders in its engine. Add public methods to set and get the values of these variables. When a car is printed (using the toString method), its name, max_speed and number_of_cylinders are shown. B: An Airplane that is also a vehicle and has a name, a max_speed value and an instance variable called...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None: """This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree.""" Example #1: tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) Output: TREE in order { } TREE in order { 5, 10, 15 } TREE in order { 5, 10, 15, 15, 15 } TREE in order {...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT