Question

In: Computer Science

C++ problem - Implement and add the advanced functionalities to the ADT of the BST made...

C++ problem - Implement and add the advanced functionalities to the ADT of the BST made with the fundamental functionalities:

Visit - Description: It will display each of the data stored in the BST depending on the input parameter:Preorder
Inorder
Bidder
Level by level

Input - An integer (1-4)
Exit - Nothing
Precondition - A valid BST
Postcondition - Nothing

Height - Description:Will return the height of the BST
Entry - Nothing
Output - An integer with which to indicate the height of the BST
Precondition - A valid BST
Postcondition - Nothing

Ancestors - Description: It will display the ancestors of a data

Entry - The data of which you want to know the ancestors
Exit - Nothing
Precondition - A valid BST
Postcondition - Nothing

whatlevelamI - Description: It will return an integer that indicates the level in which a data is located, or -1 in case it is not in the BST

Input - A piece of information to find your height
Output - Integer indicating the level of the data in the BST, or -1 if it is not found
Precondition - A valid BST
Postcondition - Nothing

This is the declaration of the MyBST class that must be used

#ifndef MYBST_H

#define MYBST_H

struct MyNodeBST{

int data;

MyNodeBST *left,

*right;

MyNodeBST(int data){

this->data=data;

this->left=this->right=nullptr;

}

};

class MyBST{

private:

int size;

MyNodeBST* root;

bool search(int data,MyNodeBST* current);

void preorder(MyNodeBST* current);

void inorder(MyNodeBST* current);

void postorder(MyNodeBST* current);

public:

MyBST();

int length();

bool isEmpty();

bool search(int data);

bool insert(int data);

bool remove(int data);

void preorder();

void inorder();

void postorder();

void level();

void visit(int type);

int height();

void ancestors(int data);

int whatLevelAmI(int data);

};

#endif

Solutions

Expert Solution

```
 * C++ Program To Implement BST
```
```
 */
```
```
# include <iostream>
```
```
# include <cstdlib>
```
```
using namespace std;
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left;
```
```
    struct node *right;
```
```
}*root;
```
```
 
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class BST
```
```
{
```
```
    public:
```

        void find(int, node **, node **);

```
        void insert(node *, node *);
```
```
        void del(int);
```
```
        void case_a(node *,node *);
```
```
        void case_b(node *,node *);
```
```
        void case_c(node *,node *);
```
```
        void preorder(node *);
```
```
        void inorder(node *);
```
```
        void postorder(node *);
```
```
        void display(node *, int);
```
```
        BST()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    int choice, num;
```
```
    BST bst;
```
```
    node *temp;
```
```
    while (1)
```
```
    {
```

        cout<<"-----------------"<<endl;

        cout<<"Operations on BST"<<endl;

        cout<<"-----------------"<<endl;

        cout<<"1.Insert 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 choice : ";
```
```
        cin>>choice;
```
```
        switch(choice)
```
```
        {
```
```
        case 1:
```
```
            temp = new node;
```

            cout<<"Enter the number to be inserted : ";

```
            cin>>temp->info;
```
```
            bst.insert(root, temp);
```
```
        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 choice"<<endl;
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Find Element in the Tree
```
```
 */
```

void BST::find(int item, node **par, node **loc)

```
{
```
```
    node *ptr, *ptrsave;
```
```
    if (root == NULL)
```
```
    {
```
```
        *loc = NULL;
```
```
        *par = NULL;
```
```
        return;
```
```
    }
```
```
    if (item == root->info)
```
```
    {
```
```
        *loc = root;
```
```
        *par = NULL;
```
```
        return;
```
```
    }
```
```
    if (item < root->info)
```
```
        ptr = root->left;
```
```
    else
```
```
        ptr = root->right;
```
```
    ptrsave = root;
```
```
    while (ptr != NULL)
```
```
    {
```
```
        if (item == ptr->info)
```
```
        {
```
```
            *loc = ptr;
```
```
            *par = ptrsave;
```
```
            return;
```
```
        }
```
```
        ptrsave = ptr;
```
```
        if (item < ptr->info)
```
```
            ptr = ptr->left;
```
```
        else
```
```
            ptr = ptr->right;
```
```
    }
```
```
    *loc = NULL;
```
```
    *par = ptrsave;
```
```
}
```
```
 
```
```
/*
```
```
 * Inserting Element into the Tree
```
```
 */
```

void BST::insert(node *tree, node *newnode)

```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        root = new node;
```
```
        root->info = newnode->info;
```
```
        root->left = NULL;
```
```
        root->right = NULL;
```

        cout<<"Root Node is Added"<<endl;

```
        return;
```
```
    }
```
```
    if (tree->info == newnode->info)
```
```
    {
```

        cout<<"Element already in the tree"<<endl;

```
        return;
```
```
    }
```
```
    if (tree->info > newnode->info)
