You will need to revise the animal-guessing program so that the initial knowledge tree is obtained by reading information from a file. Also, when program ends, the knowledge tree at that point is written to the same file. The file has data in a specific format - nodes of the knowledge tree are listed one per line using pre-order traversal. If a node contains a question (is a nonleaf node), then the question is preceeded by "?" in the line. If a node contains an animal (is a leaf node), then the line contains just the name of the animal. File textbookAnimals contains the knowledge tree from p.471 represented in this format. Such format makes it easy to read the file and set the initial tree, and to write the knowledge tree to the file using pre-order traversal. You need to do the following: 1. Add recursive method printLeaves to the generic BTNode class: public void printLeaves() The method should output all the leaves in the binary tree with this node as its root. 2. Add method readFromFile to animal guessing program: public static BTNode < String> readFromFile(Scanner input) The method has one parameter (input) - a stream of the class Scanner which is connected to a text file for reading. The method must be recursive. The method should build a tree which representation starts on the next line in input and return the root of the built tree. Note: once you read a line you may check whether this line is a question or an animal by checking the first character of the line. 3. Add method writeToFile to animal guessing program: public static void writeToFile(PrintWriter output, BTNode < String> root) The method has two parameters. The first parameter (output) is a stream of the class PrintWriter which is connected to a text file for writing. The second paramater (root) is a root of a knowledge tree. The method must be recursive. It should write a tree with root root to output using the data format described above. 4. Modify animal-guessing program (file AnimalGuess.java) so that o it prompts the user to enter file name, o instead of beginningTree method it uses readFromFile method to build the initial knowledge tree from the file user specified, o after the user is finished playing it uses method printLeaves to output a list of animals it knows, and o uses method writeToFile to write modified knowledge tree to the same file.Sample output of the program is given below. You may assume that file is always in the correct format. You do not need to check whether file is in correct format or not.

*****What you need: ***************************************************************

Opening a Text File for Reading with Scanner

Example:

import java.util.Scanner; import java.io.FileInputStream; import java.io.FileNotFoundException; ... Scanner input = null; try { input = new Scanner(new FileInputStream(filename)); } catch(FileNotFoundException fnfe) { System.out.println("File " + filename + " was not found or could not be opened."); System.exit(0); } 

*************************************************************

Opening a Text File for Writing Output

You create a stream of the class PrintWriter and connect it to a text file for writing. An object of the class PrintWriter has the methods print and println.

Example:

import java.io.PrintWriter; import java.io.FileOutputStream; import java.io.FileNotFoundException; ... String filename; ... PrintWriter output = null; try { output = new PrintWriter(new FileOutputStream(filename)); } catch(FileNotFoundException fnfe) { System.out.println("Error opening output file " + filename); System.exit(0); } ... output.close(); 

*************************************************************************

// File: BTNode.java from the package edu.colorado.nodes // Complete documentation is available from the BTNode link in: // http://www.cs.colorado.edu/~main/docs/ //package edu.colorado.nodes; /****************************************************************************** * A BTNode< provides a node for a binary tree. Each node * contains a piece of data (which is a reference to an E object) and references * to a left and right child. The references to children may be null to indicate * that there is no child. The reference stored in a node can also be null. * *

Limitations:

* Beyond Int.MAX_VALUE elements, treeSize, is * wrong. * *

Java Source Code for this class:

* * http://www.cs.colorado.edu/~main/edu/colorado/nodes/BTNode.java * * @author Michael Main * (main@colorado.edu) * * @version * Jul 22, 2005 ******************************************************************************/ public class BTNode { // Invariant of the BTNode class: // 1. Each node has one reference to an E Object, stored in the instance // variable data. // 2. The instance variables left and right are references to the node's // left and right children. private E data; private BTNode left, right; /** * Initialize a BTNode with a specified initial data and links * children. Note that a child link may be the null reference, * which indicates that the new node does not have that child. * @param initialData * the initial data of this new node * @param initialLeft * a reference to the left child of this new node--this reference may be null * to indicate that there is no node after this new node. * @param initialRight * a reference to the right child of this new node--this reference may be null * to indicate that there is no node after this new node. *

Postcondition:

