binTreeNode.h

#ifndef BINTREENODE_H #define BINTREENODE_H

template class binTree; template class binSTree;

template class binTreeNode { friend class binTree ; friend class binSTree ;

public:

// default constructor binTreeNode ( const T& =T ( ), binTreeNode * = 0, binTreeNode * = 0 );

private:

T data; // data value in node binTreeNode *left, *right; // links to other nodes

};

// default constructor template binTreeNode :: binTreeNode( const T& v, binTreeNode * newLeft, binTreeNod\ e * newRight ) { data = v; // initialize value left = newLeft; // initialize left right = newRight; // initialize right

{

#endif

binSTree.h

#ifndef BINSTREE_H #define BINSTREE_H

#include "binTree.h" #include "binTreeNode.h"

template class binSTree : public binTree { public:

void insert ( const T& x ); // insert 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 ( binTreeNode *&, const T& ); // private version of insert bool search ( binTreeNode *, const T& ) const; // private version of search binTreeNode * remove ( binTreeNode *, const T& ); // private version of remove bool leaf ( binTreeNode * node ) const; // checks if node is leaf };

// insert node with value x template void binSTree::insert ( const T& x ) { insert( this->root, x ); }

// searches leaf with value x template bool binSTree::search ( const T& x ) const { return search( this->root, x ); }

// removes leaf with value x template bool binSTree::remove ( const T& x ) { if( this->size() == 1 ) { this->root = NULL;

return false; }

if( this->size() > 1 ) { if( search( x ) ) this->root = remove( this->root, x );

return true; } else if( this->size() == 1 ) { return false; } else { return false; } }

// private version of insert template void binSTree::insert ( binTreeNode *& p, const T& v ) { if(p == NULL) { p = new binTreeNode( v ); } else if( v < p->data) { insert( p->left, v ); } else if( v > p->data ) { insert( p->right, v ); } else { return; // duplicate } }

// private version of search template bool binSTree::search ( binTreeNode * p, const T& v ) const { if( p == NULL ) return false; else { if( v == p->data ) { if( leaf( p ) ) return true; else return false; } else if( v < p->data ) return search( p->left, v ); else return search( p->right, v ); } }

// private version of remove template binTreeNode* binSTree::remove ( binTreeNode * p, const T& v ) { binTreeNode* curr; binTreeNode* parent; curr = p;

while( curr != NULL ) { if( curr->data == v ) { break; } else { parent = curr;

if( v > curr->data ) curr = curr->right; else curr = curr->left; } }

if( curr != NULL ) { if( parent->right == curr ) parent->right = NULL; else parent->left = NULL;

delete curr; curr = NULL; }

if( this->size() >= 1 ) { return this->root; }

return this->root; }

// checks if node is leaf template bool binSTree::leaf ( binTreeNode * p ) const { if( p->left == NULL && p->right == NULL ) { return true; // node is a leaf } else { return false; // node is not a leaf } }

#endif

prog7.cc

#include "binSTree.h" #include #include #include #include #include using namespace std;

#define SEED1 1 // seed for 1st RNG #define SEED2 31 // seed for 2nd RNG

#define N1 50 // size of 1st vector #define N2 100 // size of 2nd vector #define R 1000 // high val for rand integer

#define LSIZE 20 // no of vals printed on line #define ITEM_W 4 // no of spaces for each item

unsigned sz; // size of tree

// class to generate rand ints class RND { private: int seed, high; public: RND ( const int& s = 1, const int& h = 1 ) : seed ( s ), high ( h ) { srand ( seed ); } int operator ( ) ( ) const { return rand ( ) % ( high + 1 ); } };

// prints out val passed as argument template < class T > void print ( const T& x ) { static unsigned cnt = 0; cout << setw ( ITEM_W ) << x << ' '; cnt++; if ( cnt % LSIZE == 0 || cnt == sz ) cout << endl; if ( cnt == sz ) cnt = 0; }

