Start this assignment by writing a class to represent a node in a binary tree: BTNode.java. The skeleton of this class is given below:
public class BTNode implements java.io.Serializable
{
private String element; // element
associated with node
private BTNode parent; // parent of node
private BTNode left, right; // children
of node
/**
* Constructs a tree node with the given
String as an element
* and null children and
parent.
*/
public BTNode(String value)
/**
* Returns reference to left subtree of
current node
*/
public BTNode getLeft()
/**
* Returns reference to right subtree of
current node
*/
public BTNode getRight()
/**
* Returns reference to parent of this
node
*/
public BTNode getParent()
/**
* Update the left subtree of this node
to be newLeft. Parent of newLeft
* should be updated consistently. Old
left should have parent updated to null.
*/
public void setLeft(BTNode newLeft)
/**
* Update the right subtree of this node
to be newRight. Parent of newRight
* should be updated consistently. Old
right should have parent updated to null.
*/
public void setRight(BTNode newRight)
/**
* Update the parent of this node to be
newParent
*/
public void setParent(BTNode newParent)
/**
* Returns the number of descendants of
this node
*/
public int size()
/**
* Returns height of node in
tree. Height is maximum path length to
* descendant leaf
*/
public int height()
/**
* Returns true if tree is empty.
*/
public boolean isEmpty()
/**
* return true if current node has no
children
*/
public boolean isLeaf()
/**
* return true if this node is a left
child
*/
public boolean isLeftChild()
/**
* Determine if this node is a right child
*/
public boolean isRightChild()
/**
* Returns element associated with this
node
*/
public String getElement()
/**
* Sets element associated with this node
*/
public void setElement(String value)
}
Next,
write a class to represent a binary tree called DecisionTree.java. This
class should extend the ArrayList class, specifically,
ArrayList<BTNode>. The root of the DecisionTree will
always be at
position 0, so the getRoot method just returns the element at position
0 as shown below. The skeleton of this class is given below:
import java.util.*;
public class DecisionTree extends ArrayList<BTNode> {
/**
* Returns height of root node.
*/
public int height()
/**
* Returns reference to root node.
*/
public BTNode
getRoot() {
return
this.get(0);
}
/**
* Print all the items in
this tree, starting at the given BTNode,
* using a preorder
traversal. Skip null nodes.
*/
public void
printAll (BTNode v)
}
You can think of the branches in the initial tree as being labeled like this:
Are you a mammal?
/\
Y/ \N
/ \
Are you bigger Do you live
than a domestic cat? underwater?
/\ /\
Y/ \N Y/ \N
/ \ / \
Kangaroo Mouse Trout Robin
To begin each round of the game, you think of an animal. For example, suppose you are thinking of a raccoon. The program reads the binary input file (specified on the command line as args[0]) to create the initial decision tree. The first question asked by the program, if you use the given file input.txt to create your tree, will be "Are you a mammal?", to which you answer "Y" (for yes). Then the program asks, "Are you bigger than a domestic cat?", and you answer "Y" again. The program will now have its current reference set to the leftmost leaf on the initial decision tree, so it is ready to make a guess. It asks "Are you a Kangaroo?" and you answer "N".
At this point the program outputs, "I give up, what are you?". You type "Raccoon". The program outputs, "Please type a question that can be used to distinguish the Kangaroo from the Raccoon". You type something like, "Are you a marsupial?". The computer outputs, "Are you a marsupial, Raccoon?", and you type "N" (implicitly making the answer to the question "Y" for a Kangaroo).
At this point, your program should modify the decision tree by making Kangaroo the left child and Raccoon the right child of the current node and replacing the contents of the current node with the question "Are you a marsupial?." After the learning phase, the computer prompts you to see if you want to play another round.
> java AnimalGame
Welcome to the Animal Guessing Game!
Please think of an animal.
I will ask some yes/no questions to try to figure
out what you are.
Please enter a file name containing a decision tree.
[tree.bin ]
Are you a mammal?[Y or N] :
[Y ]
Are you bigger than a domestic cat?[Y or N] :
[Y ]
My guess is Kangaroo. Am I right?[Y or N] :
[N ]
I give up. What are you?
[Whale ]
Please type a yes/no question that will distinguish the
Whale from the Kangaroo.
Your question:
[Do you live in the ocean?]
Do you live in the ocean, Whale?
Please answer: [Y or N] :
[Y ]
Shall we play again?[Y or N] :
[Y ]
Are you a mammal?[Y or N] :
[N ]
Do you live underwater?[Y or N] :
[Y ]
My guess is Trout. Am I right?[Y or N] :
[N ]
I give up. What are you?
[Shark ]
Please type a yes/no question that will distinguish the
Shark from the Trout.
Your question:
[Do you eat people?]
Do you eat people, Shark?
Please answer: [Y or N] :
[Y ]
Shall we play again?[Y or N] :
[N ]
Thanks for teaching me a thing or two.
Please enter a file name to store your decision tree.
[tree2.bin ]
Are you a mammal?Each round of the game in which an incorrect guess is made by the computer will result in two new BTNodes (the new animal and the animal guessed) being added to the tree and a change in the contents and the children of the BTNode used as a guess in that round by the computer. The new question will be added to an internal node and the original and new animals will be added as the leaves of that internal node. Each round of the game in which a correct decision is made will result in no new BTNodes being added to the tree. Each round restarts the guessing game at the root.
/\
Y/ \N
/ \
Are you bigger Do you live
than a domestic cat? underwater?
/\ /\
Y/ \N Y/ \N
/ \ / \
Do you live Mouse Do you eat Robin
in the ocean? people?
/\ /\
Y/ \N Y/ \N
/ \ / \
Whale Kangaroo Shark Trout
1. Call a method to print the instructions and welcome message shown in
the sample execution above.
2. Call a method to read the initial binary decision tree from a file name
specified by the user.
3. Repeat the following as long as the user wants:
A. Play one round of the game by asking the user the question at
the root of the tree and following the reference to the right
or left child, depending on the user's response to the question.
As long as the current node is an internal node, keep following
references until the current node is a leaf, in which case the
program should make a guess and ask if it is right, with 2
possible outcomes:
i. The computer guesses correctly. Go to part B
ii. The computer guesses incorrectly. Then
- ask the user for a question to distinguish
the new animal from the animal guessed
- ask the user if the answer to the question for
the new animal is "yes" or "no"
- create new BTNodes for the guessed and the new animal
- replace the element in the guessed animal node with
the new question
- if the answer to the new question is "yes" for
the new animal (and therefore is "no" for the guessed animal),
make the new animal the left child of the question and the
guessed animal the right child of the question.
Otherwise, make the new animal BTNode the right
child and the guessed animal BTNode the left child
of the question BTNode.
B. Ask the user if they want to play again. If yes, go to
step 3A, and if no, go to step 4.
4. At this point, the user has indicated that they do not want to play
another round. Print a suitable closing message and write the contents
of the DecisionTree object to a binary output file.
Remember to
follow the maxims that each method should accomplish a separate task
and
that the length of each method should ideally be shorter than 60 lines
of text. You
will be asking the user for yes/no answers at more than one place in
this program, so it would be a good idea to create a method to query
the user that takes a String for the prompt and returns a boolean,
depending on the reply to the query.