CIT 594, Seventh Assignment: Animals!
Spring 2002, David Matuszek

Purposes of this assignment:

Your first task: Design and implement an ADT for binary trees.

A binary tree is either empty, or else is composed of nodes. One special node, called the root node, is considered to be the "starting point" of the binary tree. Each node contains some kind of data, and in addition may have zero, one, or two children. The children (when they exist) are referred to as the left child and the right child. Every node in the binary tree, except the root node, is either the left child or the right child of one other node. There is a single unique path between the root node and any other node in the binary tree. See Section 10.1 of your textbook for a more detailed explanation of binary trees.

Java does not provide a binary tree class. Your textbook describes a highly specialized kind, the binary search tree, but this is not a good starting point for your ADT.

Your binary tree ADT should provide all that is necessary for creating and manipulating the structure of a binary tree; that is, the relationships between the various nodes in the tree. It should provide a means of accessing and changing the content (data) of individual nodes the binary tree, but beyond that it should know nothing about what the content represents or how it is used. In other words, your ADT should be as general as you can make it, and definitely not tailored to the remainder of the assignment.

You will need to provide constructors, transformers, and accessors. Probably you will only want mutative transformers, not applicative ones. See Section 5.3 of your textbook, on Abstract Data Type Design, for more information.

Although not required for the Animals game, each node in your binary tree should also contain a reference to its parent, as well as to its left and right children. This extra reference may be useful in a later assignment involving binary trees. Also, there really isn't any need for a separate "header" class, since a binary tree can be represented by its root node (or null, if the tree is empty); but you can have a separate header class if you want one.

Document your binary trees properly, using javadoc. You should generate and include the javadoc-generated documentation along with your project; don't just insert the comments into your source code.

Finally, do unit testing. Provide a public static void main(String args[]) method that tests all your constructors and methods, and prints its results. The output should be in a form that someone unfamiliar with your program can examine and determine whether the binary tree class has passed its unit tests.

Your second task: Write an "Animals" game.

"Animals" is a classic computer game. The user thinks of an animal, and the computer asks a series of binary (yes/no) questions in an attempt to guess the user's animal. A typical interaction with the (old, text-only version of the) game goes something like this:

Computer: Think of an animal. Hit "Return" when ready.
User: (Hits the Return key).
Computer: Does it live in the water?
User: Yes.
Computer: Is it green?
User: No.
Computer: OK, I've got it. Is the animal you're thinking of a whale?
User: No.
Computer: What was your animal?
User: A seal.
Computer: What question would you ask to distinguish between a whale and a seal?
User: Is it very large?
Computer: What would the answer be for a seal?
User: No.
Computer: Thanks, I'll remember that. Would you like to play again?

After this, the computer does remember the description of a seal, and can use it in subsequent games. You can probably see how to use a binary tree to store the various questions, with animals at the leaves. A binary tree used in this way is usually called a decision tree.

I'll place a few constraints on your program, but beyond that, it's up to you to figure out exactly how to do the assignment. Here are the constraints:

You may wish to review my CIT 591 lectures on javadoc and on Java I/O and serialization.

Here are some decisions you have to make:

Your GUI should be self-explanatory. Remember, we have to grade about 60 of these programs, so we don't want to spend a lot of time figuring out how to use your program. Keep the operation of your program simple and obvious, and don't ask us to do anything (like finding the data file) that your program can do by itself.

Due date:

This assignment is due by midnight, Thursday, March 7. Do all your work in a single folder (directory), jar that directory, and submit it via Blackboard.