CSE 109 Programming Assignment #2   Due: 10:45 Thursday 1 March 2012
  [Late collections 10:45 PM  11 March, 12 March]

 This assignment is an exercise in using pointers and in writing recursive
 methods for a class implementing the ADT for a Binary Search Tree.
 Finish writing the class Tree that we started writing in lecture.

 In /proj/csc109/p2 you will find the file tree.cc, which is based on what
 I developed in lecture.  Add to declaration of and definitions for class
 Tree the following methods and data members (I use () to indicate that a
 given identifier is a method, but I do not mean to say that is must have no
 parameters):


   1.  size() returns the number of nodes in the tree
   2.  resetIter(), which resets the iterator so that it is prepared to
       return the first key in the tree
   3.  iterNext(), which returns the "next" key in the tree. The
         program crashes if there is no next key.
   4.  iterPeek(), which returns the key that would be returned
       if iterNext() were called. Note: iterNext() moves the iterator,
       while iterPeek() does not.
   5.  iterAtEnd() which returns true if and only if there are no more
       keys for the iterator to return
   6.  the operator "==", where for Trees a==b, if the two trees have the
       same keys and corresponding data
   7.  identical(), where Trees a and b are identical if the they have the
       same shape and the same keys and corresponding data
   8.  whatever data members are necessary to implement the above methods
   9.  other methods that you use to implement the above methods, e.g.,
       "helper methods."


 Start this assignment by creating the subdirectory p2 in your directory
 cse109.121 and copying the file tree.cc. Start your work by editing the
 file tree.cc. I will soon give more instructions on a different way to
 compile tree.cc. For the moment, our old approach will do.  As usual
 compile tree.cc with the -Wall and -Werror options.


 When you are ready to submit your work, create the file "DONE" by executing
 the command "touch DONE".

 Notes: 1. Your files should have good documentation.  They should have
         identifying information at the top, e.g., your name, the course,
         the assignment number.  The class declaration should be documented
         with comments at the top which explain each class and its purpose.
         The role of each data member should be explained.  Each member
         method should be explained (e.g., by stating pre- and
         post-conditions and by stating the overall algorithm).  Hard
         to understand sections of code should be explained.  This means
         that most of the documentation goes with the class declarations.
        2. IT IS IMPORTANT TO NOTE THAT THE FILE tree.cc ASSUMES THAT YOU
         HAVE THE CLASS Word AVAILABLE IN THE FILE  word.h. If your class
         Word functions well, rename the file word.cc as word.h and comment
         out the function main(). Then, when you compile tree.cc, the file
         word.h will be included before the file tree.cc is compiled with
         the command
            g++ -Wall -Werror tree.cc
         BUT, what if your class Word does not work well. Then copy the
         files /proj/csc109/p2/word.h and /proj/csc109/p2/word.o into your
         directory. The file word.h has only the declaration for class Word.
         The file word.o has the compiled version of my word.cc (which I am
         trying to keep secret). Compile the file tree.cc with the command
             g++ -Wall -Werror tree.cc word.o
         (which has the effect of compiling tree.cc and linking its code
         with the code in word.o to create a running program).

IN THE SYLLABUS READ THE STATEMENT ABOUT UNFAIR COLLABORATION AND AVOID
UNFAIR COLLABORATION