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

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

// 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

// 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

/** * 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); }

public void printLeaves(){ **************this needed************************ }

}//end ***********************************************************************************************************************************************************

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; Scanner scan= new Scanner(System.in); 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 yeso 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 yeso 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"); }

public static BTNode readFromFile(Scanner input){ *******this needed************************* }

public static void writeToFile(PrintWriter output, BTNode root){ *******************this needed********************* }

}

Download binary tree node class BTNode ava and animal guessing program AnimalGuess.java 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 textbook Animals 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 l. Add recursive method printLeaves to the generic BTNode class: public void print Leaves 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 returnthe 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