Write a class for a bag of strings, where the strings are stored in a binary sea
ID: 3572085 • Letter: W
Question
Write a class for a bag of strings, where the strings are stored in a binary search tree. In creating the binary search tree, you should use the string’s compareTo method, which is described on page 499. The tree itself should use the BTNode class from Figure 9.10 on page 490.
compareTo method:
compareTo (method for the String class)
public int compareTo(String str)
Compare this string to another string.
Returns:
The return value is zero if this string is equal to str.
The return value is negative if this string is lexicographically before str.
The return value is positive if this string is lexicographically after str.
BTNode:
Generic Class BTNode
public class BTNode<E> from the package edu.colorado.nodes
A BTNode<E> provides a node for a binary tree with a reference to an E object as the data in each
node.
Limitations:
Beyond Int.MAX_VALUE elements, treeSize is wrong.
Specification
Constructor for the BTNode<E>
public BTNode(E initialData, BTNode<E> initialLeft, BTNode<E> initialRight)
Initialize a node with specified initial data and links to children. Note that a reference to a child
may be null, which indicates that there is no child.
Parameters:
initialData – the initial data of this new node
initialLeft and initialRight – references to the children of this new node
Postcondition:
This new node contains the specified data and links to its children.
getData—getLeft—getRight
public E getData( )
public BTNode<E> getLeft( )
public BTNode<E> getRight( )
These are accessor methods to obtain this node’s data or a reference to one of the children.
Any of these objects may be null. A null reference to a child indicates that the child does not
exist.
getLeftmostData
public E getLeftmostData( )
Accessor method to get the data from the leftmost node of the tree below this node.
Returns:
The data from the deepest node that can be reached from this node following left links.
getRightmostData
public E getRightmostData( )
Accessor method to get the data from the rightmost node of the tree below this node.
Returns:
The data from the deepest node that can be reached from this node following right links.
inorderPrint—postorderPrint—preorderPrint
public void inorderPrint( )
public void postorderPrint( )
public void preorderPrint( )
Use a traversal to print the data from each node at or below this node of the binary tree.
Postcondition:
The data of this node and all its descendants have been written by System.out.println
using one of three traversal techniques.
isLeaf
public boolean isLeaf( )
Accessor method to determine whether a node is a leaf.
Returns:
true (if this node is a leaf); false otherwise.
print
public void print(int depth)
Uses an in-order traversal to print the data from each node at or below this node of the binary
tree, with indentation to indicate the depth of each node.
Parameter:
depth — the depth of this node (with 0 for the 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 written by System.out.println
using an in-order 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.
removeLeftmost
public BTNode<E> removeLeftmost( )
Remove the leftmost node of the tree with this node as its root.
Postcondition:
The tree starting at this node has had its leftmost node (i.e., the deepest node that can be
reached by following left links) removed. 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).
Example:
If n is a reference to a node in a tree and n has a right child, then we can remove the leftmost
node of n’s right subtree with this assignment:
n.setRight(n.getRight( ).removeLeftmost( ));
removeRightmost
public BTNode<E> removeRightmost( )
Remove the rightmost node of the tree with this node as its root.
Postcondition:
The tree starting at this node has had its rightmost node (i.e., the deepest node that can be
reached by following right links) removed. 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).
Example:
If n is a reference to a node in a tree and n has a left child, then we can remove the rightmost
node of n’s left subtree with this assignment:
n.setLeft(n.getLeft( ).removeRightmost( ));
setData—setLeft—setRight
public void setData(E newData)
public void setLeft(BTNode<E> newLeft)
public void setRight(BTNode<E> newRight)
These are modification methods to set this node’s data or a reference to one of the children.
Any of these objects may be null. Setting a child to null indicates that the child does not exist.
treeCopy
public static <E> BTNode<E> treeCopy(BTNode<E> source)
Copy a binary tree.
Parameter:
source — a reference to the root node of a binary tree that will be copied (which may be an
empty tree where source is null)
Returns:
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.
Throws: OutOfMemoryError
Indicates that there is insufficient memory for the new tree.
treeSize
public static <E> int treeSize(BTNode<E> root)
Compute the number of nodes in a binary tree.
Parameter:
root – the reference to the root of a binary tree (which may be an empty tree with a null root)
Returns:
the number of nodes in the tree with the given root
Note:
A wrong answer occurs for trees larger than Int.MAX_VALUE.
Explanation / Answer
package classes;
import java.util.Arrays;
public class BST<E extends Comparable<E>>
{
private BTNode<E> root;
private int count = 0;
public BST(E data)
{
root = new BTNode(data, null, null);
}
// constructor to build a BST from an array of comparables
public BST(E[] array)
{
E[] ar = array;
Arrays.sort(ar);
// System.out.println(" Sorted: ");
// for (Object object : ar) {
// System.out.println(object.toString());
// }
root = new BTNode(ar[ar.length/2 ], null, null);
builder(ar);
}
// takes in an array, splits it, inserts the middle into the tree,
// and splits it agian, ad nauseam... er recursively
private void builder(E[] array)
{
//System.out.println("ENTERING BUILDER");
E[] arrayLeft = Arrays.copyOfRange(array, 0, array.length/2);
E[] arrayRight = Arrays.copyOfRange(array, (array.length/2) + 1, array.length);
if (arrayLeft.length > 0)
{
//System.out.println(arrayLeft[arrayLeft.length/2]);
insert(root, (arrayLeft[arrayLeft.length/2]));
builder(arrayLeft);
}
if (arrayRight.length > 0)
{
//System.out.println(arrayRight[arrayRight.length/2]);
insert(root, (arrayRight[arrayRight.length/2]));
builder(arrayRight);
}
}
public BTNode<E> getRoot()
{
return root;
}
public void insert(BTNode<E> current, E data)
{
E d1 = current.getData();
E d2 = data;
if (d2.compareTo(d1)<=0) {
if (current.getLeft() == null)
current.setLeft(new BTNode(data,null,null));
else
insert(current.getLeft(),data);
}
else {
if (current.getRight() == null)
current.setRight(new BTNode(data,null,null));
else
insert(current.getRight(), data);
}
}
public int lessThan(BTNode<E> current, E val)
{
this.count = 0;
int numberLessThan = lessThanRecur(current, val);
this.count = 0;
return numberLessThan;
}
private int lessThanRecur(BTNode<E> current, E val)
{
E d1 = current.getData();
E value = val;
if ( value.compareTo(d1) <= 0 ) {
if (current.getLeft() != null) {
lessThanRecur(current.getLeft(), value);
}
} else {
count++;
if (current.getLeft() != null) {
lessThanRecur(current.getLeft(), value);
}
if (current.getRight() !=null) {
lessThanRecur(current.getRight(), value);
}
}
return count;
} //end lessThanRecur(.)
public int greaterThan(BTNode<E> current, E val)
{
this.count = 0;
int numberGreaterThan = greaterThanRecur(current, val);
this.count = 0;
return numberGreaterThan;
}
private int greaterThanRecur(BTNode<E> current, E val)
{
E d1 = current.getData();
E value = val;
if ( value.compareTo(d1) < 0 ) {
count++;
if (current.getRight() !=null) {
greaterThanRecur(current.getRight(), value);
}
if (current.getLeft() != null) {
greaterThanRecur(current.getLeft(), value);
}
} else {
if (current.getRight() !=null) {
greaterThanRecur(current.getRight(), value);
}
}
return this.count;
} //end greaterThanRecur(.)
public int inBetween(BTNode<E> current, E val1, E val2)
{
this.count = 0;
int numberinBetween = inBetweenRecur(current, val1, val2);
this.count = 0;
return numberinBetween;
}
private int inBetweenRecur(BTNode<E> current, E val1, E val2)
{
E d1 = current.getData();
E lower;
E upper;
if ( val1.compareTo(val2) == 0 ) {
throw new IllegalArgumentException("That's not a range bro.");
}
if ( val1.compareTo(val2) < 1 ) {
lower = val1;
upper = val2;
} else {
upper = val1;
lower = val2;
}
if ( upper.compareTo(d1) > 0 && lower.compareTo(d1) < 0 ) {
count++;
if (current.getLeft() != null) {
inBetweenRecur(current.getLeft(), lower, upper);
}
if (current.getRight() !=null) {
inBetweenRecur(current.getRight(), lower, upper);
}
} else {
if (upper.compareTo(d1) <= 0) {
}
if (lower.compareTo(d1) >= 0) {
}
if (current.getLeft() != null) {
inBetweenRecur(current.getLeft(), lower, upper);
}
if (current.getRight() !=null) {
inBetweenRecur(current.getRight(), lower, upper);
}
}
return count;
} //end inBetweenRecur(..)
public void print()
{
root.print(0);
}
public static void main (String [] args)
{
BST<Integer> tree = new BST<>(17);
System.out.println("Building binary search tree with known values");
tree.insert(tree.getRoot(), 2);
tree.insert(tree.getRoot(),34);
tree.insert(tree.getRoot(),5);
tree.insert(tree.getRoot(),55);
tree.insert(tree.getRoot(),15);
tree.insert(tree.getRoot(),25);
tree.insert(tree.getRoot(),9);
tree.print();
System.out.println(" Testing methods on tree with known values:");
System.out.println(" LessThan: 33");
int answer = tree.lessThan(tree.getRoot(), 33);
System.out.println("Answer: " + answer);
System.out.println(" GreaterThan: 5");
answer = tree.greaterThan(tree.getRoot(), 5);
System.out.println("Answer " + answer);
System.out.println(" InBetween: 2 and 34");
answer = tree.inBetween(tree.getRoot(), 2 , 34);
System.out.println("Answer " + answer);
System.out.println(" ------------------------------------------------------------");
System.out.println(" Building binary search tree with random values:");
tree = new BST<>((int)(Math.random()*50));
for (int x=0; x<14; x++)
tree.insert(tree.getRoot(),(int)(Math.random()*50));
tree.print();
System.out.println(" Testing methods on tree with random values and random search values:");
// test how many numbers are less than...
int random = (int)(Math.random()*50);
System.out.println(" LessThan: " + random);
answer = tree.lessThan(tree.getRoot(), random);
System.out.println("Answer: " + answer);
// test how many numbers are greater than...
random = (int)(Math.random()*50);
System.out.println(" GreaterThan: " + random);
answer = tree.greaterThan(tree.getRoot(), random);
System.out.println("Answer " + answer);
// test how many numbers are in between...
//(the inBetween methods have built in logic to pick which is the higher value
// in the range. Exception will be thrown if both values are the same. So I'll catch that here.
random = (int)(Math.random()*50);
int random2 = (int)(Math.random()*50);
System.out.println(" InBetween: " + random + " and " + random2);
try {
answer = tree.inBetween(tree.getRoot(), random , random2);
System.out.println("Answer " + answer);
} catch (IllegalArgumentException e) {
System.out.println(e.getMessage());
}
System.out.println(" ------------------------------------------------------------");
System.out.println(" Testing Building an array from known values:");
Integer[] data = new Integer[15];
for (int i = 0; i < 15; i++) {
data[i] = new Integer(i+1);
}
System.out.println(" Printing out the known value array:");
System.out.println(Arrays.toString(data));
//creating a BST from the array
BST<Integer> treeFromArray = new BST<>(data);
System.out.println(" Printing Tree Built From Array of known values: ");
treeFromArray.print();
System.out.println(" ------------------------------------------------------------");
System.out.println(" Testing Building an array from random values:");
int length = ((int)(Math.random()*25)) + 10;
System.out.println("Printing out array of random length of "+ length +", containing random values");
Integer[] data2 = new Integer[length];
for (int i = 0; i < length; i++) {
data2[i] = new Integer((int)(Math.random()*50));
}
System.out.println(" Printing out the random value array:");
System.out.println(Arrays.toString(data2));
//creating a BST from the random value array
BST<Integer> treeFromArray2 = new BST<>(data2);
System.out.println(" Printing Tree Built From Array: ");
treeFromArray2.print();
System.out.println("Printing out the random value array sorted: (for reference)");
Arrays.sort(data2);
System.out.println(Arrays.toString(data2));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.