Question

For this computer assignment, you are to write a C++ program to implement a class for binary trees. To deal with variety of data types, implement this class as a template.

The definition of the class for a binary tree (as a template) is given as follows:

template < class T > class binTree {

public:

binTree ( ); // default constructor

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

virtual void insert ( const T& ); // inserts a node in tree

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

protected:

Node < T >* root; // root of tree

private:

unsigned height ( Node < T >* ) const; // private version of height ( )

void insert ( Node < T >*&, const T& ); // private version of insert ( )

void inorder ( Node < T >*, void ( * ) ( const T& ) ); // private version of inorder ( ) };

Most of the public member functions of the binTree class call private member functions of the class (with the same name). 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. However, they require more memory and usually slower than their non-recursive versions in execution, especially for a large amount of input data.

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 insert ( ) function of the binTree class is described as follows:

insert ( const T& x ) : This virtual function can be used to insert a node with the data value x in a binary tree, 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, the left or the right subtree is randomly selected and the value x is inserted in that side. To implement the random selection, you can use the following RNG.

typedef enum { left_side, right_side } SIDE; SIDE rnd ( ) { return rand ( ) % 2 ? right_side : left_side; }

Put the implementation of your binTree class in the following header file:

binTree.h: Definition of the class Node, which represents the nodes in a binary tree, can be found in the header file Node.h

The source file prog6.cc contains the driver program. In addition to the main ( ) routine, it has the implementations of the following routines (as templates) and the definitions of the two RNGs used in the main ( ) routine.

o template < class T > void print ( const T& x ):

o template < class T > void print_vals ( binTree < T >& tree, const string& name );

The unary function print ( ) can be used as an argument to the member functions inorder ( ) to print the value of its argument x. The function print_vals ( ) does the followings: first, it prints name, which is the name of the tree, and it also prints the height of the tree. Then, it calls the member function inorder ( ) to print the data values in the tree in inorder. The class RND1 can be used to generate random integers in the range [ LOW1 = –999, HIGH1 = 999 ] and the class RND2 can be used to generate random floating-point numbers in the range [ LOW2 = –999.99, HIGH2 = 999.99 ]. The function objects RND1 ( ) and RND2 ( ), generated from these classes, are used to fill in the random values in vector containers vector < int > A ( N1 ) and vector < float > B ( N2 ) by using the generate ( ) function in STL, where N1 = 100 and N2 = 50 are the corresponding sizes of these two vectors. The main ( ) routine copies the random values from vectors A and B and inserts them in the binary trees first and second, respectively. At the end, the data values in the binary trees first and second are printed out on stdout with LSIZE = 12 numbers in a single line

Here is my code, just getting wrong output, please help

Node.h

#ifndef NODE_H
#define NODE_H

template <class T> class binTree;

template <class T> class Node
{
   friend class binTree <T>;
   public:
       //The node defualt constructor
       Node ( const T& =T ( ), Node <T>* = 0, Node <T>* = 0 );

   private:
       T nodeContent;
       Node <T> *leftChild, *childRight;
};

// default constructor
template <class T>
Node <T>:: Node( const T& temp, Node <T>* newLeft, Node <T>* newRight )
{
   nodeContent = temp;
   leftChild = newLeft;
   childRight = newRight;
}

#endif

binTree.h

#ifndef BINTREE_H
#define BINTREE_H

#include "Node.h"

template <class T> class binTree
{
   public:

       binTree ( );
       int height ( ) const;
       virtual void insert ( const T& );
       void inOrder ( void ( * ) ( T& ));
   protected:
       Node <T>* root;
   private:
       int height ( Node <T>* ) const;
       void insert ( Node <T>*&, const T& );
       void inOrder ( Node <T>*, void ( * ) ( T& ));
};

//function definitions
template <class T>
binTree <T>::binTree( )
{
   //set the root
   root = 0;
}

// returns height of tree
template <class T>
int binTree <T>::height( ) const
{
    return height( root ); // call recursive
}

//to insert the node in the binary tree
//recursive function
template <class T>
void binTree <T>::insert( const T& temp )
{
    insert( root, temp );
}

//To perform inorder traversal of the tree
template <class T>
void binTree <T>::inOrder( void ( *print ) ( T& ) )
{
    inOrder( root, print );
}

// private version of height
template <class T>
int binTree <T>::height( Node <T>* ptr ) const
{
   if( ptr == 0 )
   {
       return 0;
   }
   else
   {
       int heightleft = height( ptr->leftChild );
       int heigRight = height( ptr->childRight );
  
       if( heightleft > heigRight )
       {
           return 1 + heightleft;
       }
       else
       {
           return 1 + heigRight;
       }
   }
}

template <class T>
void binTree <T>::insert( Node <T>* & nod, const T& temp )
{
   if( nod == 0 )
   {
       Node <T> * newNode;
       newNode = new Node <T>( temp );
       nod = newNode;
   }     
   else
   {
       int heightleft = height( nod->leftChild );
       int heigRight = height( nod->childRight );
  
       if( heightleft <= heigRight )
       {
           insert( nod->leftChild, temp );
       }
       else
       {
           insert( nod->childRight, temp );
       }
   }
}

//inorder traversa
template <class T>
void binTree <T>::inOrder( Node <T>* nod, void ( *print ) ( T& ) )
{
   if( nod != NULL )
   {
       inOrder( nod->leftChild, print );
       print( nod->nodeContent );
       inOrder( nod->childRight, print );
   }
}

#endif

prog6.cpp

#include <iostream>
#include<cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include "binTree.h"

using namespace std;
class RND1{
   int x;
public:
   static int RND(){
   srand(time(NULL));
   return (-999+ (rand() % (static_cast<int>(999 +999 + 1))));
   srand(time(NULL));
   }

};

class RND2{
   float randm;
public:
   static float RND()
   {
       srand(time(NULL));
       return -999.99 + static_cast <float> (rand()) /( static_cast <float> (RAND_MAX/(999.99+999.99)));
   }

};

template <class T>
void print(T a)
{
    cout<<a<<" ";
}

int main()
{
    srand(unsigned(time(0)));
    vector<int> A(100);
    vector<float> B(50);
    RND1 obj3=RND1();

    std::cout << "\nIn order traversal of int tree: \n";
    binTree <int> tr=binTree <int> ( );
    int count=1;
    generate(A.begin(), A.end(), &RND1::RND);
    for (auto iv: A) {
           tr.insert(iv);
    }

tr.inOrder(&print);

    //float tree
        std::cout << "\n\nIn order traversal of float tree: \n";
   binTree <float> tr1=binTree <float> ( );
   generate(B.begin(), B.end(), &RND2::RND);
   for (auto iv: B) {
            tr1.insert(iv);
          }

   tr1.inOrder(&print);
   //print heights

   cout<<"\nint tree height"<<tr.height();

   cout<<"\nfloat tree height"<<tr1.height();
   cout<<endl;
    system("pause");
    return 0;
}

here is what it should be ouputting

first: height of tree = 10

Data values in 'first' inorder:

826 479 871 -787 139 -319 243 379 919 -337 -329 -621
639 256 -692 -703 596 57 64 -906 -831 657 -955 -617
923 -304 -524 -928 604 218 -80 136 790 978 -925 -660
-541 -706 -190 785 -856 756 191 179 -899 488 176 979
992 -304 -996 -551 -236 -715 471 424 -417 509 -375 -547
79 398 949 -439 -276 293 220 -641 873 -902 804 472
-436 -824 252 111 -822 -460 800 974 559 595 -318 -743
-386 -685 157 446 -38 -155 -985 615 610 -900 727 -957
-277 -429 -741 -418

second: height of tree = 8

Data values in 'second' inorder:

-621.05 -570.48 237.14 975.37 51.42 777.25 -623.73 -965.47 -591.68 546.78 974.32 -691.54
-616.89 840.06 572.52 -313.42 984.63 -563.99 478.9 -909.31 -493.92 318.93 -184.09 -446.25
469.7 957.73 774.68 -974.78 135.85 286.91 -974.2 652.83 605.56 -256.83 -621.87 -892.59
-760.51 -565.89 -726.96 459.03 -41.61 -410.55 -6.97 -60.01 65.96 899.21 -816.94 -148.48
-310.26 236.28

Answer 1

main.cpp

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

#include "binTree.h"

#define SEED       1 // seed for RNGs

#define N1       100 // size of 1st vector container
#define LOW1    -999 // low val for rand integer
#define HIGH1    999 // high val for rand integer

#define N2        50 // size of 2nd vector container
#define LOW2 -99999 // low val for rand float
#define HIGH2 99999 // high val for rand float
#define PREC       2 // no of digits after dec pt

#define LSIZE     12 // no of vals printed on line
#define ITEM_W     7 // no of spaces for each item

// prints single val
template < class T > void print ( const T& );

// prints data vals in tree
template < class T > void print_vals ( binTree < T >&, const string& );

// class to generate rand ints
class RND1 {
private:
    int low, high;
public:
    RND1 ( const int& l = 0, const int& h = 1 ) : low ( l ), high ( h ) { }
    int operator ( ) ( ) const {
        return rand ( ) % ( high - low + 1 ) + low;
    }
};

// class to generate rand floats
class RND2 {
private:
    int low, high, prec;
public:
    RND2 ( const int& l = 0, const int& h = 1, const int& p = 0 ) :
        low ( l ), high ( h ), prec ( p ) { }
    float operator ( ) ( ) const {
        return ( static_cast < float >
            ( rand ( ) % ( high - low + 1 ) + low ) ) / pow ( 10, prec );
    }
};

// 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 ) cout << endl;
}

