Java Homework

profilejzhng1
assignment_9.txt

For this project, write a program that stores integers in a binary search tree. The tree should use the BTNode class which is provided. Write a test program that generates 20 random numbers in the range of -50 to 50 to build the tree and then uses preorderPrint, inorderPrint, and postOrderPrint to display the contents of the tree. To get an A implement a new method for the BTNode class which creates a Java vector class to contain the data from all the nodes in the tree. The specification for this method is provided in the BTNode file. Details about the Java vector class are provided in Appendix D, although the only vector method you'll use is addElement. Also specify and implement in-order and post-order traversals and answer the question which of the three new methods creates a vector with the entries sorted from smallest to largest? Your test program should display the vectors created by your new methods rather than the print methods of BTNode. // 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 BTNode; import java.util.Vector; /****************************************************************************** * A <CODE>BTNode&lt;<E&gt;</CODE> 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. * * <dl><dt><b>Limitations:</b> <dd> * Beyond <CODE>Int.MAX_VALUE</CODE> elements, <CODE>treeSize</CODE>, is * wrong. * * <dt><b>Java Source Code for this class:</b><dd> * <A HREF="../../../../edu/colorado/nodes/BTNode.java"> * http://www.cs.colorado.edu/~main/edu/colorado/nodes/BTNode.java </A> * * @author Michael Main * <A HREF="mailto:[email protected]"> ([email protected]) </A> * * @version * Jul 22, 2005 ******************************************************************************/ public class BTNode<E> { // Invariant of the BTNode<E> 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<E> left, right; /** * Initialize a <CODE>BTNode</CODE> 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 <CODE>initialData</CODE> * the initial data of this new node * @param <CODE>initialLeft</CODE> * 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 <CODE>initialRight</CODE> * 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. * <dt><b>Postcondition:</b><dd> * This node contains the specified data and links to its children. **/ public BTNode(E initialData, BTNode<E> initialLeft, BTNode<E> 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<E> 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<E> 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 * <dt><b>Postcondition:</b><dd> * The data of this node and all its descendants have been writeen by * <CODE>System.out.println( )</CODE> 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 * <CODE>true</CODE> (if this node is a leaf) or * <CODE>false</CODE> (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 * <dt><b>Postcondition:</b><dd> * The data of this node and all its descendants have been writeen by * <CODE>System.out.println( )</CODE> 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 * <dt><b>Postcondition:</b><dd> * The data of this node and all its descendants have been writeen by * <CODE>System.out.println( )</CODE> 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 <CODE>depth</CODE> * the depth of this node (with 0 for root, 1 for the root's * children, and so on)( * <dt><b>Precondition:</b><dd> * <CODE>depth</CODE> is the depth of this node. * <dt><b>Postcondition:</b><dd> * The data of this node and all its descendants have been writeen by * <CODE>System.out.println( )</CODE> 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 * <dt><b>Postcondition:</b><dd> * 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<E> 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 * <dt><b>Postcondition:</b><dd> * 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<E> removeRightmost( ) { if (right == null) return left; else { right = right.removeRightmost( ); return this; } } /** * Modification method to set the data in this node. * @param <CODE>newData</CODE> * the new data to place in this node * <dt><b>Postcondition:</b><dd> * The data of this node has been set to <CODE>newData</CODE>. **/ public void setData(E newData) { data = newData; } /** * Modification method to set the link to the left child of this node. * @param <CODE>newLeft</CODE> * 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) * <dt><b>Postcondition:</b><dd> * The link to the left child of this node has been set to <CODE>newLeft</CODE>. * Any other node (that used to be the left child) is no longer connected to * this node. **/ public void setLeft(BTNode<E> newLeft) { left = newLeft; } /** * Modification method to set the link to the right child of this node. * @param <CODE>newLeft</CODE> * 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) * <dt><b>Postcondition:</b><dd> * The link to the right child of this node has been set to <CODE>newRight</CODE>. * Any other node (that used to be the right child) is no longer connected to * this node. **/ public void setRight(BTNode<E> newRight) { right = newRight; } /** * Copy a binary tree. * @param <CODE>source</CODE> * a reference to the root of a binary tree that will be copied (which may be * an empty tree where <CODE>source</CODE> is null) * @return * The method has made a copy of the binary tree starting at * <CODE>source</CODE>. 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 <E> BTNode<E> treeCopy(BTNode<E> source) { BTNode<E> leftCopy, rightCopy; if (source == null) return null; else { leftCopy = treeCopy(source.left); rightCopy = treeCopy(source.right); return new BTNode<E>(source.data, leftCopy, rightCopy); } } /** * Count the number of nodes in a binary tree. * @param <CODE>root</CODE> * a reference to the root of a binary tree (which may be * an empty tree where <CODE>source</CODE> is null) * @return * the number of nodes in the binary tree * <dt><b>Note:</b><dd> * A wrong answer occurs for trees larger than * <CODE>INT.MAX_VALUE</CODE>. **/ public static <E> long treeSize(BTNode<E> root) { if (root == null) return 0; else return 1 + treeSize(root.left) + treeSize(root.right); } /** * The method does a pre-order traversal of all nodes at or below this node, * appending the data from each node to a Vector * @param v * the Vector that will have data appended to it * @precondition * The node and all its descendants have been traversed with a pre-order * traversal, and all data has been apended to v using v.addElement * @postcondition * The node and all its descendants have been traversed with a pre-order * traversal, and all data has been appended to v using v.addElement. * @throws NullPointerException * Indicates that v is null. * */ public void preorderVector(Vector<E> v){ } } // 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 <CODE>AnimalGuess</CODE> Java application illustrates the use of * the binary tree node class is a small animal-guessing game. * * <p><dt><b>Java Source Code for this class:</b><dd> * <A HREF="../applications/Animals.java"> * http://www.cs.colorado.edu/~main/applications/Animals.java * </A> * * @author Michael Main * <A HREF="mailto:[email protected]"> ([email protected]) </A> * * @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 <CODE>String</CODE> argument * (<CODE>args</CODE>) is not used in this implementation. **/ public static void main(String[ ] args) { BTNode<String> 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 <CODE>current</CODE> * a reference to the root node of a binary taxonomy tree that will be * used to play the game. * <dt><b>Postcondition:</b><dd> * 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<String> 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<String> beginningTree( ) { BTNode<String> root; BTNode<String> 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<String>(ROOT_QUESTION, null, null); // Create and attach the left subtree. child = new BTNode<String>(LEFT_QUESTION, null, null); child.setLeft(new BTNode<String>(ANIMAL1, null, null)); child.setRight(new BTNode<String>(ANIMAL2, null, null)); root.setLeft(child); // Create and attach the right subtree. child = new BTNode<String>(RIGHT_QUESTION, null, null); child.setLeft(new BTNode<String>(ANIMAL3, null, null)); child.setRight(new BTNode<String>(ANIMAL4, null, null)); root.setRight(child); return root; } /** * Elicits information from the user to improve a binary taxonomy tree. * @param <CODE>current</CODE> * a reference to a leaf node of a binary taxonomy tree * <dt><b>Precondition:</b><dd> * <CODE>current</CODE> is a reference to a leaf in a binary * taxonomy tree * <dt><b>Postcondition:</b><dd> * 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<String> 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 + "."); 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<String>(correctAnimal, null, null)); current.setRight(new BTNode<String>(guessAnimal, null, null)); } else { current.setLeft(new BTNode<String>(guessAnimal, null, null)); current.setRight(new BTNode<String>(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"); } } // File: IntTreeBag.java from the package edu.colorado.collections // The implementation of most methods in this file is left as a student // exercise from Section 9.5 of "Data Structures and Other Objects Using Java" // Check with your instructor to see whether you should put this class in // a package. At the moment, it is declared as part of edu.colorado.collections: package edu.colorado.collections; import edu.colorado.nodes.IntBTNode; /****************************************************************************** * This class is a homework assignment; * An <CODE>IntTreeBag</CODE> is a collection of int numbers. * * <dl><dt><b>Limitations:</b> <dd> * Beyond <CODE>Integer.MAX_VALUE</CODE> elements, <CODE>countOccurrences</CODE>, * and <CODE>size</CODE> are wrong. * * <dt><b>Outline of Java Source Code for this class:</b><dd> * <A HREF="../../../../edu/colorado/collections/IntTreeBag.java"> * http://www.cs.colorado.edu/~main/edu/colorado/collections/IntTreeBag.java * </A> * * <dt><b>Note:</b><dd> * This file contains only blank implementations ("stubs") * because this is a Programming Project for my students. * * @version * Jan 24, 1999 * * @see IntArrayBag * @see IntLinkedBag ******************************************************************************/ public class IntTreeBag implements Cloneable { // Invariant of the IntTreeBag class: // 1. The elements in the bag are stored in a binary search tree. // 2. The instance variable root is a reference to the root of the // binary search tree (or null for an empty tree). private IntBTNode root; /** * Insert a new element into this bag. * @param <CODE>element</CODE> * the new element that is being inserted * <dt><b>Postcondition:</b><dd> * A new copy of the element has been added to this bag. * @exception OutOfMemoryError * Indicates insufficient memory a new IntBTNode. **/ public void add(int element) { // Implemented by student. } /** * Add the contents of another bag to this bag. * @param <CODE>addend</CODE> * a bag whose contents will be added to this bag * <dt><b>Precondition:</b><dd> * The parameter, <CODE>addend</CODE>, is not null. * <dt><b>Postcondition:</b><dd> * The elements from <CODE>addend</CODE> have been added to this bag. * @exception IllegalArgumentException * Indicates that <CODE>addend</CODE> is null. * @exception OutOfMemoryError * Indicates insufficient memory to increase the size of the bag. **/ public void addAll(IntTreeBag addend) { // Implemented by student. } /** * Generate a copy of this bag. * @param - none * @return * The return value is a copy of this bag. Subsequent changes to the * copy will not affect the original, nor vice versa. Note that the return * value must be type cast to an <CODE>IntTreeBag</CODE> before it can be used. * @exception OutOfMemoryError * Indicates insufficient memory for creating the clone. **/ public Object clone( ) { // Clone an IntTreeBag object. // Student will replace this return statement with their own code: return null; } /** * Accessor method to count the number of occurrences of a particular element * in this bag. * @param <CODE>target</CODE> * the element that needs to be counted * @return * the number of times that <CODE>target</CODE> occurs in this bag **/ public int countOccurrences(int target) { // Student will replace this return statement with their own code: return 0; } /** * Remove one copy of a specified element from this bag. * @param <CODE>target</CODE> * the element to remove from the bag * <dt><b>Postcondition:</b><dd> * If <CODE>target</CODE> was found in the bag, then one copy of * <CODE>target</CODE> has been removed and the method returns true. * Otherwise the bag remains unchanged and the method returns false. **/ private boolean remove(int target) { // Student will replace this return statement with their own code: return false; } /** * Determine the number of elements in this bag. * @param - none * @return * the number of elements in this bag **/ public int size( ) { return IntBTNode.treeSize(root); } /** * Create a new bag that contains all the elements from two other bags. * @param <CODE>b1</CODE> * the first of two bags * @param <CODE>b2</CODE> * the second of two bags * <dt><b>Precondition:</b><dd> * Neither b1 nor b2 is null. * @return * the union of b1 and b2 * @exception IllegalArgumentException * Indicates that one of the arguments is null. * @exception OutOfMemoryError * Indicates insufficient memory for the new bag. **/ public static IntTreeBag union(IntTreeBag b1, IntTreeBag b2) { // Student will replace this return statement with their own code: return null; } }