Computer Science 225
Advanced Programming
Spring 2017, Siena College
SimpleIntBinarySearchTree BlueJ Project
Click here to download a BlueJ project for SimpleIntBinarySearchTree.
SimpleIntBinarySearchTree Source Code
The Java source code for SimpleIntBinarySearchTree is below. Click on a file name to download it.
/**
* Example SimpleIntBinarySearchTree: a small binary search tree implementation
* for use in discussing UML diagrams.
*
* @author Jim Teresco
*
* Siena College, Computer Science 225, Spring 2017
*
*/
class IntBSTNode {
/**
* A BST node has left and right references
*/
private IntBSTNode left, right;
/**
* the value stored here
*/
private int value;
/**
* construct a new node, which is a leaf (null children)
*
* @param value the value to store in this node
*/
public IntBSTNode(int value) {
this.value = value;
}
/**
* access the value here
*
* @return the value at this node
*/
public int getValue() {
return value;
}
/**
* access left child
*
* @return reference to this node's left child
*/
public IntBSTNode getLeft() {
return left;
}
/**
* access right child
*
* @return reference to this node's right child
*/
public IntBSTNode getRight() {
return right;
}
/**
* attach a node at this node's left reference
*
* @param newLeft the IntBSTNode to attach as this node's left child
*/
public void setLeft(IntBSTNode newLeft) {
left = newLeft;
}
/**
* attach a node at this node's right reference
*
* @param newRight the IntBSTNode to attach as this node's right child
*/
public void setRight(IntBSTNode newRight) {
right = newRight;
}
}
public class SimpleIntBinarySearchTree {
/**
* the bst has a reference to the head node
*/
private IntBSTNode root;
/**
* we will also maintain a variable tracking the number of values in the tree
*/
private int size;
/**
* construct an empty tree
*/
public SimpleIntBinarySearchTree() {
// nothing to do, root is already null and size is already 0.
}
/**
* add a value to the tree
*
* @param value the value to add to the tree
*/
public void add(int value) {
size++;
if (root == null) {
// simplest case: empty tree, so this becomes the root
root = new IntBSTNode(value);
}
else {
// otherwise, we search for a leaf off of which we hang a new node
IntBSTNode finger = root;
// traverse the tree until we find a place to hang this node
while (true) {
if (value <= finger.getValue()) {
// should go left
if (finger.getLeft() == null) {
finger.setLeft(new IntBSTNode(value));
return;
}
finger = finger.getLeft();
}
else {
// should go right
if (finger.getRight() == null) {
finger.setRight(new IntBSTNode(value));
return;
}
finger = finger.getRight();
}
}
}
}
/**
* print in order traversal
*/
public void printInOrder() {
printInOrder(root);
System.out.println();
}
/**
* recursive helper method to print in order traversal
*/
private void printInOrder(IntBSTNode subTreeRoot) {
if (subTreeRoot != null) {
printInOrder(subTreeRoot.getLeft());
System.out.print(subTreeRoot.getValue() + " ");
printInOrder(subTreeRoot.getRight());
}
}
/**
* @return the number of values stored in the tree
**/
public int size() {
return size;
}
/**
* @return sum of all values in the tree
*/
public int sum() {
return (root != null ? sum(root) : 0);
/* or....
*
* if (root != null) return sum(root);
* else return 0;
*/
}
/**
*
* @param fromHere root of the subtree whose sum is to be computed
* @return sum of all values in the subtree rooted at this node
*/
private int sum(IntBSTNode fromHere) {
//return fromHere.getValue() +
//(fromHere.getLeft() != null ? sum(fromHere.getLeft()) : 0) +
//(fromHere.getRight() != null ? sum(fromHere.getRight()) :0);
int answer = fromHere.getValue();
if (fromHere.getLeft() != null) {
answer += sum(fromHere.getLeft());
}
if (fromHere.getRight() != null) {
answer += sum(fromHere.getRight());
}
return answer;
}
/**
* @param searchVal value to locate in the tree
*
* @return whether this tree contains a given value
*/
public boolean contains(int searchVal) {
// for this one, we will allow null to be passed to the helper method
// and check for it there
return contains(root, searchVal);
}
/**
* @param subTree the root of the subtree to search
* @param searchVal value to locate in the tree
*
* @return whether the portion of the tree rooted at subTree contains the value
*/
private boolean contains(IntBSTNode subTree, int searchVal) {
// an empty subtree contains nothing
if (subTree == null) return false;
// maybe we have it at the root of this subtree?
if (subTree.getValue() == searchVal) return true;
// it might be left or right but we know which sidee
// it would be, so look only that way
if (subTree.getValue() < searchVal)
return contains(subTree.getRight(), searchVal);
return contains(subTree.getLeft(), searchVal);
}
/**
* @return largest value in the tree
*/
public int getMax() {
if (root == null) return 0; // not great, throw exception instead?
return getMax(root);
}
/**
* @param subTree subTree where to find the max
*
* @return largest value in the tree
*/
private int getMax(IntBSTNode subTree) {
// if we have a right subtree, that's where the max lives
if (subTree.getRight() != null) {
return getMax(subTree.getRight());
}
// we didn't have right subtree, so we hold the max!
return subTree.getValue();
}
/**
* @return the height of the tree
*/
public int getHeight() {
// avoid passing null to the helper method by checking for
// the empty tree case here
if (root == null) return 0;
// not empty, go recursion
return getHeight(root);
}
/**
* @param s the (non-null) root of the subtree we are considering
* @return the height of the subtree rooted as s
*/
private int getHeight(IntBSTNode s) {
// compute heights of left and right subtrees first
int leftHeight = 0;
if (s.getLeft() != null) leftHeight = getHeight(s.getLeft());
int rightHeight = 0;
if (s.getRight() != null) rightHeight = getHeight(s.getRight());
// we know left and right heights, the whole thing is one more than
// the larger of the two
if (leftHeight > rightHeight) return 1 + leftHeight;
return 1 + rightHeight;
}
/**
* test the class a bit
*/
public static void main(String[] args) {
SimpleIntBinarySearchTree tree = new SimpleIntBinarySearchTree();
tree.add(5);
tree.add(4);
tree.add(6);
System.out.println("Tree size: " + tree.size());
tree.printInOrder();
System.out.println("Tree sum: " + tree.sum());
System.out.println("Tree max: " + tree.getMax());
System.out.println("Tree height: " + tree.getHeight());
for (int i = 3; i <= 7; i++) {
System.out.println("Tree contains " + i + ": " + tree.contains(i));
}
}
}