// prints out height of bin tree and data val in each node in inorder
template < class T >
void print_vals ( binTree < T >& tree, const string& name )
{
    cout << name << ": "; // print name of tree

    // print height of tree
    cout << "height of tree = " << tree.height ( ) << endl << endl;

    // print data values of tree in inorder
    cout << "Data values in '" << name << "' inorder:\n\n";
    tree.inorder ( print ); cout << endl;
}

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

int main ( )
{
    srand ( SEED ); // set seed for RNGs

    // create 1st vector and fill it with rand ints
    vector < int > A ( N1 );
    generate ( A.begin ( ), A.end ( ), RND1 ( LOW1, HIGH1 ) );

    // create bin tree with int vals in vector A,
    // and print all vals of tree

    binTree < int > first;
    for (unsigned i = 0; i < A.size ( ); i++)
        first.insert ( A [ i ] );
    print_vals ( first, "first" ); cout << endl;

    // create 2nd vector and fill it with rand floats
    vector < float > B ( N2 );
    generate ( B.begin ( ), B.end ( ), RND2 ( LOW2, HIGH2, PREC ) );

    // create bin tree with float-pt vals in vector B,
    // and print all vals of tree

    binTree < float > second;
    for ( unsigned i = 0; i < B.size ( ); i++ )
        second.insert ( B [ i ] );
    print_vals ( second, "second" ); cout << endl;

   
    return 0;
}