* This node contains the specified data and links to its children. **/ public BTNode(E initialData, BTNode initialLeft, BTNode initialRight) { data = initialData; left = initialLeft; right = initialRight; } /** * Accessor method to get the data from this node. * @param - none * @return * the data from this node **/ public E getData( ) { return data; } /** * Accessor method to get a reference to the left child of this node. * @param - none * @return * a reference to the left child of this node (or the null reference if there * is no left child) **/ public BTNode getLeft( ) { return left; } /** * Accessor method to get the data from the leftmost node of the tree below * this node. * @param - none * @return * the data from the deepest node that can be reached from this node by * following left links. **/ public E getLeftmostData( ) { if (left == null) return data; else return left.getLeftmostData( ); } /** * Accessor method to get a reference to the right child of this node. * @param - none * @return * a reference to the right child of this node (or the null reference if there * is no right child) **/ public BTNode getRight( ) { return right; } /** * Accessor method to get the data from the rightmost node of the tree below * this node. * @param - none * @return * the data from the deepest node that can be reached from this node by * following right links. **/ public E getRightmostData( ) { if (left == null) return data; else return left.getRightmostData( ); } /** * Uses an inorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none *

Postcondition:

* The data of this node and all its descendants have been writeen by * System.out.println( ) using an inorder traversal. **/ public void inorderPrint( ) { if (left != null) left.inorderPrint( ); System.out.println(data); if (right != null) right.inorderPrint( ); } /** * Accessor method to determine whether a node is a leaf. * @param - none * @return * true (if this node is a leaf) or * false (if this node is not a leaf. **/ public boolean isLeaf( ) { return (left == null) && (right == null); } /** * Uses a preorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none *

Postcondition:

* The data of this node and all its descendants have been writeen by * System.out.println( ) using a preorder traversal. **/ public void preorderPrint( ) { System.out.println(data); if (left != null) left.preorderPrint( ); if (right != null) right.preorderPrint( ); } /** * Uses a postorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none *

Postcondition:

* The data of this node and all its descendants have been writeen by * System.out.println( ) using a postorder traversal. **/ public void postorderPrint( ) { if (left != null) left.postorderPrint( ); if (right != null) right.postorderPrint( ); System.out.println(data); } /** * Uses an inorder traversal to print the data from each node at or below * this node of the binary tree, with indentations to indicate the depth * of each node. * @param depth * the depth of this node (with 0 for root, 1 for the root's * children, and so on)( *

Precondition:

* depth is the depth of this node. *

Postcondition:

* The data of this node and all its descendants have been writeen by * System.out.println( ) using an inorder traversal. * The indentation of each line of data is four times its depth in the * tree. A dash "--" is printed at any place where a child has no * sibling. **/ public void print(int depth) { int i; // Print the indentation and the data from the current node: for (i = 1; i <= depth; i++) System.out.print(" "); System.out.println(data); // Print the left subtree (or a dash if there is a right child and no left child) if (left != null) left.print(depth+1); else if (right != null) { for (i = 1; i <= depth+1; i++) System.out.print(" "); System.out.println("--"); } // Print the right subtree (or a dash if there is a left child and no left child) if (right != null) right.print(depth+1); else if (left != null) { for (i = 1; i <= depth+1; i++) System.out.print(" "); System.out.println("--"); } } /** * Remove the leftmost most node of the tree with this node as its root. * @param - none *

Postcondition:

* The tree starting at this node has had its leftmost node removed (i.e., * the deepest node that can be reached by following left links). The * return value is a reference to the root of the new (smaller) tree. * This return value could be null if the original tree had only one * node (since that one node has now been removed). **/ public BTNode removeLeftmost( ) { if (left == null) return right; else { left = left.removeLeftmost( ); return this; } } /** * Remove the rightmost most node of the tree with this node as its root. * @param - none *

Postcondition:

* The tree starting at this node has had its rightmost node removed (i.e., * the deepest node that can be reached by following right links). The * return value is a reference to the root of the new (smaller) tree. * This return value could be null if the original tree had only one * node (since that one node has now been removed). **/ public BTNode removeRightmost( ) { if (right == null) return left; else { right = right.removeRightmost( ); return this; } } /** * Modification method to set the data in this node. * @param newData * the new data to place in this node *

Postcondition:

* The data of this node has been set to newData. **/ public void setData(E newData) { data = newData; } /** * Modification method to set the link to the left child of this node. * @param newLeft * a reference to the node that should appear as the left child of this node * (or the null reference if there is no left child for this node) *

Postcondition:

* The link to the left child of this node has been set to newLeft. * Any other node (that used to be the left child) is no longer connected to * this node. **/ public void setLeft(BTNode newLeft) { left = newLeft; } /** * Modification method to set the link to the right child of this node. * @param newLeft * a reference to the node that should appear as the right child of this node * (or the null reference if there is no right child for this node) *

Postcondition:

* The link to the right child of this node has been set to newRight. * Any other node (that used to be the right child) is no longer connected to * this node. **/ public void setRight(BTNode newRight) { right = newRight; } /** * Copy a binary tree. * @param source * a reference to the root of a binary tree that will be copied (which may be * an empty tree where source is null) * @return * The method has made a copy of the binary tree starting at * source. The return value is a reference to the root of the copy. * @exception OutOfMemoryError * Indicates that there is insufficient memory for the new tree. **/ public static BTNode treeCopy(BTNode source) { BTNode leftCopy, rightCopy; if (source == null) return null; else { leftCopy = treeCopy(source.left); rightCopy = treeCopy(source.right); return new BTNode(source.data, leftCopy, rightCopy); } } /** * Count the number of nodes in a binary tree. * @param root * a reference to the root of a binary tree (which may be * an empty tree where source is null) * @return * the number of nodes in the binary tree *

Note:

* A wrong answer occurs for trees larger than * INT.MAX_VALUE. **/ public static long treeSize(BTNode root) { if (root == null) return 0; else return 1 + treeSize(root.left) + treeSize(root.right); } }

