// 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();
}
}