binTree.h

#ifndef BINTREE_H
#define BINTREE_H

//#include "/home/cs340/progs/16f/p6/Node.h"
#include "Node.h"

template <class T> //foward declartion of binTree class
class binTree;

template <class T>
class binTree {
    public:
    binTree() { root = NULL; };         //default constructor, sets root to NULL
    unsigned height () const;       //public height()
    virtual void insert( const T& );    //public insert()
    void inorder( void (*) (const T&) );    //public inorder()

    typedef enum { left_side, right_side } SIDE;
    SIDE rnd ( ) { return rand ( ) % 2 ? right_side : left_side; } //Used to decide random placement of Nodes, either left or right side
                                    //If the number is even, right side - else left side
    protected:
    Node <T>* root; //root of tree

    private:
    unsigned height( Node<T>* ) const;          //private height()
    void insert( Node<T>*&, const T& );             //private insert()
    void inorder( Node<T>*, void (*) (const T&) );      //private inorder()
};

/*
*Public version*
height() const
returns: The height of the tree
arguments: none
purpose: calls the private version of height()
*/
template <class T>
unsigned binTree<T>::height() const {
    return height(root);
}

/*
*Public version*
inorder()
returns: nothing
arguments: A pointer to a function that takes a class T element
Purpose: Calls the private version of inorder()
*/
template <class T>
void binTree<T>::inorder( void (*func) (const T& ) ) {
    inorder(root, func );
}

