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

Most of the public member functions of the BinaryTreeclass call private member functions of the class (with thesame name). These private member functions can beimplemented as either recursive or non-recursive, butclearly, recursive versions of thesefunctions are preferable because of their short and simpleimplementations in code. However, they require more memory andusually slower than their non-recursive versions inexecution, especially for a large amount of input data.

#ifndef H_BINARYTREE

#define H_BINARYTREE

template class BinaryTree{

public:

    BinaryTree();                                      //default constructor

    unsigned     getSize()const;                      //returns size of tree

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

    virtual void Insert(constT&);                     //inserts node in tree

    void         Inorder(void(*)(constT&));          //inorder traversal of tree

protected:

    Node*root;                                      //root of tree

private:

    unsigned _getSize(Node *)const;                 //private version of getSize()

    unsigned _getHeight(Node *)const;               //private version of getHeight()

    void     _Insert(Node*&, constT&);             //private version of Insert()

    void     _Inorder(Node*, void (*)(const T&));   // private version ofInorder()

};

#endif // End of H_BINARYTREE

Because of information hiding, a client is not permitted toaccess the binary tree directly, so the root of the treeis kept protected (not private because of futureimplementations of derived classes from the base class of theBinaryTree), so it cannot be passed as an argument to any of thepublic functions of the tree. It is essential to haveprivate utility functions, which act as interface betweena client and the tree. The Insert() function of the BinaryTreeclass is described as follows:

• Insert(const T &x) This virtual function can beused to insert a node with the data value x in a binary tree,applying the following technique: if the tree is empty, then thenew node will be the root of the tree with the value x; otherwise,the left or the right subtree is randomly selectedand the value x is inserted in that side. To implement the randomselection, you can use the following RNG.

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

Put the implementation of your BinaryTree class in the headerfile binarytree.h. Definition of the class Node,which represents the nodes in a binary tree, can be found in theheader file node.h. To use the class Node in yourprogram, include the header file node.h, inserting#include \"node.h\" at the top of your header file.

The source file binarytreeDriver.cc containsthe driver program. In addition to the main() routine, it has theimplementations of the following routines (as templates) and thedefinitions of the two RNGs used in the main() routine.

• template void print(const T &x):
• template void printValues(BinaryTree &tree, const string&name);

The unary function print() can be used as an argument to themember functions Inorder() to print the value of its argument x.The function printValues() does the followings:

• it prints name, which is the name of the tree, and it alsoprints the height of the tree.
• it calls the member function Inorder() to print the data valuesin the tree in inorder.

The class RND1 can be used to generate random integers in therange [LOW1 = –999, HIGH1 = 999] and the class RND2 can be used togenerate 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 valuesin vector containers vector A(N1) and vector B(N2) byusing the generate() function in the STL, where N1 = 100 and N2 =50 are the sizes of these two vectors.

The main() routine copies the random values from vectors A and Band inserts them in the binary trees first and second,respectively. At the end, the data values in the binary trees firstand second are printed out on stdout with LSIZE = 12 numbers in asingle line.

Put the implementation of your BinaryTree class in the headerfile binarytree.h. Definition of the class Node,which represents the nodes in a binary tree, can be found in theheader file node.h. To use the class Node in yourprogram, include the header file node.h, inserting#include \"node.h\" at the top of your header file.

The source file binarytreeDriver.cc containsthe driver program. In addition to the main() routine, it has theimplementations of the following routines (as templates) and thedefinitions of the two RNGs used in the main() routine.

• template void print(const T &x):
• template void printValues(BinaryTree &tree, const string&name);

The unary function print() can be used as an argument to themember functions Inorder() to print the value of its argument x.The function printValues() does the followings:

• it prints name, which is the name of the tree, and it alsoprints the height of the tree.
• it calls the member function Inorder() to print the data valuesin the tree in inorder.

The class RND1 can be used to generate random integers in therange [LOW1 = –999, HIGH1 = 999] and the class RND2 can be used togenerate 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 valuesin vector containers vector A(N1) and vector B(N2) byusing the generate() function in the STL, where N1 = 100 and N2 =50 are the sizes of these two vectors.

The main() routine copies the random values from vectors A and Band inserts them in the binary trees first and second,respectively. At the end, the data values in the binary trees firstand second are printed out on stdout with LSIZE =12 numbers in a single line.

BINARYTREE.CC

#include

#include

#include

#include

#include

using namespace std;

#include \"binarytree.h\"

#define SEED 1  // seed for RNGs

#define N1    100   // sizeof 1st vector container

#define LOW1  -999  // low val for randinteger

#define HIGH1 999   // high val for randinteger

#defineN2    50      //size of 2nd vector container

#define LOW2  -99999  // low val for randfloat

#define HIGH2 99999   // high val for randfloat

#definePREC  2       // no ofdigits after dec pt

#define LSIZE  12  // no of vals printed online

#define ITEM_W 7   // no of spaces for eachitem

// prints single val

template

void print(const T&);

// prints data vals in tree

template

void print_vals(BinaryTree&, conststring&);

// 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(rand() % (high - low + 1) + low)) /pow(10, prec); }

};

// prints val passed as argument

template

void print(const T& x) {

  static unsigned cnt = 0;

  cout << setw(ITEM_W) << x << '';

  cnt++;

  if (cnt % LSIZE == 0) cout << endl;

}

// prints size and height of bin tree and data val in

// each node in inorder

template

void print_vals(BinaryTree& tree, const string&name) {

  cout << name << \": \";  //print name of tree

  // print size and height of tree

  cout << \"size = \" << tree.getSize()<< \", \";

  cout << \"height = \" << tree.getHeight()<< 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 ofBinaryTree class

int main() {

  srand(SEED);  // set seed for RNGs

  // create 1st vector and fill it with rand ints

  vector A(N1);

  generate(A.begin(), A.end(), RND1(LOW1, HIGH1));

  // create binary tree with int vals in vector A,

  // and print all vals of tree

  BinaryTree 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 randfloats

  vector B(N2);

  generate(B.begin(), B.end(), RND2(LOW2, HIGH2,PREC));

  // create binary tree with float vals in vectorB,

  // and print all vals of tree

  BinaryTree second;

  for (unsigned i = 0; i < B.size(); i++)second.Insert(B[i]);

  print_vals(second, \"second\");

  cout << endl;

  return 0;

}