JAVA programming: In this assignment, you are to implement exercises 19.15, and
ID: 3915166 • Letter: J
Question
JAVA programming: 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.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<AnyType> {
BinaryNode(AnyType theElement)
{
element = theElement;
left = right = null;
}
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
}
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>{
protected BinaryNode<AnyType> 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<AnyType> t)
{
return t == null ? null : t.element;
}
private BinaryNode<AnyType> find(AnyType x, BinaryNode<AnyType> 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<AnyType> findMin( BinaryNode<AnyType> t)
{
if(t != null)
while (t.left != null)
t = t.left;
return t;
}
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t)
{
if(t != null)
while (t.right != null)
t = t.right;
return t;
}
protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t)
{
if(t == null)
{
t = new BinaryNode<AnyType>(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<AnyType> removeMin( BinaryNode<AnyType> t)
{
if(t == null)
{
throw new ItemNotFoundException();
}
if(t.left != null)
{
return t.right;
}
t.left = removeMin(t.left);
return t.left;
}
protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> 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;
}
}
Explanation / Answer
here is your answer : ---------->>>>>>>>>>
import java.util.Scanner;
public class BSTDriver{
public static void menu(){
System.out.println("1- Insert ");
System.out.println("2- Remove");
System.out.println("3- Find");
System.out.println("4- FindMin");
System.out.println("5- FindMax");
System.out.println("6- RemoveMin");
System.out.println("7- Quit");
System.out.println("Choose Number(1-7)... ");
}
public static void main(String[] args) {
BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
String choice = "9";
Scanner sc = new Scanner(System.in);
while(!choice.equals("7")){
menu();
choice = sc.next();
switch(choice){
case "7":break;
case "1":
{
int n;
System.out.println("Enter A Integer Number to insert : ");
n = sc.nextInt();
t.insert(new Integer(n));
break;
}
case "2":
{
int n;
System.out.println("Enter A Integer Number to remove : ");
n = sc.nextInt();
t.remove(new Integer(n));
break;
}
case "3":
{
int n;
System.out.println("Enter A Integer Number to Find : ");
n = sc.nextInt();
if(t.find(new Integer(n)) != null){
System.out.println("Found");
}else{
System.out.println("Not Found");
}
break;
}
case "4":
{
System.out.println("Min Value = "+t.findMin());
break;
}
case "5":
{
System.out.println("Max Value = "+t.findMax());
break;
}
case "6":
{
System.out.println("Removed Min Value ");
break;
}
default:
sytem.out.println("Wrong Choice !!! ");
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.