CPE 103 


Work with your assigned partner to complete the activity below.
Before you write any code, read the directions and write a test plan (what automated and manual tests you will create). Draw the tree you will create, the data to be input (in order), and show the exact program output you expect.

Implement the test plan you wrote as a test driver to demonstrate that all six methods perform correctly.   You may write a local main, but a JUnit test is recommended.  Compile your test driver and run it.  It should compile without error, and when executed it should report that the tests fail.


We will be enhancing Weiss's BinarySearchTree implementation.
Download:

• DuplicateItemException.java
• BinaryNode.java
• BinarySearchTree.java
• ItemNotFoundException.java

In the class header comment for BinarySearchTree include separate @author tags for each student.

Implement the following six methods in your class.  The search() and traverse() methods must be implemented recursively. search() must not call find().

   /** See if the tree contains a given item.
    * @param target the item to search for
    * @return true if the item is in the tree
    */
   public boolean contains(AnyType target)

    /** Recursively search the tree for the target */
   private boolean search(BinaryNode<AnyType> curr, AnyType target)

   /** Show an ordered list of the items in the tree,
    * one item per line.     */
   public void list()
        
   /** Recursive in-order traversal of the tree, printing each node */
   private void traverseInOrder(BinaryNode<AnyType> curr)

   /** Print a formatted display of the tree.  */
   public void print()

   /** Recursive pre-order traversal of the tree, printing each node
    * indented an amount corresponding to its level in the tree.
    */
   private void traversePreOrder(BinaryNode<AnyType> curr, int indent)
        

The formatted display uses indenting to show nodes on the same level at a consistent level of indentation, and periods where no child exists.
For example, the tree in this diagram  would print like this:

   E
      D
         .
         .
      N
         K
            F
               .
               H
                  .
                  .
            L
               .
               .
         S
            .
            W
               .
               .