In this assignment, you are to implement exercises 19.15, and 19.16.

You need to start with the BinaryNode.java and the BinarySearchTree.java files provided for

you in the text.

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

19.15

Implement find, findMin, and findMax recursively

19.16

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; }

}