CSCI 340 Computer Assignment 5 Spring 2018 (10 points) Binary Tree Class For thi
ID: 3726883 • Letter: C
Question
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 <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#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<int> v(MAX_SIZE);
for (int i=1; i<MAX_SIZE; i++)
v[i] = i;
random_shuffle( v.begin(), v.end() );
binTree bt;
vector<int>::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.
Explanation / Answer
C++ Code below with the exact output
//copy paste in a c++ compiler or ideone to see the deisred output
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
void printPostorder(struct node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
printf("%d ", node->key);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->key);
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;
/* first print data of node */
printf("%d ", node->key);
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
int size(struct node* node)
{
if (node==NULL)
return 0;
else
return(size(node->left) + 1 + size(node->right));
}
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Height: %d" , maxDepth(root));
printf(" ");
printf("Size: %d", size(root));
printf(" ");
// print inoder traversal of the BST
printf("Inorder:");
printf(" ");
printInorder(root);
printf(" ");
printf("Preorder:");
printf(" ");
printPreorder(root);
printf(" ");
printf("Postorder:");
printf(" ");
printPostorder(root);
printf(" ");
return 0;
}