All the code is in the dict package. You can compile it from your lab4 directory with javac -g dict/*.java Some test code is provided and can be run with java dict.BinaryTree Familiarize yourself with the fields and methods of the BinaryTree and BinaryTreeNode classes. BinaryTree is an implementation of the Dictionary interface (which you also used in Homework 6) as a binary search tree. Note that BinaryTree uses Comparable objects as keys (since it is an ordered dictionary), whereas in the Dictionary abstract class, keys are declared as plain Objects. Thus you will occasionally need to cast Objects to Comparables. Part I: Finding an Element in a Binary Search Tree (2 points) -------------------------------------------------------------- Complete the implementation of the find() method in dict/BinaryTree.java by filling in the body of findHelper(). find() takes a key as its single parameter, and returns an element associated with that key, or null if there is none. (If there are several elements associated with a key, it doesn't matter which one is returned.) findHelper() helps by recursively finding and returning a node that contains the key (or null if no such node exists). Take a look at insertHelper() for inspiration. find() should run in O(d) time on a tree with depth d. Part II: Removing an Element with a Given Key (2 points) --------------------------------------------------------- Fill in the body of remove() method in BinaryTree.java. remove() takes a key as its single parameter, and removes one item having that key if the tree contains one. (If there are several elements associated with a key, it doesn't matter which one is removed and returned.) remove() returns the same value that find() returns, but should not call find(). However, remove() SHOULD use the findHelper() method you wrote for Part I. remove() should run in O(d) time if the depth of the tree is d. Check-off --------- Show your TA or Lab Assistant the code you have written, and run the test program. You'll receive points for each part that runs correctly. 2 points: If find() works correctly. 1 point: If remove() works for nodes that have no child or one child. 1 point: If remove() works for nodes that have two children.

/* Dictionary.java */

package dict;

/** * An interface for (unordered) dictionary ADTs. * * DO NOT CHANGE THIS FILE. **/

public interface Dictionary {

/** * Returns the number of entries stored in the dictionary. Entries with * the same key (or even the same key and value) each still count as * a separate entry. * @return number of entries in the dictionary. **/

public int size();

/** * Tests if the dictionary is empty. * * @return true if the dictionary has no entries; false otherwise. **/

public boolean isEmpty();

/** * Create a new Entry object referencing the input key and associated value, * and insert the entry into the dictionary. Return a reference to the new * entry. Multiple entries with the same key (or even the same key and * value) can coexist in the dictionary. * * @param key the key by which the entry can be retrieved. * @param value an arbitrary object. * @return an entry containing the key and value. **/

public Entry insert(Object key, Object value);

/** * Search for an entry with the specified key. If such an entry is found, * return it; otherwise return null. If several entries have the specified * key, choose one arbitrarily and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. **/

public Entry find(Object key);

/** * Remove an entry with the specified key. If such an entry is found, * remove it from the table and return it; otherwise return null. * If several entries have the specified key, choose one arbitrarily, then * remove and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. */

public Entry remove(Object key);

/** * Remove all entries from the dictionary. */

public void makeEmpty();

}