Build a Java class file using Switch Case to test all the methods below. public

Q: Build a Java class file using Switch Case to test all the methods below. public

Hi, Please find below test class BinarySearchTreeTest.java for testing all methods. class BinaryNode { //Constructor BinaryNode( AnyType theElement ) { element = theElement; left = right = null; } //Data; accessible by other package routines AnyType element; // The data in the node BinaryNode left; // Left child BinaryNode right; // Right child } public class BinarySearchTree

ID: 3691570 • Letter: B

Question

Build a Java class file using Switch Case to test all the methods below.

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}

/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}

/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}

/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( )
{
root = removeMin( root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public AnyType findMax( )
{
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public AnyType find( AnyType x )
{
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private AnyType elementAt( BinaryNode<AnyType> t )
{
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
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( ) ); // Duplicate
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
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
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if t is empty.
*/
protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> t )
{
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null )
{
t.left = removeMin( t.left );
return t;
}
else
return t.right;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if(t == null)
return null;
else if(t.left == null)
return t;
else
return findMin(t.left);

}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if(t == null)
return null;
else if(t.right == null)
return t;
else
return findMax(t.right);

}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode<AnyType> find( AnyType x, BinaryNode<AnyType> t )
{
if( t != null )
{
if( x.compareTo( t.element ) < 0 )
find(x,t.left);
else if( x.compareTo( t.element ) > 0 )
find(x,t.right);
else
return t; // Match
}

return null; // Not found
}

/** The tree root. */
protected BinaryNode<AnyType> root;

///////////////////////////////////////////////////////////////////////

class BinaryNode<AnyType>
{
// Constructor
BinaryNode( AnyType theElement )
{
element = theElement;
left = right = null;
}

// Data; accessible by other package routines
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}

Explanation / Answer

Hi, Please find below test class BinarySearchTreeTest.java for testing all methods.

class BinaryNode<AnyType>
{
//Constructor
BinaryNode( AnyType theElement )
{
element = theElement;
left = right = null;
}
//Data; accessible by other package routines
AnyType element; // The data in the node

BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{

protected BinaryNode<AnyType> root;
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}
/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException
* @throws DuplicateItemException if x is already present.
*/
public void insert( AnyType x ) throws DuplicateItemException
{
root = insert( x, root );
}
/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException
* @throws ItemNotFoundException if x is not found.
*/
public void remove( AnyType x ) throws ItemNotFoundException
{
root = remove( x, root );
}
/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) throws ItemNotFoundException
{
root = removeMin( root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public AnyType findMax( )
{
return elementAt( findMax( root ) );
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public AnyType find( AnyType x )
{
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private AnyType elementAt( BinaryNode<AnyType> t )
{
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t ) throws DuplicateItemException
{
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( ) ); // Duplicate
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t ) throws ItemNotFoundException
{
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
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException
* @throws ItemNotFoundException if t is empty.
*/
protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> t ) throws ItemNotFoundException
{
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null )
{
t.left = removeMin( t.left );
return t;
}
else
return t.right;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if(t == null)
return null;
else if(t.left == null)
return t;
else
return findMin(t.left);

}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if(t == null)
return null;
else if(t.right == null)
return t;
else
return findMax(t.right);

}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode<AnyType> find( AnyType x, BinaryNode<AnyType> t )
{
if( t != null )
{
if( x.compareTo( t.element ) < 0 )
find(x,t.left);
else if( x.compareTo( t.element ) > 0 )
find(x,t.right);
else
return t; // Match
}

return null; // Not found
}
}

BinarySearchTreeTest.java

import java.util.Scanner;

public class BinarySearchTreeTest {

   /**
   * @param args
   * @throws DuplicateItemException
   * @throws ItemNotFoundException
   */
   public static void main(String[] args) throws DuplicateItemException, ItemNotFoundException {
       // TODO Auto-generated method stub
       Scanner scan = new Scanner(System.in);
   /* Creating object of BST */
       BinarySearchTree bst = new BinarySearchTree();
   System.out.println("Binary Search Tree Test ");
   char ch;
   /* Perform tree operations */
   do
   {
   System.out.println(" Binary Search Tree Operations ");
   System.out.println("1. Add ");
   System.out.println("2. clear");
   System.out.println("3. Max");
   System.out.println("4. check empty");
   System.out.println("5. Min");
   System.out.println("6. Remove Min");

   int choice = scan.nextInt();
   switch (choice)
   {
   case 1 :
   System.out.println("Enter integer element to insert");
   bst.insert( scan.nextInt() );
   break;
   case 2 :
   bst.makeEmpty();
   break;
   case 3 :
   System.out.println("Max = "+ bst.findMax());
   break;
   case 4 :
   System.out.println("Empty status = "+ bst.isEmpty());
   break;
   case 5 :
   System.out.println("Min = "+ bst.findMin());
   break;
   case 6 :
   bst.removeMin();
   System.out.println("Removed");
   break;
   default :
   System.out.println("Wrong Entry ");
   break;
   }
   System.out.println(" Do you want to continue (Type y or n) ");
   ch = scan.next().charAt(0);
   } while (ch == 'Y'|| ch == 'y');

}

Output:

Binary Search Tree Test

Binary Search Tree Operations

1. Add
2. clear
3. Max
4. check empty
5. Min
6. Remove Min
1
Enter integer element to insert
2