JAVA: I need help with the following 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 *********************************************

// 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"

//import edu.colorado.nodes.IntBTNode;

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

*****

* 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;

/**

* 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)

{

// Implemented by student.

}

/**

* 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.

}

/**

* 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:

return null;

}

/**

* 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:

return 0;

}

/**

* 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:

return false;

}

/**

* 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:

return null;

}

}