COP 3530
sections U03
Spring 2017



                        The Binary Search Tree Handout
                        ==============================





This handout contains 5 classes BinarySearchTree, BinaryNode (this will be inserted 
after we are done with Homework #3), DuplicateItemException, ItemNotFoundException,
Main (the driver) and the output.



1. The BinaryNode class
----------------------------------------------------------------------------------

    This class will be inserted after we are done with Homework #3.
----------------------------------------------------------------------------------


2. The BinarySearchTree class
----------------------------------------------------------------------------------
public class BinarySearchTree<T extends Comparable<? super T>>
{
    
    /** Creates a new instance of BinarySearchTree */
    public BinarySearchTree()
    {
        root = null;
    }
    
    // insert x in the tree
    public void insert(T x)
    {
        root = insert(x,root);
    }
    
    // remove x from the tree
    public void remove(T x)
    {
        root = remove(x,root);
    }
    
    public void removeMin()
    {
        root = removeMin(root);
    }
    
    public T findMin()
    {
        return elementAt( findMin(root));
    }
    
    public T findMax()
    {
        return elementAt( findMax( root));
    }
    
    public T find(T x)
    {
        return elementAt( find(x,root));
    }
    
    public void makeEmpty()
    {
        root = null;
    }
    
    public boolean isEmpty()
    {
        return root == null;
    }
    
    // private method to get an element field
    // @param t is the node
    // @return the element field or null if t is null
    private T elementAt( BinaryNode<T> t)
    {
        return t == null ? null : t.element;
    }
    
    // internal method to find an item in a subtree
    // @param x is the inquiry
    // @param t is the root of the tree
    // @return the node containing that item
    private BinaryNode<T> find(T x, BinaryNode<T> t)
    {
        while ( t != null)
        {
            if (x.compareTo(t.element) < 0 )    
                t = t.left;
            else if ( x.compareTo(t.element) > 0)
                t = t.right;
            else // we found the value
                return t;
        }    
        
        // the value was not found
        return null;
    }
    // find the smallest item in a subtree
    // @param t is the node that roots the tree
    // @return the node that contains the smallest value
    protected BinaryNode<T> findMin(BinaryNode<T> t)
    {
        if ( t != null)
            while ( t.left != null)
                t = t.left;
        return t;
    }
    
    // find the largest item in the tree
    // @param t is the root of the tree
    // @return the node contaoning the largest item
    private BinaryNode<T> findMax(BinaryNode<T> t)
    {
        if (t != null)
            while ( t.right != null)
                t = t.right;
        return t;
    }
    
    // inset into a subtree
    // @param x is the item to insert
    // @param t is the root
    // return the new root
    // @throws DuplicateItemException if x is present in the tree
    protected BinaryNode<T>  insert(T x, BinaryNode<T> t )
    {
        if (t == null)
            t = new BinaryNode<T>(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 // xis already in the tree
            throw new DuplicateItemException(x.toString());
        return t;
    }
    
    // remove the minimal item from a tree
    // @param t is the root of the tree
    // @return the new root
    // throws ItemNotFoundException if t is empty
    protected BinaryNode<T> removeMin(BinaryNode<T> t)
    {    
        if ( t == null)
            throw new ItemNotFoundException();
        else if ( t.left != null )
        {
            t.left = removeMin(t.left);
            return t;
        }
        else
            return t.right;
    }
    
    // remove a node from a subtree
    // @param X is the item to remove
    // @param t is the root of the subtree
    // @return the new root
    // @throws ItemNotFoundException if x ix not found
    protected BinaryNode<T> remove(T x, BinaryNode<T> t)
    {
        if ( t == null)
            throw new ItemNotFoundException();
        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;
     }
    
    // print the tree in preorder
    public void printPreOrder()
    {
        if (root != null)
            root.printPreOrder();
    }
    
    // print the tree in postorder
    public void printPostOrder()
    {
        if (root != null)
            root.printPostOrder();
    }
    
    // print the tree in inorder
    public void printInOrder()
    {
        if (root != null)
            root.printInOrder();
    }
    
    
    
     // the field
    
    protected BinaryNode<T> root;
}
----------------------------------------------------------------------------------


3. The DuplicateItemException class


----------------------------------------------------------------------------------
public class DuplicateItemException extends IllegalArgumentException
{
    
    /** Creates a new instance of DuplicateItemException */
    public DuplicateItemException(String msg) {}
    
}
----------------------------------------------------------------------------------


4. The ItemNotFoundException class

----------------------------------------------------------------------------------
public class ItemNotFoundException extends IllegalArgumentException
{
    
    /** Creates a new instance of ItemNotFoundException */
    public ItemNotFoundException() 
    {
    }
    
}
----------------------------------------------------------------------------------


5. The Main class

----------------------------------------------------------------------------------


public class Main {
       
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // print the title
        System.out.println("Testing Binary Search Trees");
        System.out.println("===========================\n\n\n");
        
        // form a binary search tree with the names Papa Bill, Hex, Poco Pelo
        // Ali Baba, Tornado, Shrek, Zorba, Geoff the Chef
        System.out.println("Form a binary search tree with the names Papa Bill, Hex, Poco Pelo,");
        System.out.println("Ali Baba, Tornado, Shrek, Zorba, Geoff the Chef");
        
        BinarySearchTree<String> t = new BinarySearchTree<String>();
        t.insert("Papa Bill");
        t.insert("Hex");
        t.insert("Poco Pelo");
        t.insert("Ali Baba");
        t.insert("Tornado");
        t.insert("Shrek");
        t.insert("Zorba");
        t.insert("Geoff the Chef");
        
        // try to insert Zorba again
        try
        {
            System.out.println("We try to insert Zorba again.");
            t.insert("Zorba");
        }
        catch (DuplicateItemException e)
        {
            System.out.println("We get a duplicate item exception.");
        }
        
        System.out.println("We print the tree in preorder and inorder");
        System.out.println("The tree in preorder");
        t.printPreOrder();
        System.out.println("\nThe tree in inorder");
        t.printInOrder();
       
        // find the min and the max
        System.out.println("The min is " + t.findMin());
        System.out.println("The max is " + t.findMax());
        // remove some items
        System.out.println("Remove Papa Bill");
        t.remove("Papa Bill");
        
        System.out.println("We print the tree in preorder and inorder");
        System.out.println("The tree in preorder");
        t.printPreOrder();
        System.out.println("\nThe tree in inorder");
        t.printInOrder();
        
        System.out.println("We try to remove Papa Bill again.");
        try
        {
            t.remove("Papa Bill");
        }        
        catch ( ItemNotFoundException e)
        {
            System.out.println("We get an item not found exception.");
        }
        
        // we remove Tornado
        System.out.println("Remove Tornado");
        t.remove("Tornado");
        
        System.out.println("We print the tree in preorder and inorder");
        System.out.println("The tree in preorder");
        t.printPreOrder();
        System.out.println("\nThe tree in inorder");
        t.printInOrder();
               
    }
    
}

----------------------------------------------------------------------------------


6. The output:

----------------------------------------------------------------------------------
run:
Testing Binary Search Trees
===========================



Form a binary search tree with the names Papa Bill, Hex, Poco Pelo,
Ali Baba, Tornado, Shrek, Zorba, Geoff the Chef
We try to insert Zorba again.
We get a duplicate item exception.
We print the tree in preorder and inorder
The tree in preorder
Papa Bill
Hex
Ali Baba
Geoff the Chef
Poco Pelo
Tornado
Shrek
Zorba

The tree in inorder
Ali Baba
Geoff the Chef
Hex
Papa Bill
Poco Pelo
Shrek
Tornado
Zorba
The min is Ali Baba
The max is Zorba
Remove Papa Bill
We print the tree in preorder and inorder
The tree in preorder
Poco Pelo
Hex
Ali Baba
Geoff the Chef
Tornado
Shrek
Zorba

The tree in inorder
Ali Baba
Geoff the Chef
Hex
Poco Pelo
Shrek
Tornado
Zorba
We try to remove Papa Bill again.
We get an item not found exception.
Remove Tornado
We print the tree in preorder and inorder
The tree in preorder
Poco Pelo
Hex
Ali Baba
Geoff the Chef
Zorba
Shrek

The tree in inorder
Ali Baba
Geoff the Chef
Hex
Poco Pelo
Shrek
Zorba
BUILD SUCCESSFUL (total time: 3 seconds)
----------------------------------------------------------------------------------