/*
*Public version*
insert()
returns: nothing
arugments: a reference to a constant class T, called element
Purpose: calls the private version of insert()
*/
template <class T>
void binTree<T>::insert( const T& element ) {
    insert(root, element);
}

/*
*Private version*
height() const
arguments: a pointer to a Node of class T, called ptr (holds the root)
returns: the height of the tree
purpose: finds the height of the tree,
    if there are no Nodes, returns a height of 0
*/
template <class T>
unsigned binTree<T>::height( Node<T>* ptr) const {
    if(!ptr) //if null, height = 0
        return 0;

    return 1 + max(height(ptr->left), height(ptr->right)); //finds tree height
}

/*
*Private version*
insert()
returns: nothing
arguments: A pointer to a reference Node of class T, called ptr (holds the root)
    A constant reference to a class T, called element (element to be inserted)
purpose: Adds an item to the tree,
    If there is no Node, creates a new one, sets necessary pointers to NULL and sets Node data to the element.
    Decides where to make the new Node based on rnd() method call
*/
template <class T>
void binTree<T>::insert( Node<T>*& ptr, const T& element) {
    if(ptr == NULL) {
        ptr = new Node<T>();
        ptr->right = NULL;
        ptr->left = NULL;
        ptr->data = element;
    }
    else if( rnd() == right_side ) //if rnd == right_side, make new node on right
        insert(ptr->right, element);
    else //else left
        insert(ptr->left, element);

}

/*
*Private version*
inorder()
returns: nothing
arguments: a pointer to a Node of class T, called ptr (holds root).
    A pointer function that takes a class T argument
Purpose: Goes through the tree using in order method, using recursion
*/
template <class T>
void binTree<T>::inorder( Node<T>* ptr, void (*func) (const T& ) ) {
    if(ptr != NULL) {
        inorder(ptr->left,func );
        func( ptr->data );
        inorder(ptr->right, func);
    }
}

#endif

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 Node {
friend class binTree < T >;         // binTree 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

CAUserslsowmi\DesktoplProjectl.exe first: height of tree9 Data values in ' firstinorder: 846 966 430 -846 329 179 -903 -486 380 680 540 550 560 -282 -592 -594 -544 823 -164 439 -388 -798 -272 708 682 938 544 373 484 728 549 -170 639 -221 -361 -651 737 -687 543 870 274 843 -370 -878 -732 -333 -274 658 450 338 -267 149 -134 899 964 -678 358 -958 -611 922 293 -450 -662 898 904 948 732 -707 -840 -234 817 -873 -340 -508 -523 460 -677 -321 905 -523 -226 746 -952 second: height of tree '? Data values in ' second' inorder 723.88-944.43-885.37 -785.4-996.99-870.61-934.88 -777.2 -826.01 -778.57 906.86-772.98 953.24-898.23-815.56-682.16-894.51-983.73-673.21-878.06-982.47-734.65 771.51-899.59 855.86-930.37 -873.26-991.24-821.29-872.65-680.65 -751.44-795.75-742.94 833.58-977.76 691.22 -983.62 -772.58 -821.74-841.18 -798.24-801.44-762.45-967.78 -717.03 980.06-847.94 761.49-868.57 Process exited after .1122 seconds with return value 0 Press any key to continue .. .