©2005 Felleisen, Proulx, et. al.
Compare the two classes in figure 1. A Set
is a
collection of integers that contains each element at most once. A
Bag
is also a collecion of integers, but an integer may
show up many times in a bag.
Your tasks are:
// a list of integers interface ILin { int howMany(int i); }The constructors are MTin for the empty list and Cin for constructing a list from an integer and an existing list.
Develop examples of Set
s and
Bag
s.
Develop functional examples for all methods in Set
and Bag
. Turn them into tests.
The two classes clearly share a number of similarities. Create a union and lift the commonalities into an abstract superclass. Name the union interface ICollection. Don't forget to re-run your test suite at each step.
Develop the method size, which determines how many elements a
Bag
or a Set
contain. If a Bag contains an
integer n times, it contributes n to size.
Develop the method rem, which removes a given integer. If a
Bag
contains an integer more than once, only one of them
is removed.
Most object-oriented languages provide libraries like
Set
, and Bag
. Find the documentation for
your local Java implementation and read up on
Set
s.
// Figure 1: // a set of integers: // contains an integer at most once> class Set { ILin elements; Set(ILin elements) { this.elements = elements; } // add i to this set unless it is already in there Set add(int i) { if (this.in(i)) return this; else return new Set(new Cin(i,this.elements)); } // is i a member of this set? boolean in(int i) { return this.elements.howMany(i) > 0; } } // a bag of integers class Bag { ILin elements; Bag(ILin elements) { this.elements = elements; } // add i to this bag Bag add(int i) { return new Bag(new Cin(i,this.elements)); } // is i a member of this bag? boolean in(int i) { return this.elements.howMany(i) > 0; } // how often is i a member of this bag? int howMany(int i) { return this.elements.howMany(i); } }
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