***************************************************************************************

// FILE: AnimalGuess.java // This animal-guessing program illustrates the use of the binary tree node class. //import edu.colorado.nodes.BTNode; import java.util.Scanner; /****************************************************************************** * The AnimalGuess Java application illustrates the use of * the binary tree node class is a small animal-guessing game. * *

Java Source Code for this class:

* * http://www.cs.colorado.edu/~main/applications/Animals.java * * * @author Michael Main * (main@colorado.edu) * * @version * Jul 22, 2005 ******************************************************************************/ public class AnimalGuess { private static Scanner stdin = new Scanner(System.in); /** * The main method prints instructions and repeatedly plays the * animal-guessing game. As the game is played, the taxonomy tree * grows by learning new animals. The String argument * (args) is not used in this implementation. **/ public static void main(String[ ] args) { BTNode root; instruct( ); root = beginningTree( ); do play(root); while (query("Shall we play again?")); System.out.println("Thanks for teaching me a thing or two."); } /** * Print instructions for the animal-guessing game. **/ public static void instruct( ) { System.out.println("Please think of an animal."); System.out.println("I will ask some yes/no questions to try to figure"); System.out.println("out what you are."); } /** * Play one round of the animal guessing game. * @param current * a reference to the root node of a binary taxonomy tree that will be * used to play the game. *

Postcondition:

