The purpose of this question is to give a small amout of experience in
writing Java, and in particular to use the inner class mechanism and types
and interfaces. It isn't intended to require that you understand the Java
class library in detail (so in particular just write the BinaryTree class
from scratch).
Write and test a class BinaryTree in Java
that implements sorted binary trees. (Use whichever Java compiler is
convenient.)
The nodes in the tree should hold objects that implement the
Comparable interface (this includes String, Integer, Float, etc).
Your binary tree should provide the following methods:
- public void insert(Comparable x) -- insert x
into the tree
- public Iterator iterator() -- return an iterator,
which will perform an inorder traversal of the tree
- a constructor
You don't need to implement delete. Also, you don't need to worry
about synchronization issues (inserting a new element into a tree while
there is an iterator in use for that tree). Finally, to keep things
simple, you don't need to have your BinaryTree implement the
Collection interface. (If you were providing this as part of a
Java library for practical use, this would be the right thing to do
however.)
There are several possible ways of handling the tree traversal method. The
issue is that the iterator must return one value at a time from the
next() method, so you can't just implement the traditional
recursive procedure directly. Pick an technique, and discuss why you chose
that particular technique.
This question concerns abstract types and subtypes, parameterized
types, and the contravariant rule. We have an abstract type
Consumer, parameterized by T, the type of object
that the Consumer consumes. Consumer has a single operation
eat, which takes a single argument of type T and
doesn't return anything.
We also have an abstract type Producer, again parameterized by
T. Producer has a single operation
make, which takes no arguments and returns an object of type
T.
Finally we have an abstract type ProducerConsumer, again
parameterized by T, the type of object that the
ProducerConsumer contains. ProducerConsumer has two
operations: eat and make.
Using the contravariant rule, what is the subtype relation between the
following pairs of types? (The answer to each question would be either
X is a subtype of Y, Y is a subtype
of X, or neither is a subtype of the other.)
- ProducerConsumer[Integer] and ProducerConsumer[Number]
- Consumer[Integer] and Consumer[Number]
- Producer[Integer] and Producer[Number]
- ProducerConsumer[Integer] and Producer[Number]
- ProducerConsumer[Number] and Producer[Integer]
- ProducerConsumer[Integer] and Consumer[Number]
- ProducerConsumer[Number] and Consumer[Integer]