Java Homework Help on BinarySearchTree

• 17th Jun, 2022
• 15:33 PM

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// boolean contains( x )  --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * Implements an unbalanced binary search tree.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class BinarySearchTree>
{
    /**
     * Construct the tree.
     */
    public BinarySearchTree( )
    {
        root = null;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        root = insert( x, root );
    }

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

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

    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public AnyType findMax( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMax( root ).element;
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return true if not found.
     */
    public boolean contains( AnyType x )
    {
        return contains( 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;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    /**
     * Calculate size of the tree.
     */
    public int size( )
    {
       return size( root );
    }

    /**
     * Calculate number of leaves in the tree.
     */
    public int numLeaves( )
    {
        if( isEmpty( ) )
            return 0;
        else
            return numLeaves( root );
    }

    /**
     * Calculate number of left children in the tree.
     */
    public int numLeftChildren( )
    {
        if( isEmpty( ) )
            return 0;
        else
            return numLeftChildren( root );
    }

    /**
     * Check is each node of tree has two children or no children.
     */
    public boolean isFull( )
    {
        if( isEmpty( ) )
            return true;
        else
            return isFull( root );
    }

    /**
     * Calculates the depth of the node containing given element
     */
    public int nodeDepth( AnyType element )
    {
        if ( isEmpty() )
            return -1;
        else
            return nodeDepth( root, element, 0 );
    }

    /**
     * Prints all nodes of tree ordered by levels
     */
    public void printByLevels( )
    {
        Queue> queue = new ArrayDeque<>();
        if ( root == null )
        {
            System.out.println( "Empty tree" );
            return;
        }
        queue.add( root );
        while ( !queue.isEmpty() )
        {
            BinaryNode currNode = queue.poll();
            System.out.print( currNode.element + " " );

            if ( currNode.left != null )
                queue.add( currNode.left );
            if ( currNode.right != null )
                queue.add( currNode.right );
        }
        System.out.println();
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode insert( AnyType x, BinaryNode t )
    {
        if( t == null )
            return new BinaryNode<>( x, null, null );

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return t;
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode remove( AnyType x, BinaryNode t )
    {
        if( t == null )
            return t;   // Item not found; do nothing

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            t.left = remove( x, t.left );
        else if( compareResult > 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 = remove( t.element, t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }

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

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

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the subtree.
     * @return node containing the matched item.
     */
    private boolean contains( AnyType x, BinaryNode t )
    {
        if( t == null )
            return false;

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            return contains( x, t.left );
        else if( compareResult > 0 )
            return contains( x, t.right );
        else
            return true;    // Match
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the subtree.
     */
    private void printTree( BinaryNode t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

    /**
     * Internal method to calculate size of subtree.
     * @param t the node that roots the subtree.
     */
    private int size( BinaryNode t )
    {
        if( t != null )
        {
            return 1 + size( t.left ) + size( t.right );
        }
        else
            return 0;
    }

    /**
     * Internal method to calculate number of leaves in the subtree.
     * @param t the node that roots the subtree.
     */
    private int numLeaves( BinaryNode t )
    {
        if ( t.left == null && t.right == null )
            return 1;

        int leaves = 0;
        if ( t.left != null )
            leaves += numLeaves( t.left );
        if ( t.right != null )
            leaves += numLeaves( t.right );
        return leaves;
    }

    /**
     * Internal method to calculate number of left children in the subtree.
     * @param t the node that roots the subtree.
     */
    private int numLeftChildren( BinaryNode t )
    {
        int leftChildren = 0;
        if ( t.left != null  )
        {
            leftChildren += 1 + numLeftChildren( t.left );
        }

        if ( t.right != null  )
        {
            leftChildren += numLeftChildren( t.right );
        }

        return leftChildren;
    }

    /**
     * Internal method to check if subtree us full or not.
     * @param t the node that roots the subtree.
     */
    private boolean isFull( BinaryNode t )
    {
        if ( t.left == null && t.right == null )
            return true;
        if ( t.left != null && t.right != null )
            return isFull( t.left ) && isFull( t.right );
        return false;
    }

    /**
     * Internal method to check if subtree us full or not.
     * @param t the node that roots the subtree.
     * @param element the element to find.
     * @param depth current depth of the node
     */
    private int nodeDepth( BinaryNode t, AnyType element, int depth )
    {
        if ( element.equals( t.element ) )
            return depth;

        if ( t.left != null )
        {
            int result = nodeDepth( t.left, element, depth + 1 );
            if ( result >= 0 )
                return result;
        }

        if ( t.right != null )
        {
            int result = nodeDepth( t.right, element, depth + 1 );
            if ( result >= 0 )
                return result;
        }

        return -1;
    }

    /**
     * Internal method to compute height of a subtree.
     * @param t the node that roots the subtree.
     */
    private int height( BinaryNode t )
    {
        if( t == null )
            return -1;
        else
            return 1 + Math.max( height( t.left ), height( t.right ) );
    }

    // Basic node stored in unbalanced binary search trees
    private static class BinaryNode
    {
        // Constructors
        BinaryNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( AnyType theElement, BinaryNode lt, BinaryNode rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        AnyType element;            // The data in the node
        BinaryNode left;   // Left child
        BinaryNode right;  // Right child
    }

    /** The tree root. */
    private BinaryNode root;

    // Test program
    public static void main( String [ ] args )
    {
        BinarySearchTree t = new BinarySearchTree<>( );
        final int NUMS = 4000;
        final int GAP  =   37;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        for( int i = 1; i < NUMS; i+= 2 )
            t.remove( i );

        if( NUMS < 40 )
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );

        for( int i = 2; i < NUMS; i+=2 )
            if( !t.contains( i ) )
                System.out.println( "Find error1!" );

        for( int i = 1; i < NUMS; i+=2 )
        {
            if( t.contains( i ) )
                System.out.println( "Find error2!" );
        }

        BinarySearchTree testTree = new BinarySearchTree<>();
        if ( testTree.size() != 0 )
            System.out.println( "Find error3!" );
        if ( testTree.numLeaves() != 0 )
            System.out.println( "Find error4!" );
        if ( testTree.numLeftChildren() != 0 )
            System.out.println( "Find error5!" );
        if ( !testTree.isFull() )
            System.out.println( "Find error6!" );
        if ( testTree.nodeDepth( 5 ) != -1 )
            System.out.println( "Find error7!" );
        testTree.printByLevels();

        testTree.insert(25);
        if ( testTree.size() != 1 )
            System.out.println( "Find error8!" );
        if ( testTree.numLeaves() != 1 )
            System.out.println( "Find error9!" );
        if ( testTree.numLeftChildren() != 0 )
            System.out.println( "Find error10!" );
        if ( !testTree.isFull() )
            System.out.println( "Find error11!" );
        if ( testTree.nodeDepth( 5 ) != -1 )
            System.out.println( "Find error12!" );
        if ( testTree.nodeDepth( 25 ) != 0 )
            System.out.println( "Find error13!" );
        testTree.printByLevels();

        testTree.insert(50);
        if ( testTree.size() != 2 )
            System.out.println( "Find error14!" );
        if ( testTree.numLeaves() != 1 )
            System.out.println( "Find error15!" );
        if ( testTree.numLeftChildren() != 0 )
            System.out.println( "Find error16!" );
        if ( testTree.isFull() )
            System.out.println( "Find error17!" );
        if ( testTree.nodeDepth( 5 ) != -1 )
            System.out.println( "Find error18!" );
        if ( testTree.nodeDepth( 50 ) != 1 )
            System.out.println( "Find error19!" );
        testTree.printByLevels();

        testTree.insert(10);
        if ( testTree.size() != 3 )
            System.out.println( "Find error20!" );
        if ( testTree.numLeaves() != 2 )
            System.out.println( "Find error21!" );
        if ( testTree.numLeftChildren() != 1 )
            System.out.println( "Find error22!" );
        if ( !testTree.isFull() )
            System.out.println( "Find error23!" );
        if ( testTree.nodeDepth( 5 ) != -1 )
            System.out.println( "Find error24!" );
        if ( testTree.nodeDepth( 10 ) != 1 )
            System.out.println( "Find error25!" );
        testTree.printByLevels();

        testTree.insert(5);
        if ( testTree.size() != 4 )
            System.out.println( "Find error26!" );
        if ( testTree.numLeaves() != 2 )
            System.out.println( "Find error27!" );
        if ( testTree.numLeftChildren() != 2 )
            System.out.println( "Find error28!" );
        if ( testTree.isFull() )
            System.out.println( "Find error29!" );
        if ( testTree.nodeDepth( 4 ) != -1 )
            System.out.println( "Find error30!" );
        if ( testTree.nodeDepth( 5 ) != 2 )
            System.out.println( "Find error31!" );
        testTree.printByLevels();

        testTree.insert(30);
        if ( testTree.size() != 5 )
            System.out.println( "Find error32!" );
        if ( testTree.numLeaves() != 2 )
            System.out.println( "Find error33!" );
        if ( testTree.numLeftChildren() != 3 )
            System.out.println( "Find error34!" );
        if ( testTree.isFull() )
            System.out.println( "Find error35!" );
        if ( testTree.nodeDepth( 4 ) != -1 )
            System.out.println( "Find error36!" );
        if ( testTree.nodeDepth( 30 ) != 2 )
            System.out.println( "Find error37!" );
        testTree.printByLevels();

        testTree.insert(15);
        if ( testTree.size() != 6 )
            System.out.println( "Find error39!" );
        if ( testTree.numLeaves() != 3 )
            System.out.println( "Find error40!" );
        if ( testTree.numLeftChildren() != 3 )
            System.out.println( "Find error41!" );
        if ( testTree.isFull() )
            System.out.println( "Find error42!" );
        if ( testTree.nodeDepth( 4 ) != -1 )
            System.out.println( "Find error43!" );
        if ( testTree.nodeDepth( 15 ) != 2 )
            System.out.println( "Find error44!" );
        testTree.printByLevels();

        testTree.insert(100);
        if ( testTree.size() != 7 )
            System.out.println( "Find 45!" );
        if ( testTree.numLeaves() != 4 )
            System.out.println( "Find error46!" );
        if ( testTree.numLeftChildren() != 3 )
            System.out.println( "Find error47!" );
        if ( !testTree.isFull() )
            System.out.println( "Find error48!" );
        if ( testTree.nodeDepth( 4 ) != -1 )
            System.out.println( "Find error49!" );
        if ( testTree.nodeDepth( 100 ) != 2 )
            System.out.println( "Find error50!" );
        testTree.printByLevels();
    }
}