Description:

Modify the author's BinarySearchTree code to implement the methods shown below.

a) nodeCount Recursively traverses the tree and returns the count of nodes.

b) isFull Returns true if the tree is full. A full tree has every node as either a leaf or a parent with two children.

c) compareStructure Compares the structure of current tree to another tree and returns true if they match.

For example, these two trees have the same structure:

5 10 / \ / \ 3 8 5 15 / \ / \ 1 4 2 7

d) equals Compares the current tree to another tree and returns true if they are identical.

e) copy Creates and returns a new tree that is a copy of the original tree.

f) mirror Creates and returns a new tree that is a mirror image of the original tree. For example, for the tree on the left, the tree on the right is returned: 100 100 / \ / \ 50 150 --> 150 50 / \ 40 40 \ / 45 45

g) isMirror Returns true if the tree is a mirror of the passed tree.

h) rotateRight Performs a single rotation on the node having the passed value. If a RotateRight on 100 is performed:

100 50 / \ / \ 50 150 --> 40 100 / \ \ 40 45 150 \ 45

g) rotateLeft As above but left rotation.

i) printLevels - performs a level-by-level printing of the tree.

j) main - demonstrate in your main method that all of your new methods work.

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

// 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 /** * 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 ); } /** * 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 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!" ); } } }