C++

WRITE THE IMPLEMENTATION FOR BINSTREE.H

DUE DATE 11/07

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& ) ;// 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.h

#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;

}

//binTree.h

ifndef BINTREE_H

#define BINTREE_H

#include "Node.h"

#include

using namespace std;

template < class T > class binTree {

//public function versions call the private functions

public:

// default constructor

binTree();

// returns height of BT

unsigned height() const;

// inserts node in BT

virtual void insert(const T&v);

// inorder traversal of BT

void inorder(void(*fn)(const T&));

protected:

//Root for tree

Node < T >* root;

private:

// private versions of functions that have access to nodes and root

unsigned height(Node < T >*) const;

void insert(Node < T >*&p, const T&v);

void inorder(Node < T >*p, void(*fn) (const T&));

};

//type definition

typedef enum { left_side, right_side } SIDE;

SIDE ran() { return rand() % 2 ? right_side : left_side; }

//default consturctor initializez root

template

binTree ::binTree()

{

root = 0;

}

//public function calls private and returns the height of the BT

template

unsigned binTree ::height() const

{

return height(root);

}

//calls private insert

template

void binTree ::insert(const T& v)

{

insert(root, v);

}

//calls private inorder function

template

void binTree ::inorder(void(*fn)(const T&))

{

inorder(root, fn);

}

//private function definitions

template

unsigned binTree ::height(Node < T >* p) const

{

//If the node is empty it returns 0

if (p == 0)

{

return 0;

}

else

{

//Using recursion to find height of BT

//left side

int leftHeight = height(p->left);

//right side

int rightHeight = height(p->right);

//determines which is side has the greater height

if (leftHeight > rightHeight)

{

return 1 + leftHeight;

}

else

{

return 1 + rightHeight;

}

}

}

//inserts a value into node

template

void binTree ::insert(Node < T >*&p, const T&val) {

if (p == nullptr)

{

//sets p to a new node

p = new Node (val);

}

else

{

//randomizes the variable

SIDE s = rnd();

//condition to put value into either left or right

if (s == left_side)

{

insert(p->left, val);

}

else

{

insert(p->right, val);

}

}

}

//prints the tree inorder

template

void binTree ::inorder(Node < T >*p, void(*fn) (const T&)) {

if (p != NULL)

{

inorder(p->left, fn);

fn(p->data);

inorder(p->right, fn);

}

}

#endif