CSC 172
Homework 4

Assigned 11 Oct, due 25 Oct

• Before you start writing code, fill out a Product Plan Estimate form in the PSP package (click on "Input" under "Product Plan Estimates").
  As you go, or when you're done, fill out a time log form in the PSP package (click on "Input" under "Time Management Data").
  Every time you find and fix a defect, record it using the PSP package (click on "Input" under "Defect Removal Data").
• For all your programming assignments, follow the appropriate design recipe. Each method should be documented with examples and the results they should produce (write these before writing the code!); be sure to test the method thoroughly before turning it in.
  Each class, method, and variable should have a well-chosen, meaningful name.
  Each class should have a static void test() method where you put all your standard test cases relevant to this class.
  All javadoc comments (and all comments, for that matter) should be correct and up-to-date; a misleading comment is worse than none at all.
• Design and implement a collection of classes to represent a binary search tree, as in section 14.2 of How to Design Programs. Since we're writing in Java rather than Scheme, we don't have symbols; instead, each non-empty node of our trees will contain a number, a String, and two other binary trees.

  Version 1 (for partial credit): implement binary trees, as described in How to Design Programs. Your collection of classes should provide at least the following methods:

  • One or more constructors (analogous to make-node in HtDP) so a user can build arbitrarily large binary trees;
  • contains, which takes a number and tells whether that number appears in the tree;
  • search, which takes a number and returns the String associated with that number in the tree. If the number is not found, it returns null. (You can check whether something is null by using ==, e.g.

    if (myTree.search(13) == null) ...

  • toString, which prints out a binary tree in a reasonable way. (Hint: this is analogous to the inorder function in HtDP, only it returns a String.)
  • equals, which takes in another binary tree and tells whether it has the same structure, with the same numbers and Strings in the same places.

  Version 2 (for full credit): implement binary search trees as well, which provide at least the following methods:

  • search, which takes a number and returns the String associated with that number in the tree. If the number is not found, it returns null. Note that since you are now working on a binary search tree, this function should examine only a few elements of the tree rather than looking through all of it.
  • insert, which takes a number and returns a new binary search tree with the number inserted in the appropriate place in the old binary search tree. (Hint: this is analogous to create-bst in HtDP.)

  There are a number of different ways to implement this. After implementing binary trees, you could define a binary search tree from it by inheritance (do all the operations on binary trees make sense on binary search trees?). Or you could define a BinarySearchTree class that contains a BinaryTree (using composition rather than inheritance). Or you could modify your BinaryTree collection of classes into a corresponding BinarySearchTree collection of classes. See what you come up with.