Question: // 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
// 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_VALUEelements,treeSize, is* wrong.
*
*
- Java Source Code for this class:
-
* http://www.cs.colorado.edu/~main/edu/colorado/nodes/IntBTNode.java
*
* @author Michael Main
*
* @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
IntBTNodewith 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:
-
*
depthis 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 <= depth; 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 <= depth+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 <= depth+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
sourceis 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
sourceis 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);
}
}
***************************************************************************
//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
IntTreeBagis a collection of int numbers.*
*
- Limitations:
-
* Beyond
Integer.MAX_VALUEelements,countOccurrences,* and
sizeare wrong.*
*
- Outline of Java Source Code for this class:
-
* http://www.cs.colorado.edu/~main/edu/colorado/collections/IntTreeBag.java
*
*
*
- 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)
{
if (root.equals(null)){
root = new IntBTNode(element, null, null);
}
IntBTNode cursor = root;
Boolean done = false;
while (done == false){
if (element <= cursor.getData()){
if (cursor.getLeft() == null){
IntBTNode temp = new IntBTNode(element, null, null);
cursor.setLeft(temp);
done = true;
}
cursor = cursor.getLeft();
}
if (element > cursor.getData()){
if (cursor.getRight() == null){
IntBTNode temp = new IntBTNode(element, null, null);
cursor.setRight(temp);
done = true;
}
cursor = cursor.getRight();
}
}
}
/**
* 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
addendhave been added to this bag.* @exception IllegalArgumentException
* Indicates that
addendis null.* @exception OutOfMemoryError
* Indicates insufficient memory to increase the size of the bag.
**/
public void addAll(IntTreeBag addend)
{
IntBTNode addroot;
if(root == addend.root){
addroot = IntBTNode.treeCopy(addend.root);
addTree(addroot);
}
else{
addTree(addend.root);
}
}
/**
* 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( )
{
IntTreeBag answer;
try{
answer = (IntTreeBag) super.clone();
}
catch (CloneNotSupportedException e){
throw new RuntimeException ("This class does not implement Cloneable.");
}
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
targetoccurs in this bag**/
public int countOccurrences(int target)
{
int count = 0;
IntBTNode cursor = root;
while(cursor != null){
if (target < cursor.getData()){
cursor = cursor.getLeft();
}
if (target > cursor.getData()){
cursor = cursor.getRight();
}
if (target == cursor.getData()){
count++;
cursor = cursor.getLeft();
}
}
return count;
}
/**
* Remove one copy of a specified element from this bag.
* @param
target* the element to remove from the bag
*
- Postcondition:
-
* If
targetwas found in the bag, then one copy of*
targethas been removed and the method returns true.* Otherwise the bag remains unchanged and the method returns false.
**/
public boolean remove(int target)
{
IntBTNode cursor = root;
IntBTNode parentOfCursor = null;
while (cursor != null){
if (target == cursor.getData()){
if (cursor.equals(root)){
if (cursor.isLeaf()){
root = null;
return true;
}
if (cursor.getLeft() == null){
root = root.getRight();
return true;
}
if ( cursor.getRight() == null){
root = root.getLeft();
return true;
}
}
if (cursor.isLeaf()){
if (cursor == parentOfCursor.getLeft()){
parentOfCursor.setLeft(null);
return true;
}
else{
parentOfCursor.setRight(null);
return true;
}
}
if (cursor.getLeft() == null){
if (cursor == parentOfCursor.getLeft()){
parentOfCursor.setLeft(cursor.getRight());
return true;
}
else{
parentOfCursor.setRight(cursor.getRight());
return true;
}
}
if (cursor.getRight() == null){
if (cursor == parentOfCursor.getLeft()){
parentOfCursor.setLeft(cursor.getLeft());
return true;
}
else {
parentOfCursor.setRight(cursor.getLeft());
return true;
}
}
else{
cursor.setData(cursor.getLeft().getRightmostData());
cursor.setLeft(cursor.getLeft().removeRightmost());
return true;
}
}
if (target < cursor.getData()){
parentOfCursor = cursor;
cursor = cursor.getLeft();
}
if (target > cursor.getData()){
parentOfCursor = cursor;
cursor = cursor.getRight();
}
}
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)
{
IntTreeBag answer = null;
answer.addTree(b1.root);
answer.addTree(b2.root);
return answer;
}
// 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 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());
if (addroot.getLeft() != null){
addTree(addroot.getLeft());
}
if (addroot.getRight() != null){
addTree(addroot.getRight());
}
}
}
// Method sortedArrayToBST constructs a BST using a sorted Array
// Parameters: int [] data, int first, int last
// postconditions: returns a balanced BST with elements from int [] data
public static IntTreeBag sortedArrayToBST(int[] data, int first, int last){
IntTreeBag answer = null;
answer.root.setData(data[data.length / 2]);
if (first <= data.length / 2){
IntBTNode temp = new IntBTNode(data[first], null, null);
answer.root.setLeft(temp);
sortedArrayToBST(data, first + 1, last);
}
if (last >= data.length / 2){
IntBTNode temp = new IntBTNode(data[last], null, null);
answer.root.setRight(temp);
sortedArrayToBST(data, first, last - 1);
}
return answer;
}
// Method selectionSort sorts an array from smallest to largest value
// parameters: int[] data, int first, int n
// postcondition: the array is now sorted from smallest value to largest value
public static void selectionSort(int[] data, int first, int n){
int i, j;
int big;
int temp;
for (i = n -1; i > 0; i--){
big = first;
for (j = first + 1; j <= first + i; j++)
if(data[big] < data[j])
big = j;
temp = data[first + i];
data[first + i] = data[big];
data[big] = temp;
}
}
}
Q.Write a program that would do the following: 1) prompt the user to enter the number of integers, then, prompt the user to enter integers (with no duplicates) and place them in an array in the order they are entered; 2) use the sorting algorithm which you picked to sort elements of the array in increasing order and display the result (sorted array); 3) use the method you wrote to produce a balanced binary search tree from the sorted array; 4) display obtained balanced BST (tree 1) using print method of BTNode class; 5) use clone method to create the second tree (tree 2) - clone of the first tree (tree 1); (to test your clone method) 6) allow the user to add and remove elements from tree 2 (multiple copies of elements may be added); display the tree after each addition or removal of an element (to test your add and remove methods); 7) prompt the user for an element and count occurrences of this element in tree 2 (to test your countOccurrences method); 8) use union method to build a union of tree 1 and tree 2 and display the resulting tree (to test union method); 9) use addAll method to add elements from tree 2 to tree 1 and display the result (to test addAll method).
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help