For this computer assignment, implement a derived class to represent a binary se

Question

For this computer assignment, implement a derived class to represent a binary search tree. Since a binary search tree is also a binary tree, implement your binary search tree class from the base class of binary trees.

The above public functions simply call their private versions. The private versions of insert (), remove (), search() and sumOfRange () functions can be implemented as recursive functions. You can assume there are no identical numbers to be inserted into the tree.

When you implement the remove() function, consider three possible cases: the node to be removed(1) is a leaf; (2) has only one child; and (3) has two children. In the first case, simply delete the node. In the second case, bypass the node making a new link from its parent to its child, and delete the node. In the third case, find the immediate predecessor of the node – first move to the left child of the node, and then move to rightmost node in the sub-tree, replace the value of the node with its immediate predecessor, and delete the predecessor. The pseudo-code is shown below

#include <iostream>

#include <algorithm>

#include <vector>

#include <iomanip>

using namespace std;

static const int SEARCH_LOW = 20;

static const int SEARCH_HIGH = 30;

static const int MAX_COUNT = 20;

static int mcount = 0;

class BST : public binTree {

public:

       BST() : binTree() {} // constructor

       void insert(int); // insert an item in the tree

       bool search(int); // search an item in the tree

       bool remove(int); // remove an item in the tree

                                  // returns true when successful

       int sumOfRange(

              const int lower, const

              int upper);

       // the sum of

       values

              // between the range [lower, upper].

private:

       void insert(Node*&, int); // private version of insert(int)

       bool search(Node*&, int); // private version of search(int)

       bool remove(Node*&, int); // private version of remove(int)

       int sumOfRange(

              Node*& n, int lower, const int upper); // private version

                                                                             // of sumt Of Range

};

void display2(int d) {

    if ( mcount < MAX_COUNT ) {

        cout << setw(4) << d;

        mcount++;

    }

}

// produce a random number within range [1 1000]

int rand_1000() {

    return rand() % 1000 + 1;

}

void show_tree_information( BST& bst ) {

    cout << "Size of the tree: " << bst.size() << endl;

    cout << "Height of the tree: " << bst.height() << endl;

    cout << "In order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;

    mcount = 0;

    bst.inorder( display2 );

    cout << " Pre order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;

    mcount = 0;

    bst.preorder( display2 );

    cout << " Post order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;

    mcount = 0;

   bst.postorder( display2 );

}

// For each value in searchVec, search it in the binary search tree

// and report the number of successful searches

void run_search( BST& bst, vector<int>& searchVec ) {

    int success = 0;

    vector<int>::iterator it;

    for ( it = searchVec.begin(); it != searchVec.end(); it++ )

        if ( bst.search( *it ) )

            success++;

    cout << endl << endl << "Out of " << searchVec.size() << " searches, " << success << " are successful." << endl << endl;

}

int main() {

    //-------------- Create a B.S.T. using unique random numbers -----------

    vector<int> inputVec(1000);

    srand(7);

    generate(inputVec.begin(), inputVec.end(), rand_1000);

    sort(inputVec.begin(), inputVec.end());

    vector<int>::iterator it = unique(inputVec.begin(), inputVec.end());

    inputVec.resize( it - inputVec.begin() );

    random_shuffle( inputVec.begin(), inputVec.end() );

    BST bst;

    for (it=inputVec.begin(); it!=inputVec.end(); it++)

        bst.insert( *it );

    cout << "A binary search tree is generated with random numbers: " << endl;

    show_tree_information( bst );

    //-------------- Create a vector of random integers to be searched ------

    vector<int> searchVec(500);

    srand(11);

    generate( searchVec.begin(), searchVec.end(), rand_1000 );

    //cout << endl << endl << "Sum of range: " << bst.sumOfRange(SEARCH_LOW, SEARCH_HIGH) << endl;

    //------------ test search operations ----------------

    run_search( bst, searchVec );

    //------------ remove half of nodes from the tree ---------

    int counter = 0;

    random_shuffle( inputVec.begin(), inputVec.end() );

    for ( it = inputVec.begin(); it < inputVec.end(); it += 2 ) {

        if ( bst.remove( *it ) )

            counter++;

    }

    cout << endl << counter << " nodes are removed." << endl << endl;

    show_tree_information( bst );

    cout << endl << endl << "Sum of range between " << SEARCH_LOW << " and "

         << SEARCH_HIGH << " : " << bst.sumOfRange(SEARCH_LOW, SEARCH_HIGH) << endl;

    //-------------- test search operations again ---------------

    run_search( bst, searchVec );

    return 0;

}

Explanation / Answer

Here is the solution for above scenario:

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.