The ADT "simple binary tree on integers" (non empty) can be specified as a data type "btree" with the following operations:

• is_empty_left: (btree) -> boolean. Tests whether the left subtree is empty.
• is_empty_right: (btree) -> boolean. Tests whether the right subtree is empty.
• root: (btree) -> integer. Returns the information of the root.
• left_sub_bt: (btree) -> btree. Returns the left subtree.
• right_sub_bt: (btree) -> btree. Returns the right subtree.
• leaf: (integer) -> btree. Constructor. Returns a leaf with the given integer as information.
• cons_bt: (integer,btree,btree) -> btree. Constructor. Given an integer n and two btrees t1 and t2, returns the tree which has n in the root, left subtree t1, and right subtree t2.

1. [Points 60] Implement the ADT "btree" as a class in C++. Each node should contain three fields: the information (an integer), and the pointers to the left and to the right subtrees. These fields should be inaccessible from outside the class "btree". The public methods of btree should correspond to the operations of the specification above. More specifically, we should have the following methods corresponding to the first five operations above:

      bool is_empty_left() 
      bool is_empty_right() 
      int root()
      btree* left_sub_bt()
      btree* right_sub_bt()
   

   and the following constructor methods (corresponding respectively to leaf and cons_bt):

      btree(int)
      btree(int,btree*,btree*)
   

   Furthermore, there should be a destructor method

      ~btree()
   

   which, when activated, deallocates all the nodes of the binary tree.

Note 1: If your C++ compiler does not recognize the type bool, you can use int instead.
Note 2: If, you find it much easier (for Exercises 2 and 3) to have "insert" methods which insert new nodes in the tree, you can add them. In such case, use the following specification:

   void insert_left(int n);
   void insert_right(int n);  

where insert_left(n), when applied to a btree t, inserts a new node, with info n, as the left subtree of t, if the corresponding field was NULL. It gives error otherwise. insert_right(n) works analogously, for the right subtree.
2. [Points 20] Define a function search_tree that takes as argument an array of numbers and returns (the pointer to) the search tree which has these numbers on the nodes. The tree does not need to be balanced. Remember that a search tree has the property that every node contains an information that is greater than all the informations contained in the nodes of its left subtree, and smaller than the informations contained in the nodes of its right subtree.
3. [Points 20] Define a procedure in_visit which takes as argument (the pointer to) a btree and prints the informations contained in its nodes, in the in-visit order. (Note that if the btree is a search tree, then this procedure will print an increasing sequence of numbers.)

Note: When you do Exercise 1, you should pretend to be the programmer who implements the class. Just follow the given specification, and assume you don't know about its possible uses. In particular, pretend you don't know that it is going to be used to build search-trees.
When you do Exercises 2 and 3, you should pretend to be a different programmer, who just uses the class, and has no possibility of modifying it. Hence you should define search_tree and in_visit as functions external to the class, or as methods of an extended class, but not as methods of the original class.

Add to your definitions the following program main:

   void main(int ac, char* av[]){
      int i, tot;
      int  *ary;
      tot = ac - 1;
      ary = new int [tot];
      for(i=0; i < tot; i++)  sscanf( av[i+1], "%d", &(ary[i]) );
      btree *t;
      t = search_tree(tot,ary);
      in_visit(t);
      delete t;
      delete ary;
      printf("\n");   
   }

   2 10 4 3 8

   2 3 4 8 10 

Format of the solution

Please make sure that your program can be compiled and executed on Unix.

The format of the input should be as follows:

   % filename n1 n2 n3 n4 ... nM