JAVA PROGRAMMING ;

In this assignment, you are to implement exercises 19.15, and 19.16 on page 766 of the book. You need to start with the BinaryNode.java and the BinarySearchTree.java files provided for you in the text. I recommend that you type them instead of obtaining them from the book's website. In order to test your code, you need to implement a driver program for this assignment. Your driver program must test all the methods that are provided in the BinarySearchTree class implementation repeatedly. So, what you need to do is go into a while loop and a switch statement within it to handle all the choices. while quit was not selected switch(choice) case 1: Insert case 2: find . . . default: quit. end switch end while One of the choices in your driver program must be to print the tree as shown in figure 18.6 of the book except instead of using tabs as the character that signifies a level down the tree, use the '*' character. You need to submit all three files (BinaryNode.java, BinarySearchTree.java, and the driver) You must not make any changes to the BinaryNode.java file, but submit it anyway. 

19.16

Implement find, findMin, and findMax recursively

19.17

Implement findKth non recursively, using the same technique used for a non recursive find.

Binary Node public class BinaryNode { BinaryNode(AnyType theElement) { element = theElement; left = right = null; } AnyType element; BinaryNode left; BinaryNode right; }

public class BinarySearchTree>{ protected BinaryNode root; public BinarySearchTree() { root = null; } public void insert( AnyType x) { root = insert(x, root); } public void remove(AnyType x) { root = remove(x, root); } public void removeMin() { root = removeMin(root); } public AnyType findMin() { return elementAt (findMin(root)); } public AnyType findMax() { return elementAt(findMax(root)); } public AnyType find( AnyType x) { return elementAt(find (x, root)); } public void makeEmpty() { root = null; } public boolean isEmpty() { return root == null; } private AnyType elementAt (BinaryNode t) { return t == null ? null : t.element; } private BinaryNode find(AnyType x, BinaryNode t) { while(t != null) { if(x.compareTo(t.element)< 0){ t = t.left; }else if ( x.compareTo(t.element)>0){ t = t.right; }else{ return t; //match } } return null; } protected BinaryNode findMin( BinaryNode t) { if(t != null) while (t.left != null) t = t.left; return t; } private BinaryNode findMax( BinaryNode t) { if(t != null) while (t.right != null) t = t.right; return t; } protected BinaryNode insert( AnyType x, BinaryNode t) { if(t == null) { t = new BinaryNode(x); } else if( x.compareTo(t.element)< 0) { t.left = insert(x, t.left); } else if(x.compareTo(t.element)> 0) { t.right = insert(x, t.right); } else { throw new DuplicateItemException(x.toString() ); } return t; } protected BinaryNode removeMin( BinaryNode t) { if(t == null) { throw new ItemNotFoundException(); } if(t.left != null) { return t.right; } t.left = removeMin(t.left); return t.left; }

protected BinaryNode remove( AnyType x, BinaryNode t) { if(t == null) { Throw new ItemNotFoundException(x.toString()); } if(x.compareTo(t.element)>0) { t.left = remove(x , t.left); } else if(x.compareTo(t.element)>0) { t.right = remove(x, t.right); } else if( t.left != null && t.right != null) // two children { t.element = findMin(t.right).element; t.right = removeMin(t.right); } else { return (t.left != null)? t.left : t.right; } return t; }

}