CSCI 340 Computer Assignment 5 Spring 2018

(10 points)

Binary Tree Class

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 at /home/turing/mhou/public/csci340spring2018.

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

#ifndef ASSIGNMENT5

#define ASSIGNMENT5

class binTree;

class BST;

class Node {

};

class binTree {

public:

binTree(); // default constructor

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

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

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

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

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

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

protected:

Node* root;

// default constructor

// returns height of tree

// return size of tree

// inserts a node in tree

// inorder traversal of tree

// preorder traversal

// postorder traversal

// root of tree

private:

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

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

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

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

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

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

};

#endif

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

1

or right sub-tree of r, depending on the sub-trees heights. 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).

Main:

#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

v[i] = i;

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

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;

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

mcount = rcount = 0;

bt.inorder( display );

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

mcount = rcount = 0;

bt.preorder( display );

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

mcount = rcount = 0;

bt.postorder( display );

cout << endl;

return 0;

}

#endif

Output has to look like this:

Height: 5

Size: 40

In order traverse (displaying first 40 numbers):

38 23 36 22 12 15 16 8

39 6 28 37 18 31 20 35

34 21 2 1 4 13 25 26

14 24 29 5 19 10 11 3

32 33 27 17 9 7 0 30

Pre order traverse (displaying first 40 numbers):

4 28 15 36 23 38 12 22

39 8 16 6 35 31 18 37

20 2 21 34 1 11 24 26

25 13 14 19 5 29 10 17

33 32 3 27 0 7 9 30

Post order traverse (displaying first 40 numbers):

38 23 22 12 36 16 8 6

39 15 37 18 20 31 34 21

1 2 35 28 13 25 14 26

29 5 10 19 24 3 32 27

33 9 7 30 0 17 11 4

Programming Notes:

1. 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.

2. 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.

3. Include any necessary headers and add necessary global constants.

4. You are not allowed to use any I/O functions from the C library, such as scanf or printf.

Instead, use the I/O functions from the C++ library, such as cin or cout.