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