JAVA: Help with Binary Search Tree Program

************************ IntBTNode.java **********************************

// File: IntBTNode.java from the package edu.colorado.nodes

// Complete documentation is available from the IntBTNode link in:

// http://www.cs.colorado.edu/~main/docs

//package edu.colorado.nodes;

/*************************************************************************

*****

* A IntBTNode provides a node for a binary tree. Each node

* contains a piece of data (which is a reference to an object) and

references

* to a left and right child. The references to children may be null to

indicate

* that there is no child. The reference stored in a node can also be

null.

*

*

Limitations:

* Beyond Int.MAX_VALUE elements, treeSize, is

* wrong.

*

*

Java Source Code for this class:

*

* http://www.cs.colorado.edu/~main/edu/coloradoodes/IntBTNode.java

*

* @author Michael Main

* (main@colorado.edu)

*

* @version

* Jun 12, 1998

*

* @see BTNode

* @see BooleanBTNode

* @see ByteBTNode

* @see CharBTNode

* @see DoubleBTNode

* @see FloatBTNode

* @see LongBTNode

* @see ShortBTNode

**************************************************************************

****/

public class IntBTNode

{

// Invariant of the IntBTNode class:

// 1. Each node has one integer, stored in the instance

// variable data.

// 2. The instance variables left and right are references to the

node's

// left and right children.

private int data;

private IntBTNode left, right;

/**

* Initialize a IntBTNode with a specified initial data

and links

* children. Note that a child link may be the null reference,

* which indicates that the new node does not have that child.

* @param initialData

* the initial data of this new node

* @param initialLeft

* a reference to the left child of this new node--this reference may

be null

* to indicate that there is no node after this new node.

* @param initialRight

* a reference to the right child of this new node--this reference may

be null

* to indicate that there is no node after this new node.

*

Postcondition:

* This node contains the specified data and links to its children.

**/

public IntBTNode(int initialData, IntBTNode initialLeft, IntBTNode

initialRight)

{

data = initialData;

left = initialLeft;

right = initialRight;

}

/**

* Accessor method to get the data from this node.

* @param - none

* @return

* the data from this node

**/

public int getData( )

{

return data;

}

/**

* Accessor method to get a reference to the left child of this node.

* @param - none

* @return

* a reference to the left child of this node (or the null reference if

there

* is no left child)

**/

public IntBTNode getLeft( )

{

return left;

}

/**

* Accessor method to get the data from the leftmost node of the tree

below

* this node.

* @param - none

* @return

* the data from the deepest node that can be reached from this node by

* following left links.

**/

public int getLeftmostData( )

{

if (left == null)

return data;

else

return left.getLeftmostData( );

}

/**

* Accessor method to get the data from the rightmost node of the tree

below

* this node.

* @param - none

* @return

* the data from the deepest node that can be reached from this node by

* following right links.

**/

public int getRightmostData( )

{

if (right == null)

return data;

else

return right.getRightmostData( );

}

/**

* Accessor method to get a reference to the right child of this node.

* @param - none

* @return

* a reference to the right child of this node (or the null reference

if there

* is no right child)

**/

public IntBTNode getRight( )

{

return right;

}

/**

* Uses an inorder traversal to print the data from each node at or

below

* this node of the binary tree.

* @param - none

*

Postcondition:

* The data of this node and all its descendants have been writeen by

* System.out.println( ) using an inorder traversal.

**/

public void inorderPrint( )

{

if (left != null)

left.inorderPrint( );

System.out.println(data);

if (right != null)

right.inorderPrint( );

}

/**

* Accessor method to determine whether a node is a leaf.

* @param - none

* @return

* true (if this node is a leaf) or

* false (if this node is not a leaf.

**/

public boolean isLeaf( )

{

return (left == null) && (right == null);

}

/**

* Uses a preorder traversal to print the data from each node at or

below

* this node of the binary tree.

* @param - none

*

Postcondition:

* The data of this node and all its descendants have been writeen by

* System.out.println( ) using a preorder traversal.

**/

public void preorderPrint( )

{

System.out.println(data);

if (left != null)

left.preorderPrint( );

if (right != null)

right.preorderPrint( );

}

/**

* Uses a postorder traversal to print the data from each node at or

below

* this node of the binary tree.

* @param - none

*

Postcondition:

* The data of this node and all its descendants have been writeen by

* System.out.println( ) using a postorder traversal.

**/

public void postorderPrint( )

{

if (left != null)

left.postorderPrint( );

if (right != null)

right.postorderPrint( );

System.out.println(data);

}

/**

* Uses an inorder traversal to print the data from each node at or

below

* this node of the binary tree, with indentations to indicate the

depth

* of each node.

* @param depth

* the depth of this node (with 0 for root, 1 for the root's

* children, and so on)(

*

Precondition:

* depth is the depth of this node.

*

Postcondition:

* The data of this node and all its descendants have been writeen by

* System.out.println( ) using an inorder traversal.

* The indentation of each line of data is four times its depth in the

* tree. A dash "--" is printed at any place where a child has no

* sibling.

**/

public void print(int depth)

{

int i;

// Print the indentation and the data from the current node:

for (i = 1; i

System.out.print(" ");

System.out.println(data);

// Print the left subtree (or a dash if there is a right child and

no left child)

if (left != null)

left.print(depth+1);

else if (right != null)

{

for (i = 1; i

System.out.print(" ");

System.out.println("--");

}

// Print the right subtree (or a dash if there is a left child and

no left child)

if (right != null)

right.print(depth+1);

else if (left != null)

{

for (i = 1; i

System.out.print(" ");

System.out.println("--");

}

}

/**

* Remove the leftmost most node of the tree below this node.

* @param - none

*

Postcondition:

* The tree starting at this node has had its leftmost node removed

(i.e.,

* the deepest node that can be reached by following left links). The

* return value is a reference to the root of the new (smaller) tree.

* This return value could be null if the original tree had only one

* node (since that one node has now been removed).

**/

public IntBTNode removeLeftmost( )

{

if (left == null)

return right;

else

{

left = left.removeLeftmost( );

return this;

}

}

/**

* Remove the rightmost most node of the tree below this node.

* @param - none

*

Postcondition:

* The tree starting at this node has had its rightmost node removed

(i.e.,

* the deepest node that can be reached by following right links). The

* return value is a reference to the root of the new (smaller) tree.

* This return value could be null if the original tree had only one

* node (since that one node has now been removed).

**/

public IntBTNode removeRightmost( )

{

if (right == null)

return left;

else

{

right = right.removeRightmost();

return this;

}

}

/**

* Modification method to set the data in this node.

* @param newData

* the new data to place in this node

*

Postcondition:

* The data of this node has been set to newData.

**/

public void setData(int newData)

{

data = newData;

}

/**

* Modification method to set the link to the left child of this node.

* @param newLeft

* a reference to the node that should appear as the left child of this

node

* (or the null reference if there is no left child for this node)

*

Postcondition:

* The link to the left child of this node has been set to

newLeft.

* Any other node (that used to be the left child) is no longer

connected to

* this node.

**/

public void setLeft(IntBTNode newLeft)

{

left = newLeft;

}

/**

* Modification method to set the link to the right child of this node.

* @param newLeft

* a reference to the node that should appear as the right child of

this node

* (or the null reference if there is no right child for this node)

*

Postcondition:

* The link to the right child of this node has been set to

newRight.

* Any other node (that used to be the right child) is no longer

connected to

* this node.

**/

public void setRight(IntBTNode newRight)

{

right = newRight;

}

/**

* Copy a binary tree.

* @param source

* a reference to the root of a binary tree that will be copied (which

may be

* an empty tree where source is null)

* @return

* The method has made a copy of the binary tree starting at

* source. The return value is a reference to the root of

the copy.

* @exception OutOfMemoryError

* Indicates that there is insufficient memory for the new tree.

**/

public static IntBTNode treeCopy(IntBTNode source)

{

IntBTNode leftCopy, rightCopy;

if (source == null)

return null;

else

{

leftCopy = treeCopy(source.left);

rightCopy = treeCopy(source.right);

return new IntBTNode(source.data, leftCopy, rightCopy);

}

}

/**

* Count the number of nodes in a binary tree.

* @param root

* a reference to the root of a binary tree (which may be

* an empty tree where source is null)

* @return

* the number of nodes in the binary tree

*

Note:

* A wrong answer occurs for trees larger than

* INT.MAX_VALUE.

**/

public static int treeSize(IntBTNode root)

{

if (root == null)

return 0;

else

return 1 + treeSize(root.left) + treeSize(root.right);

}

}

************************* IntTreeBag.java *********************************************

/* IntTreeBag.java

// File: IntTreeBag.java from the package edu.colorado.collections

*

* // The implementation of most methods in this file is left as a student

*

* // exercise from Section 9.5 of "Data Structures and Other Objects Using

*

* Java"

*

*

* /*************************************************************************

*****

*

*

* This class is a homework assignment;

*

* An IntTreeBag is a collection of int numbers.

*

*

*

*

*

Limitations:

*

*

* Beyond Integer.MAX_VALUE elements,

*

* countOccurrences,

*

* and size are wrong.

*

*

*

*

Outline of Java Source Code for this class:

*

*

*

*

* http://www.cs.colorado.edu/~main/edu/colorado/collections/IntTreeBag.ja

*

* va

*

*

*

*

*

*

Note:

*

*

* This file contains only blank implementations ("stubs")

*

* because this is a Programming Project for my students.

*

*

*

* @version

*

* Jan 24, 1999

*

*

*

* @see IntArrayBag

*

* @see IntLinkedBag

**************************************************************************

*

*

****/

public class IntTreeBag implements Cloneable

{

// Invariant of the IntTreeBag class:

// 1. The elements in the bag are stored in a binary search tree.

// 2. The instance variable root is a reference to the root of the

// binary search tree (or null for an empty tree).

private IntBTNode root;

static private int counter = 0;

/**

*

* Insert a new element into this bag.

*

* @param element

*

* the new element that is being inserted

*

*

Postcondition:

*

*

* A new copy of the element has been added to this bag.

*

* @exception OutOfMemoryError

*

* Indicates insufficient memory a new IntBTNode.

*

**/

public void add(int element)

{

IntBTNode cursor = root;

IntBTNode node = new IntBTNode(element, null, null);

boolean done = false;

if (root == null) {// creates the first node and it is the root

root = new IntBTNode(element, null, null);

System.out.println("element of root = " + element);

} else {

while (!done) {

if (element

if (cursor.getLeft() == null) {// if null then creates a

// node

cursor.setLeft(node);

done = true;

} else {// then continue going through node until

// cursor.getLeft == null

cursor = cursor.getLeft();

}

} else {// focus on the right

if (cursor.getRight() == null) {

cursor.setRight(node);

done = true;

} else {

cursor = cursor.getRight();

}

}

} // end while

}

}

/**

*

* Add the contents of another bag to this bag.

*

* @param addend

*

* a bag whose contents will be added to this bag

*

*

Precondition:

*

*

* The parameter, addend, is not null.

*

*

Postcondition:

*

*

* The elements from addend have been added to this

* bag.

*

* @exception IllegalArgumentException

*

* Indicates that addend is null.

*

* @exception OutOfMemoryError

*

* Indicates insufficient memory to increase the size of the

* bag.

*

**/

public void addAll(IntTreeBag addend)

{

// Implemented by student.

IntBTNode addroot;

if (addend == null) {

throw new IllegalArgumentException(" bag is empty");

}

if (root == addend.root) {

addroot = IntBTNode.treeCopy(addend.root);

addTree(addroot);

} else {

addTree(addend.root);

}

}

// Precondition: addroot is a reference to the root of a binary search tree

// that is separate from the binary search tree of the bag that activated

// this

// this method.

// Postcondition: All the elements from the addroot's binary search tree

// have been added to the binary search tree of the bag that activated this

// method

private void addTree(IntBTNode addroot) {

if (addroot != null) {

add(addroot.getData());

addTree(addroot.getLeft());

addTree(addroot.getRight());

}

}

/**

*

* Generate a copy of this bag.

*

* @param -

* none

*

* @return

*

* The return value is a copy of this bag. Subsequent changes to the

*

* copy will not affect the original, nor vice versa.

*

* @exception OutOfMemoryError

*

* Indicates insufficient memory for creating the clone.

*

**/

public IntTreeBag clone()

{ // Clone an IntTreeBag object.

// Student will replace this return statement with their own code:

IntTreeBag answer = null;

try {

answer = (IntTreeBag) super.clone();

} catch (CloneNotSupportedException e) {

System.out.println(e.toString());

}

answer.root = IntBTNode.treeCopy(root);

return answer;

}

/**

*

* Accessor method to count the number of occurrences of a particular

*

* element

*

* in this bag.

*

* @param target

*

* the element that needs to be counted

*

* @return

*

* the number of times that target occurs in this bag

*

**/

public int countOccurrences(int target)

{

// Student will replace this return statement with their own code:

IntBTNode cursor = root;

int count = 0;

int nextElement;

if (root == null) {

return 0;

}

while (cursor != null) {

if (target

nextElement = cursor.getLeft().getData();

System.out.println("next data = " + nextElement);

cursor = cursor.getLeft();

} else if (target > cursor.getData()) {

cursor = cursor.getRight();

} else {// means target and cursor.data are equal

count++;

System.out.println("find!!" + counter + " count = " + count);

// System.out.println("next value right" +

// cursor.getRight().getData());

// System.out.println("next value left" +

// cursor.getLeft().getData());

// cursor = cursor.getLeft();

cursor = cursor.getRight();

}

}

return count;

}

/**

*

* Remove one copy of a specified element from this bag.

*

* @param target

*

* the element to remove from the bag

*

*

Postcondition:

*

*

* If target was found in the bag, then one copy of

*

* target has been removed and the method returns

* true.

*

* Otherwise the bag remains unchanged and the method returns

* false.

*

**/

public boolean remove(int target)

{

// Student will replace this return statement with their own code:

IntBTNode parentOfCursor = null;

IntBTNode cursor = root;

while (cursor != null && target != cursor.getData())

{

parentOfCursor = cursor;

if (target

cursor = cursor.getLeft();

else

cursor = cursor.getRight();

}

if (cursor == null)

return false;

else if (cursor.getLeft() == null)

{

if (parentOfCursor == null)

root = cursor.getRight();

else if (cursor == parentOfCursor.getLeft())

parentOfCursor.setLeft(cursor.getRight());

else

parentOfCursor.setRight(cursor.getRight());

return true;

}

else

{

cursor.setData(cursor.getLeft().getRightmostData());

cursor.setLeft(cursor.getLeft().removeRightmost());

return true;

}

}

/**

*

* Determine the number of elements in this bag.

*

* @param -

* none

*

* @return

*

* the number of elements in this bag

*

**/

public int size()

{

return IntBTNode.treeSize(root);

}

/**

*

* Create a new bag that contains all the elements from two other bags.

*

* @param b1

*

* the first of two bags

*

* @param b2

*

* the second of two bags

*

*

Precondition:

*

*

* Neither b1 nor b2 is null.

*

* @return

*

* the union of b1 and b2

*

* @exception IllegalArgumentException

*

* Indicates that one of the arguments is null.

*

* @exception OutOfMemoryError

*

* Indicates insufficient memory for the new bag.

*

**/

public static IntTreeBag union(IntTreeBag b1, IntTreeBag b2)

{

// Student will replace this return statement with their own code:

IntTreeBag newBag = new IntTreeBag();// creates a new bag

if ((b1 == null) || (b2 == null)) {

throw new IllegalArgumentException(" at least one bag is empty");

} else {

newBag = (IntTreeBag) b1.clone();

}

newBag.addAll(b2);

return newBag;

}

}

2. Binary search trees have their best performance when they are balanced, which means that at each node, n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a recursive static method for IntTreeBag class that takes a sorted array of distinct integers and produces a balanced binary search tree. (The array is sorted with smallest integers at front to largest at the end.) The header of the method is the following public static IntTreeBag sortedArrayToBST (int[) data, int first, int last) Hint: Set the middle element of the array to be the root of the tree, then recursively build the left subtree of the root, then the right subtree of the root. Note: For method sortedArrayToBST we assume that integers in the array are distinct (no duplicates) This is because if duplicates are allowed then a balanced BST containing elements from the array may not exist. For example, if array contains integers 5, 5, 5, 5, 5, 5, then a balanced BST containing 6 copies of 5 does not exist. If we use the proposed method to build a balanced BST from this array, we will get that 5 is a right child of 5 which contradicts the BST property that a right child of a node must contain a key that is strictly greater than the key of the node. For all the other methods in the assignments duplicates can be used. Note: IntTreeBag class does not support balanced property. If you add and/or remove nodes from a balanced binary search tree using methods from IntTreeBag class then the resulting tree may no longer be balanced. 2. Binary search trees have their best performance when they are balanced, which means that at each node, n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a recursive static method for IntTreeBag class that takes a sorted array of distinct integers and produces a balanced binary search tree. (The array is sorted with smallest integers at front to largest at the end.) The header of the method is the following public static IntTreeBag sortedArrayToBST (int[) data, int first, int last) Hint: Set the middle element of the array to be the root of the tree, then recursively build the left subtree of the root, then the right subtree of the root. Note: For method sortedArrayToBST we assume that integers in the array are distinct (no duplicates) This is because if duplicates are allowed then a balanced BST containing elements from the array may not exist. For example, if array contains integers 5, 5, 5, 5, 5, 5, then a balanced BST containing 6 copies of 5 does not exist. If we use the proposed method to build a balanced BST from this array, we will get that 5 is a right child of 5 which contradicts the BST property that a right child of a node must contain a key that is strictly greater than the key of the node. For all the other methods in the assignments duplicates can be used. Note: IntTreeBag class does not support balanced property. If you add and/or remove nodes from a balanced binary search tree using methods from IntTreeBag class then the resulting tree may no longer be balanced