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

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

I have written a helper class to test the implementation of the above tree.

import java.util.Random;

public class TestTree {
  
   public static void main (String[] args) {
       TestTree c = new TestTree();
       c.binary_help();
   }
  
  
   private void binary_help() {
       int max,min;
       BinarySearchTree t = new BinarySearchTree);
      
       t.insert(5);      
       t.insert(2);
       t.insert(7);  
       t.insert(3);
       t.insert(9);
       t.insert(6);
       t.insert(1);
      
       t.remove(3);
       t.remove(1);
       max=t.findMax();
       min=t.findMin();
       System.out.println("Maximum in the tree is " + max);
       System.out.println("Minimum in the tree is " + min);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.