©2005 Felleisen, Proulx, et. al.

We have the following data definition:

A *Binary Search Tree* is one of

*Empty Tree*a

*Node*

A *Node* consists of

`data`

of the type`String`

,`left`

*Binary Search Tree*,`right`

*Binary Search Tree*.

Additionally, every `Node`

has the property that all data in
the `left`

subtree contains strings that appear in the dictionary
before the data in the `Node`

, and all data in the
`right`

subtree are strings that appear in
the dictionary after the `data`

in this node. The string that
is identical to the field `data`

can be in
either the `left`

or in the `right`

subtree -- it is
not important.

The following are examples of such trees:

ppp mmm ------ -------- / \ / \ ggg ttt ddd rrr ----- ----- ----- ----- / \ / \ / \ / \ bbb * sss * aaa kkk * xxx ----- ----- ----- ----- ----- / \ / \ / \ / \ / \ * * * * * * * * * * Tree-1 Tree-2

Your task is to design classes that represent this data as Java
classes, and to design several methods to manipulate this data. You
will also need an auxilliary classes that represent a list of
`String`

s. You may read more about binary search tree in HtDP.

Design the classes that represent binary search trees of
`String`

s. Make examples of data.

Design the method `same`

that determines whether two binary
search trees are the same, i.e. they have the same structure and
contain the same `String`

s.

Design the method `insert`

that insert a `String`

into
a binary search tree, preserving the tree property stated
earlier.

Java provides the following method for `String`

comparison:

// compare this String with that String lexicographically // return <0 --- if 'this' is before 'that' // return 0 --- if 'this' is the same String as 'that' // return >0 --- if 'this' is after 'that' int compareTo(String that) ...

If you do not understand how to do it, try some examples by hand, or read about the problem in HtDP.

Design the classes that represent a list of `String`

s. Add the
method `sort`

that sorts the list in lexicographical order. Add
the method `same`

that determines whether two lists contain the
same `String`

s in the same order. You should just modify your
solutions to the previous homework.

Design the method `inorder`

that produces a list of
`String`

s that appear in the nodes of this tree, ordered so
that all strings in the left subtree appear in the list before the
data in the root node, and all strings in the right subtree appear in
the list after the data in the root node.

For example, our two examples would produce the lists in the following order:

Tree-1: bbb ggg ppp sss ttt Tree-2: aaa ddd kkk mmm rrr xxx

The method consumes a list of `String`

s, initially empty, that
represents the list of strings that come after all the nodes in this
subtree have been entered into the list. So, for our `Tree-2`,
in the `Node`

`ddd`, the given list of strings will contain
(`mmm rrr xxx`). The nodes in this subtree, `ddd`,
`aaa`, and `kkk`, still have to be added to the list. It
is clear, that when we start at the node `mmm`, there is
nothing in the list.

Again, make examples until you understand the problem. Follow the design recipe!

Design the method `contains`

for both, the classes that
represent the binary search trees, and the classes that represent lists
of `Strings`

. The method determines whether the given
`String`

appears in the tree or list repsectively.

Explore the power of the methods you designed through the following examples:

insert the same items into a binary search tree several times in different order, then produce the result from the

`inorder`

method and check that they are the same.insert the same items into a list of

`String`

s, again several times in a different order, and sort these lists.design a comparison between a binary search tree and a list of

`String`

s to determine whether they contain the same`String`

s.design the method

`sameData`

for the classes that represent binary

search trees, that determines whether two trees contain the same`String`

s, not necessarily organized the same way. For example, any pair of the following three trees would pass this test:bb cc aa / \ / \ / \ aa cc aa * * bb / \ / \ / \ / \ * * * * * bb * cc / \ / \ * * * *

design the method

`buildTree`

for the classes that represent

binary search trees that consumes a list of`String`

s and produces a binary search tree, with all`String`

s in the list inserted in the tree. Verify that you produced the correct list by comparing the result of invoking the`inorder`

method with the given list in sorted order.

Design the method `delete`

that deletes the given
`String`

from the binary search tree, while preserving the
binary search tree property. If the tree does not contain the
`String`

, the method just returns the original tree.

The height of the binary tree is the longest path from the root
`Node`

to an `Empty Tree`

. So
for example, `Tree-1` and `Tree-2` in the first set of
examples both have height 3, while the first tree in the **Problem
5.7** has height 2.

What is the smallest and what is the greatest height of a binary serch tree with 63 nodes?, with 31 nodes?

Make examples of the binary search tree of minimum and maximum height with 15 nodes.

Show all possible binary search trees that contain the following

`Strings`

and no others:`aa bb cc dd`

HTML conversion by TeX2page 2004-09-11