C++

For this computer assignment, implement a derived class (as a template) to represent a binary search tree. Since a binary search tree is a binary tree, implement your binary search tree class from the base class of the binary tree as you implemented in your previous assignment.

The definition of the derived class of a binary search tree (as a template) is given as follows:

template < class T >

class binSTree : public binTree < T > {

public:

void insert ( const T& x ); // inserts node with value x

bool search ( const T& x ) const; // searches leaf with value x

bool remove ( const T& x ); // removes leaf with value x

private:

void insert ( Node < T >*&, const T& ); // private version of insert

bool search ( Node < T >*, const T& ) const;// private version of search

void remove ( Node < T >*&, const T& ); // private version of remove

bool leaf ( Node < T >* node ) const; // checks if node is leaf

};

The insert ( ) function inserts a node with the data value x in the tree. For the search ( ) function, x is the data value of a leaf to be searched for. If the search is successful, the search ( ) function returns true; otherwise, it returns false. The remove ( ) function first calls the search ( ) function to determine the result of the search for a leaf with the data value x, and if the search is successful, then it calls the private version of the remove ( ) function to remove the corresponding leaf from the tree and returns true; otherwise, it returns false. The leaf ( ) function simply checks if a node is a leaf.

The private versions of the member functions insert ( ), remove ( ) and search ( ) can be implemented as recursive functions, but these functions have an additional argument, which is the root of the tree. The private version of the remove ( ) function unlike its public version does not return any value.

//Node.h

#ifndef H_NODE

#define H_NODE

// definition for class of nodes in bin tree

template < class T > class binTree; // forward declaration

template < class T > class binSTree; // forward declaration

template < class T >

class Node {

friend class binTree < T >; // binTree is friend

friend class binSTree < T >; // binSTree is friend

public:

// default constructor

Node(const T& x = T(), Node < T >* l = 0, Node < T >* r = 0) :

data(x), left(l), right(r) { }

private:

T data; // data component

Node < T > *left, *right; // left and right links

};

#endif

//prog7.cc

#include

#include

#include

#include

using namespace std;

#ifndef H_PROG7

#define H_PROG7

#define SEED 1 // seed for RNG

#define N 100 // num of rand ints

// class to generate rand ints

class RND {

private:

int seed;

public:

RND(const int& s = SEED) : seed(s) { srand(seed); }

int operator ( ) () { return rand() % N + 1; }

};

#define NO_ITEMS 16 // max num of elems printed in line

#define ITEM_W 3 // size of each elem on printout

unsigned sz; // size of vector

// macro to print size

#define COUT_SZ cout << "size = " << setw ( ITEM_W ) << sz << " :"

// function to print elems on stdout

template < class T > void print(T& x)

{

static unsigned cnt = 0;

const string sp(12, ' ');

cout << setw(ITEM_W) << x << ' '; cnt++;

if (cnt % NO_ITEMS == 0 || cnt == sz) cout << endl << sp;

if (cnt == sz) cnt = 0;

}

#endif

//prog7.cc

#include "prog7.h"

#include "binSTree.h"

// This program generates bunch of rand ints in given range

// and stores them in vector, and it also inserts them in

// bin search tree. Then, removes all leaves in tree and

// repeat this process until tree becomes empty.

int main()

{

vector < int > v(N); // holds rand ints

binSTree < int > t; // bin search tree ( BST )

// generate rand ints

generate(v.begin(), v.end(), RND());

// printout contents of vector

sz = v.size(); COUT_SZ;

for_each(v.begin(), v.end(), print < int >); cout << endl;

// insert ints in vector into BST

for (unsigned i = 0; i < v.size(); i++) t.insert(v[i]);

// remove leaves of BST until it becomes empty

bool flag = true; // to check if BST empty

while (flag)

{

// printout contents of BST

sz = t.size(); COUT_SZ;

t.inorder(print < int >); cout << endl;

// remove all leaves of BST

flag = false;

for (unsigned i = 0; i < v.size(); i++)

if (t.remove(v[i])) flag = true;

}

return 0;

}