For this computer assignment, you are to write a C++ program to implement classes to represent a binary tree (of integers). You are required to implement assignment5.h and assignment5.cc files. Both of them are partially implemented. assignment5.h already contains the class definition of binTree, and assignment5.cc already contains implementation of the main() function. Both files are available

The definition of the binary tree class is given here to facilitate the following description

class binTree {

public:

binTree ( ); // default constructor

int height ( ) const; // returns height of tree

unsigned size () const; // return size of tree

virtual void insert ( int ); // inserts a node in tree

void inorder( void(*)(int) ); // inorder traversal of tree

void preorder( void(*)(int) ); // preorder traversal

void postorder( void(*)(int) ); // postorder traversal

protected: Node* root; // root of tree

private: int height(Node*) const; // private version of height()

unsigned size(Node*) const; // private version of size()

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

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

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

void postorder( Node*, void(*)(int));// private version of postorder() };

Most of the public member functions of the binTree class call private member functions of the class (with the same name). All of these private member functions can be implemented as either recursive or non-recursive, but clearly, recursive versions of these functions are preferable because of their short and simple implementations in code.

Because of information hiding, a client is not permitted to access the binary tree directly, so the root of the tree is kept protected (not private because of future implementations of derived classes from the base class of the binTree), so it cannot be passed as an argument to any of the public functions of the tree. It is essential to have private utility functions, which act as interface between a client and the tree.

The private insert(), size(), height(), and inorder() functions of the binTree class are described as following. preorder() and postorder() are similar to inorder().

insert ( Node*& r, int x ) : This function is used to insert a node with the data value x in a binary (sub-)tree at root r, applying the following technique: if the tree is empty, then the new node will be the root of the tree with the value x; otherwise, x is inserted in the left

or right sub-tree of r, depending on the sub-trees sizes. If the size of the right sub-tree is less than the size of the left sub-tree, x is inserted in the right sub-tree; otherwise x is inserted in the left sub-tree.

size(Node* r) const : This function returns the number of nodes in the tree rooted at r. If the tree is empty, the size is 0.

height(Node* r) const : This function returns the height of the tree rooted at r. If the tree is empty, the size is -1.

Inorder ( Node* r, void(* p)(int) ) : This function traverse the tree rooted at r. p is the visit operation on each node. To visit r, simply invoke p(r->data).

. You need to add the definition of the Node class in the file assignment5.h. You need to make binTree class a friend of the Node class

The file assignment5.cc also contains some constants, global variables, and the implementation of function display(), which is invoked by main(). You need to add the implementation of binTree class (and Node class if necessary) in assignment5.cc

***********

assignment5.cc file

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

const int MAX_SIZE = 40; const int MAX_COUNT = 40; const int WIDTH = 5; const int ROW_SIZE = 8;

int mcount = 0; int rcount = 0;

void display(int d) { if ( mcount < MAX_COUNT ) { cout << setw(WIDTH) << d; mcount++; rcount++; if ( rcount == ROW_SIZE ) { cout << endl; rcount = 0; } } }

#define BINTREE_MAIN #ifdef BINTREE_MAIN int main() { vector v(MAX_SIZE); for (int i=1; i

binTree bt; vector::iterator it; for (it=v.begin(); it!=v.end(); it++) bt.insert( *it );

cout << "Height: " << bt.height() << endl; cout << "Size: " << bt.size() << endl;

*******

header file

assignment5.h

#ifndef ASSIGNMENT5 #define ASSIGNMENT5

class binTree; class BST;

class Node { };

class binTree { public: binTree(); virtual void insert( int ); int height() const; unsigned size() const; void inorder( void(*)(int) ); void preorder( void(*)(int) ); void postorder( void(*)(int) );

protected: Node* root;

private: void insert( Node*&, int ); int height( Node* ) const; unsigned size( Node* ) const; void inorder( Node*, void(*)(int) ); void preorder( Node*, void(*)(int) ); void postorder( Node*, void(*)(int) ); };

#endif