// prints out size and height of bin search tree and // data val in each node in sorted order template < class T > void print_vals ( binSTree < T >& tree ) { // print size and height of tree sz = tree.size ( ); unsigned ht = tree.height ( ); cout << "size of tree = " << sz << endl; cout << "height of tree = " << ht << endl << endl;

// print data values of tree in sorted order tree.inOrder ( print ); cout << endl; }

// driver program: to test several member functions // of bin search tree class

int main ( ) { // create 1st vector and fill it with rand ints vector < int > v1 ( N1 ); generate ( v1.begin ( ), v1.end ( ), RND ( SEED1, R ) );

// create 2nd vector and fill it with rand ints vector < int > v2 ( N2 ); generate ( v2.begin ( ), v2.end ( ), RND ( SEED2, R ) );

// create bin search tree with int vals in 1st vector binSTree < int > tree; for (unsigned i = 0; i < v1.size ( ); i++) tree.insert ( v1 [ i ] );

// print vals of bin search tree before removals cout << "Values of bin search tree before removals "; cout << "----------------------------------------- "; print_vals ( tree );

// print vals of 2nd vector in sorted order and // deleting duplicate vals

cout << "Values in 2nd vector in sorted order "; cout << "------------------------------------ "; vector < int > v3 = v2; sort ( v3.begin ( ), v3.end ( ) ); auto p = unique ( v3.begin ( ), v3.end ( ) ); v3.resize ( p - v3.begin ( ) ); sz = v3.size ( ); for_each ( v3.cbegin ( ), v3.cend ( ), print < int > ); cout << endl;

// delete vals in 2nd vector from binary search tree for ( unsigned i = 0; i < v2.size ( ); i++ ) tree.remove ( v2 [ i ] );

// print vals of bin search tree after removals cout << "Values of bin search tree after removals "; cout << "---------------------------------------- "; print_vals ( tree );

return 0;

}

binTree.h

#ifndef BINTREE_H #define BINTREE_H #include #include "binTreeNode.h"

template class binTree { public:

binTree ( ); // default constructor bool empty ( ) const; // checks if tree empty int size ( ) const; // returns no of nodes int height ( ) const; // returns height of tree virtual void insert ( const T& ); // inserts a node in shortest subtree

binTree ( const binTree & ); // copy constructor binTree & operator = ( const binTree & ); // assignment operator virtual ~binTree ( ); // destructor void clear ( ); // destroys tree

void inOrder ( void ( * ) ( T& )); // inorder traversal of tree

void preOrder ( void ( * ) ( T& )); // preorder traversal of tree void postOrder ( void ( * ) ( T& )); // postorder traversal of tree

protected:

binTreeNode * root; // root of tree

private:

int size ( binTreeNode * ) const; // private version of size int height ( binTreeNode * ) const; // private version of height

void insert ( binTreeNode *&, const T& ); // private version of insert

void inOrder ( binTreeNode *, void ( * ) ( T& )); // private version of in\ Order void preOrder ( binTreeNode *, void ( * ) ( T& )); // private version of p\ reOrder void postOrder ( binTreeNode *, void ( * ) ( T& )); // private version of \ postOrder

void clear ( binTreeNode *& ); // private version of clear binTreeNode * copy ( const binTreeNode * ); // creates clone of tree

};

// default constructor template binTree ::binTree( ) { root = 0; // initialize root }

// checks if tree empty