* The method has played one round of the game, and possibly * added new information about a new animal. * @exception java.lang.OutOfMemoryError * Indicates that there is insufficient memory to add new * information to the tree. **/ public static void play(BTNode current) { while (!current.isLeaf( )) { if (query(current.getData( ))) current = current.getLeft( ); else current = current.getRight( ); } System.out.print("My guess is " + current.getData( ) + ". "); if (!query("Am I right?")) learn(current); else System.out.println("I knew it all along!"); } /** * Construct a small taxonomy tree with four animals. * @param - none * @return * a reference to the root of a taxonomy tree with the animals: * kangaroo, mouse, trout, robin. * @exception OutOfMemoryError * Indicates that there is insufficient memory to create the tree. **/ public static BTNode beginningTree( ) { BTNode root; BTNode child; final String ROOT_QUESTION = "Are you a mammal?"; final String LEFT_QUESTION = "Are you bigger than a cat?"; final String RIGHT_QUESTION = "Do you live underwater?"; final String ANIMAL1 = "Kangaroo"; final String ANIMAL2 = "Mouse"; final String ANIMAL3 = "Trout"; final String ANIMAL4 = "Robin"; // Create the root node with the question Are you a mammal? root = new BTNode(ROOT_QUESTION, null, null); // Create and attach the left subtree. child = new BTNode(LEFT_QUESTION, null, null); child.setLeft(new BTNode(ANIMAL1, null, null)); child.setRight(new BTNode(ANIMAL2, null, null)); root.setLeft(child); // Create and attach the right subtree. child = new BTNode(RIGHT_QUESTION, null, null); child.setLeft(new BTNode(ANIMAL3, null, null)); child.setRight(new BTNode(ANIMAL4, null, null)); root.setRight(child); return root; } /** * Elicits information from the user to improve a binary taxonomy tree. * @param current * a reference to a leaf node of a binary taxonomy tree *

Precondition:

* current is a reference to a leaf in a binary * taxonomy tree *

Postcondition:

* Information has been elicited from the user, and the tree has * been improved. * @exception OutOfMemoryError * Indicates that there is insufficient memory to add new * information to the tree. **/ public static void learn(BTNode current) // Precondition: current is a reference to a leaf in a taxonomy tree. This // leaf contains a wrong guess that was just made. // Postcondition: Information has been elicited from the user, and the tree // has been improved. { String guessAnimal; // The animal that was just guessed String correctAnimal; // The animal that the user was thinking of String newQuestion; // A question to distinguish the two animals // Set Strings for the guessed animal, correct animal and a new question. guessAnimal = current.getData( ); System.out.println("I give up. What are you? "); correctAnimal = stdin.nextLine( ); System.out.println("Please type a yes/no question that will distinguish a"); System.out.println(correctAnimal + " from a " + guessAnimal + "."); System.out.print("Your question: "); newQuestion = stdin.nextLine( ); // Put the new question in the current node, and add two new children. current.setData(newQuestion); System.out.println("As a " + correctAnimal + ", " + newQuestion); if (query("Please answer")) { current.setLeft(new BTNode(correctAnimal, null, null)); current.setRight(new BTNode(guessAnimal, null, null)); } else { current.setLeft(new BTNode(guessAnimal, null, null)); current.setRight(new BTNode(correctAnimal, null, null)); } } public static boolean query(String prompt) { String answer; System.out.print(prompt + " [Y or N]: "); answer = stdin.nextLine( ).toUpperCase( ); while (!answer.startsWith("Y") && !answer.startsWith("N")) { System.out.print("Invalid response. Please type Y or N: "); answer = stdin.nextLine( ).toUpperCase( ); } return answer.startsWith("Y"); } }

**************************************************************************************

textBookAnimal.txt

?Are you a mammal? ?Are you bigger than a cat? ?Are you a marsupial? kangaroo raccoon mouse ?Do you live underwater? trout robin

***************************************************************

Animals.txt

?Does it have feathers? ?Does it live in a barnyard? chicken ?Is it wise? owl ?Does it say "Nevermore!"? raven ?Does it gobble? turkey eagle ?Is it a mammal? ?Does it have stripes? tiger elephant crocodile ************************************* Sample Run ****************************************

For a knowledge tree represented in file animals sample run of your program may look like the following. Please enter file name: animals Knowledge tree is read from animals Please think of an animal. I will ask some yes/no questions to try to figure out what you are. Does it have feathers? [Y or N]: y Does it live in a barnyard? [Y or N]: y My guess is chicken. Am I right? [Y or N]: y I knew it all along! Shall we play again? [Y or N]: y Does it have feathers? [Y or N]: n Is it a mammal? [Y or N]: y Does it have stripes? [Y or N]: n My guess is elephant. Am I right? [Y or N]: n I give up. What are you? kangaroo Please type a yes/no question that will distinguish a kangaroo from a elephant. Your question: Does it hop? As a kangaroo, Does it hop? Please answer [Y or N]: y Shall we play again? [Y or N]: y Does it have feathers? [Y or N]: n Is it a mammal? [Y or N]: y Does it have stripes? [Y or N]: n Does it hop? [Y or N]: y My guess is kangaroo. Am I right? [Y or N]: y I knew it all along! Shall we play again? [Y or N]: n Thanks for teaching me a thing or two. Now I know the following animals: chicken owl raven turkey eagle tiger kangaroo elephant crocodile Updated knowledge tree is written to file animals