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.