```
```
    {
```
```
        if (tree->left != NULL)
```
```
        {
```

            insert(tree->left, newnode);

```
        }
```
```
        else
```
```
        {
```
```
            tree->left = newnode;
```
```
            (tree->left)->left = NULL;
```
```
            (tree->left)->right = NULL;
```

            cout<<"Node Added To Left"<<endl;

```
            return;
```
```
        }
```
```
    }
```
```
    else
```
```
    {
```
```
        if (tree->right != NULL)
```
```
        {
```

            insert(tree->right, newnode);

```
        }
```
```
        else
```
```
        {
```
```
            tree->right = newnode;
```
```
            (tree->right)->left = NULL;
```

            (tree->right)->right = NULL;

            cout<<"Node Added To Right"<<endl;

```
            return;
```
```
        }       
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Delete Element from the tree
```
```
 */
```
```
void BST::del(int item)
```
```
{
```
```
    node *parent, *location;
```
```
    if (root == NULL)
```
```
    {
```
```
        cout<<"Tree empty"<<endl;
```
```
        return;
```
```
    }
```
```
    find(item, &parent, &location);
```
```
    if (location == NULL)
```
```
    {
```

        cout<<"Item not present in tree"<<endl;

```
        return;
```
```
    }
```

    if (location->left == NULL && location->right == NULL)

```
        case_a(parent, location);
```

    if (location->left != NULL && location->right == NULL)

```
        case_b(parent, location);
```

    if (location->left == NULL && location->right != NULL)

```
        case_b(parent, location);
```

    if (location->left != NULL && location->right != NULL)

```
        case_c(parent, location);
```
```
    free(location);
```
```
}
```
```
 
```
```
/*
```
```
 * Case A
```
```
 */
```
```
void BST::case_a(node *par, node *loc )
```
```
{
```
```
    if (par == NULL)
```
```
    {
```
```
        root = NULL;
```
```
    }
```
```
    else
```
```
    {
```
```
        if (loc == par->left)
```
```
            par->left = NULL;
```
```
        else
```
```
            par->right = NULL;
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Case B
```
```
 */
```
```
void BST::case_b(node *par, node *loc)
```
```
{
```
```
    node *child;
```
```
    if (loc->left != NULL)
```
```
        child = loc->left;
```
```
    else
```
```
        child = loc->right;
```
```
    if (par == NULL)
```
```
    {
```
```
        root = child;
```
```
    }
```
```
    else
```
```
    {
```
```
        if (loc == par->left)
```
```
            par->left = child;
```
```
        else
```
```
            par->right = child;
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Case C
```
```
 */
```
```
void BST::case_c(node *par, node *loc)
```
```
{
```
```
    node *ptr, *ptrsave, *suc, *parsuc;
```
```
    ptrsave = loc;
```
```
    ptr = loc->right;
```
```
    while (ptr->left != NULL)
```
```
    {
```
```
        ptrsave = ptr;
```
```
        ptr = ptr->left;
```
```
    }
```
```
    suc = ptr;
```
```
    parsuc = ptrsave;
```

    if (suc->left == NULL && suc->right == NULL)

```
        case_a(parsuc, suc);
```
```
    else
```
```
        case_b(parsuc, suc);
```
```
    if (par == NULL)
```
```
    {
```
```
        root = suc;
```
```
    }
```
```
    else
```
```
    {
```
```
        if (loc == par->left)
```
```
            par->left = suc;
```
```
        else
```
```
            par->right = suc;
```
```
    }
```
```
    suc->left = loc->left;
```
```
    suc->right = loc->right;
```
```
}
```
```
 
```
```
/*
```
```
 * Pre Order Traversal
```
```
 */
```
```
void BST::preorder(node *ptr)
```
```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        cout<<"Tree is empty"<<endl;
```
```
        return;
```
```
    }
```
```
    if (ptr != NULL)
```
```
    {
```
```
        cout<<ptr->info<<"  ";
```
```
        preorder(ptr->left);
```
```
        preorder(ptr->right);
```
```
    }
```
```
}
```
```
/*
```
```
 * In Order Traversal
```
```
 */
```
```
void BST::inorder(node *ptr)
```
```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        cout<<"Tree is empty"<<endl;
```
```
        return;
```
```
    }
```
```
    if (ptr != NULL)
```
```
    {
```
```
        inorder(ptr->left);
```
```
        cout<<ptr->info<<"  ";
```
```
        inorder(ptr->right);
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Postorder Traversal
```
```
 */
```
```
void BST::postorder(node *ptr)
```
```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        cout<<"Tree is empty"<<endl;
```
```
        return;
```
```
    }
```
```
    if (ptr != NULL)
```
```
    {
```
```
        postorder(ptr->left);
```
```
        postorder(ptr->right);
```
```
        cout<<ptr->info<<"  ";
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Display Tree Structure
```
```
 */
```
```
void BST::display(node *ptr, int level)
```
```
{
```
```
    int i;
```
```
    if (ptr != NULL)
```
```
    {
```
```
        display(ptr->right, level+1);
```
```
        cout<<endl;
```
```
        if (ptr == root)
```
```
            cout<<"Root->:  ";
```
```
        else
```
```
        {
```
```
            for (i = 0;i < level;i++)
```
```
                cout<<"       ";
```
```
        }
```
```
        cout<<ptr->info;
```
```
        display(ptr->left, level+1);
```
```
    }
```
```
}
```

Output:-

venereology answered 1 year ago

Next > < Previous

Related Solutions

In C++, Design and implement an ADT that represents a triangle. The data for the ADT...

In C++, Design and implement an ADT that represents a triangle. The data for the ADT should include the three sides of the triangle but could also include the triangle’s three angles. This data should be in the private section of the class that implements the ADT. Include at least two initialization operations: one that provides default values for the ADT’s data, and another that sets this data to client-supplied values. These operations are the class’s constructors. The ADT also...

In C++, Implement the queue ADT with a singly linked list

The question is about C++ The main should test all functionalities of the playlist implement a...

The question is about C++ The main should test all functionalities of the playlist implement a linked list to store songs of a playlist. A song (which is your node) is going to include the following data: - int Song ID - string Song Title - string Author Title - double Length Don't forget to include the next pointer that will lead to the next song. Your playlist (which is your linkedlist) is going to include the following functionalities: -...

1. Implement the graph ADT using the adjacency list structure. 2. Implement the graph ADT using...

1. Implement the graph ADT using the adjacency list structure. 2. Implement the graph ADT using the adjacency matrix structure. LANGUAGE IS IN JAVA Comment for any questions Data structures and algorithms

This is C++ programming. Use separate compilation to implement a polynomial ADT that manipulates polynomials in...

This is C++ programming. Use separate compilation to implement a polynomial ADT that manipulates polynomials in a single variable x (e.g., p = 4 x^5 + 7 x^3 – x^2 + 9 ). For this problem, consider only polynomials whose exponents are non-negative integers. You are required to identify a proper data representation schema to store such polynomials and hide such data from external users of this ADT. Additionally, your ADT will at least include the following member functions: One...

C++ PROGRAMMING In the linked-list based bag implementation, we demonstrated the functionalities, such as, add, remove,...

C++ PROGRAMMING In the linked-list based bag implementation, we demonstrated the functionalities, such as, add, remove, and list. This assignment is to extend the functionalities of the bag with other operations average, min, and max, You need to extend the Bag class (under Wk 2, BagLinked_List.cpp) with the following methods: -int Bag::min( ), is to find minimum of items of the bag. -int Bag::max( ), is to find maximum of items of the bag -float Bag::ave( ), is to find...

Overview: implement the ADT List in Java. This program is meant to the ADT List from...

Overview: implement the ADT List in Java. This program is meant to the ADT List from the ground up In the lecture, we learned how to implement an ADT like the ArrayList you have used in Project 1. With this project, you have the chance to implement an ADT called MyList, which is a simplified replacement for the full-blown ArrayList. Requirements You will implement the MyList ADT according to the following: 1. MyList must implement the List interface. It will...

Implement a function named printRange that, given the pointer to the root of a BST, a...

Implement a function named printRange that, given the pointer to the root of a BST, a low key value, and a high key value, prints in sorted order all records whose key values fall between the two given keys (inclusive). Function printRange should visit as few nodes in the BST as possible. Here is the start code (in Java 8) for this problem. Input Format Three lines. The first line includes the number of keys to be put in the...

Implement a Bag ADT using Dynamic Array structure as underlying data storage for Bag ADT. RESTRICTIONS:...

Implement a Bag ADT using Dynamic Array structure as underlying data storage for Bag ADT. RESTRICTIONS: Not allowed to use ANY built-in Python data structures and their methods. You must solve by importing the DynamicArray class and using class methods to write solution. Also not allowed to directly access any variables of the DynamicArray class (like self.size, self.capacity and self.data in part 1). All work must be done by only using class methods. Below is the Bag ADT starter code...

Add a clone method to the BST program. This method returns a deep copy of a...

Add a clone method to the BST program. This method returns a deep copy of a tree. Coding Language C++ Use this main method to test your code: int main() { Tree T; T.insert(50); T.insert(20); T.insert(80); T.insert(60); T.insert(90); T.display(); Tree T1 = T; Tree T2 = T.clone(); cout << "\n\nT1 and T2 before insert(999)\n=====================\n\n"; T1.inOrder(); T2.inOrder(); T.insert(999); cout << "\n\nT1 and T2 after insert(999)\n=====================\n\n"; T1.inOrder(); T2.inOrder(); system("pause"); // may need to remove this on some systems return 0; } #include...

Subjects