CIT 594, Eighth Assignment: Animals! revisited
Spring 2002, David Matuszek

Purpose of this assignment:

Your task: Improve the Animals! game

As the proud implementer of the Animals! game, you would like to show it off to your friends. Unfortunately, some people who have used it really don't know much about animals, and they have put in some things that are just wrong. You know better, of course. For example, you know that a whale is a kind of mammal, not a kind of fish. However, the program now thinks that a whale is a fish, and you are embarrassed to show the program any more.

Your job is to improve the Animals! game by allowing it to hold a conversation something like this:

Computer: Think of an animal. Hit "Return" when ready.
. . .
Computer: OK, I've got it. Is the animal you're thinking of a seal?
User: No.
Computer: What was your animal?
User: A whale.
Computer: I thought I already knew about a whale.
        Before, in answer to the question "Is it a kind of fish?"
        I was told the answer was "yes", but you said "no".
        Which answer is correct?
User: No.
Computer:
OK, I'll have to fix that.
         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?

How does the program recognize that it already knows the animal "whale"? You could, of course, search the entire binary tree every time, but that's inefficient. Instead, use a Hashtable or a HashMap. Each time you add an animal to the binary tree, also add it to the map. The key is the name of the animal, and the value is the node in the binary tree that contains that animal. So when someone tells you that the new animal is "whale", look in your map to see if you already have a whale--if you do, there's a problem. Looking it up in the map is very efficient--O(1).

Of course, any time you change a leaf of the binary tree, you have to make any necessary changes in the map.

How does the program figure out what question was answered incorrectly? This is going to take a little work. However, you have two nodes to start from: the program's guess (the leaf node containing "seal"), and the leaf node that contains the correct animal (the leaf node containing "whale"). You can find the latter node easily from your Hashtable or HashMap. The nearest common ancestor of these two nodes is the node containing the question that was answered incorrectly.

A possible part of the tree. The circles represent nodes containing other questions and animals that we don't care about at the moment.

The parent links will probably come in handy for discovering this common ancestor. You should not have to search the entire binary tree, just the ancestors of the two leaf nodes ("whale" and "seal" in the example).

What do you need to do if the original answer was correct? Nothing. Well, say something to the user, but don't change the binary tree in any way, since it is already correct.

What do you need to do if the original answer was wrong? First, you have to remove the original leaf node ("whale", in this example). This leaves you with a question (the black node in the above picture) that you no longer want, because you only have one subtree ("shark") below it. Remove the question, and replace it with the good subtree (the leaf containing "shark" in this example, but it might be a subtree containing many nodes).

Second, you have to put the animal in the (new) correct place in the binary tree, and for that you need a question that distinguishes "whale" from "seal". This is code that you have already written for the previous assignment.

Here is the result of modifying the binary tree.

The constraints on your program are the same as last time, except that you must generate javadoc for all methods, public and private. The Forté FAQ and the Using javadoc from within Forté pages have been updated with information on how to do this.

Possible extra credit program:

In addition to the above (required) program, you might write another program to edit the Animals! binary tree directly. This would not use the above question-answer style interface, but would present the binary tree directly, as something you would load in, edit, and save again. The program would be something that you would use to do things like fix typos and misspellings in questions, and maybe completely rearrange the tree; but the program would be a tool, and probably not something you would show off to your friends.

I suspect that the Swing JTree component is the best tool for an editor like this, but JTree is a very complex component and one that I have never used myself (yet!), so that's just a guess.

Note that there is one restriction on the Animals! binary tree that is not a restriction on binary trees in general: In the Animals! binary tree, no node is permitted to have only one child--it either has two children, or is a leaf. It's up to you whether to implement this restriction in your binary tree editor. (Ideally, this should be a checkbox in a preferences panel.)

Using the program should be fairly intuitive (that is, easy to figure out without reading an instruction manual), but you can supply instructions where needed.

Designing this program and making it general enough is not likely to be easy. If you do a really good job you might earn as much as an extra 100 points--but not more than you earn on the required assignment (Assignment 8). This limit is to encourage you to do the assigned work before you try the extra credit work. So if you do try to do this extra credit program,

Due date:

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