CSE 109 Programming Assignment #2   Due: 9 PM Friday 13 March 2009
 [Late collections 9 PM Saturday 15 March, Sunday 16 March]

 This assignment is an exercise in writing a class, in implementing a
 ternary tree, and in writing recursive functions. Write a class Tree
 that has the same functionality as the class Tree that I developed
 in lecture, except that it should use a ternary tree structure in place of
 the binary tree structure (and a Node class practically identical to the
 Node class developed in lecture, except for having three pointers, rather
 than two, and except for storing two keys (and their associated data) rather
 than one).  You should be able to take the program I used to test the class
 Tree, use your class Tree, and get the same output.

 In /proj/csc109/p2 you will find the file testTree.cc which is
 a program that tests out the implementation of the class Tree and (its
 associated class, class Node).  Also, in /proj/csc109/p2 I have stored the
 executable file testTree, which is the compiled version of testTree.cc, using
 the code for class Tree developed in lecture.  The output you get when
 running your p2 should be close to the output obtained when running testTree.
 The program in testTree.cc requires the implementation of the following
 methods (member functions) in the in class Tree.  (Note that I indicate
 methods with (), but this is not meant to suggest how the method should be
 parameterized.)

   1.  The default constructor.
   2.  The copy constructor.
   3.  The destructor, ~Tree()
   4.  The [] operator gives access to the data corresponding to the given
       key in the tree, provided the key is in the tree. otherwise it
       adds that key to the tree, so that the tree maintains the data in
       in ascending order (in an inorder search).
   5.  The []const operator gives access to the data corresponging to the
       given key, provided the key is in the tree, otherwise it crashes
       the program.
   6.  inTree() returns true if and only if the given key is in the tree.
   7.  <<   displays the tree.

 Start this assignment by creating the subdirectory p2 in your subdirectory
 cse109.091 and copying the file /proj/csc109/p2/testTree.cc into
 the file cse109.091/p2/p2.cc. Create a Makefile for compiling p2.  DO NOT
 CHANGE THE CODE OF p2.cc AT ALL. I REPEAT, DO NOT CHANGE THE PROGRAM CODE
 IN ANY WAY OTHER THAN TO ADD THE USUAL (IMPORTANT) DOCUMENTATION (name,
 assignment, program and class purposes, etc.,) ELSE LOSE AT LEAST 20 PTS.
 I will test your classes Tree (and Node) by using the command "make clean"
 to discard all .o files (where you should implement "clean" in your Makefile),
 by replacing your p2.cc with the the file /proj/csc109/p2/testTree.cc, by
 using your Makefile to compile p2.cc (and the code for your classes),
 and then by  running the resulting executable file p2. IT IS IMPORTANT THAT
 YOU COMPILE ALL YOUR .cc FILES WITH THE -Werror  -Wall OPTIONS (E.G.,
 g++ -c -Werror -Wall p2.cc).

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

 Notes: 1. All your files should have good documentation.  Each file should
         have identifying information at the top, e.g., your name, the course,
         the assignment number.  Each class declaration should be documented
         with comments at the top which explain the 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.
        2.  You should have separate .h files and .cc files for the classes
            Node and Tree, for the function check(), if you use it, and for
            p2.cc.
        3.  The files I provide are stored in /proj/csc109/p2.
        4.  I may test your classes with some other programs.
        5.  Each node of a ternary tree has one or two keys and zero, one,
         two, or three children. If it has two keys, the keys are stored in
         ascending order. Numbering the children c0, c1, and c2, and the keys
         k1 and k2, each key has a corresponding datum, the keys in c0 and
         all its descendants are all less than k1, the keys in c1 and all
         its descendants are all greater than k1 and less than k2, and the
         keys in c2 and all its descendants are all greater than k2.  Finally,
         only leaves (nodes with no children) can have fewer than two keys.
         The ternary structure promotes "bushiness" (making it a
         compassionately conservative tree?).  Below is an example

                                    12    113
                                   /    |
                                 2 4  19 99
                                     /  |
                                    13  27

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