template bool binTree::empty( ) const { if( root == 0 ) { return true; // empty tree } else { return false; }

}

// returns no of nodes template int binTree ::size( ) const { return size( root ); // call recursive }

// returns height of tree template

int binTree ::height( ) const { return height( root ); // call recursive }

// inserts a node in shortest subtree template void binTree ::insert( const T& v ) { insert( root, v ); // call recursive }

// inorder traversal of tree template void binTree ::inOrder( void ( *fn ) ( T& ) ) { inOrder( root, fn ); // call recursive }

// preorder traversal of tree template void binTree ::preOrder( void ( *fn ) ( T& ) )

{ preOrder( root, fn ); // call recursive }

// postorder traversal of tree template void binTree ::postOrder( void ( *fn ) ( T& ) ) { postOrder( root, fn ); // call recursive }

// private version of size template int binTree ::size( binTreeNode * ptr ) const { if( ptr != 0 ) // if not empty { return 1 + size( ptr->left ) + size( ptr->right ); } else { return 0; // emtpy tree

} else { int lHeight = height( ptr->left ); // left side int rHeight = height( ptr->right ); // right side

if( lHeight > rHeight ) // which is greater { return 1 + lHeight; // return left } else {

return 1 + rHeight; // return right } } }

// private version of insert template void binTree ::insert( binTreeNode * & p, const T& v ) { if( p == 0 ) {

binTreeNode * newNode; newNode = new binTreeNode ( v ); // new node with new value p = newNode; // set ptr to new node } else { int lHeight = height( p->left ); int rHeight = height( p->right );

if( lHeight <= rHeight ) {

insert( p->left, v ); } else { insert( p->right, v ); } } }

// private version of inOrder template

void binTree ::insert( binTreeNode * & p, const T& v ) { if( p == 0 ) { binTreeNode * newNode; newNode = new binTreeNode ( v ); // new node with new value p = newNode; // set ptr to new node } else { int lHeight = height( p->left ); int rHeight = height( p->right );

if( lHeight <= rHeight ) {

insert( p->left, v ); } else { insert( p->right, v ); } } }

// private version of inOrder template

void binTree ::inOrder( binTreeNode * p, void ( *fn ) ( T& ) ) { if( p != NULL ) { inOrder( p->left, fn ); fn( p->data ); inOrder( p->right, fn ); } }

// private version of preOrder

template void binTree ::preOrder( binTreeNode * p, void ( *fn ) ( T& ) ) { if( p != NULL ) { fn( p->data ); preOrder( p->left, fn ); preOrder( p->right, fn ); } }

// private version of postOrder template void binTree ::postOrder( binTreeNode * p, void ( *fn ) ( T& ) ) { if( p != NULL ) { postOrder( p->left, fn ); postOrder( p->right, fn ); fn( p->data ); } }

// copy constructor template binTree ::binTree ( const binTree & t) { root = copy( t.root ); }

// assignment operator template binTree& binTree::operator= (const binTree& p)

{ if( this != &p ) { clear(root); // clear tree root = copy(p.root); // copy tree } return *this; }

// destructor template

binTree ::~binTree ( ) { clear(); }

// destroys tree template void binTree ::clear ( ) { clear( this->root ); root = NULL;

}

// private version of clear template void binTree ::clear ( binTreeNode *& p ) { if( p != NULL ) { clear( p->left ); clear( p->right ); delete p;

} }

// creates clone of tree template binTreeNode * binTree::copy ( const binTreeNode * p ) { binTreeNode * newNode; if(p != NULL) { newNode = new binTreeNode( p->data );

newNode->left = copy( p->left ); newNode->right = copy( p->right ); return newNode; } else { return NULL; } }

#endif

getting these errors please help:

prog7.cc: In instantiation of void print_vals(binSTree&) [with T = int]: prog7.cc:73:23: required from here prog7.cc:49:5: error: no matching function for call to binSTree::inOrder() tree.inOrder ( print ); cout << endl; ^~~~ In file included from binSTree.h:4:0, from prog7.cc:1: binTree.h:87:6: note: candidate: void binTree::inOrder(void (*)(T&)) [with T = int] void binTree ::inOrder( void ( *fn ) ( T& ) ) ^~~~~~~~~~~ binTree.h:87:6: note: no known conversion for argument 1 from to void (*)(int&) binTree.h:172:6: note: candidate: void binTree::inOrder(binTreeNode*, void (*)(T&)) [with T = int] void binTree ::inOrder( binTreeNode * p, void ( *fn ) ( T& ) ) ^~~~~~~~~~~ binTree.h:172:6: note: candidate expects 2 arguments, 1 provided

.,