Sunday, December 21, 2008

Binary Search Tree in Java


import java.io.PrintWriter;

public class BinaryTreeNode {

private Comparable key;
private Object data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode(Comparable pKey, Object pData)
{
key = pKey;
data = pData;
}

/**
* @return Returns the data.
*/
public Object getData() {
return data;
}

/**
* @param data The data to set.
*/
public void setData(Object data) {
this.data = data;
}

/**
* @return Returns the key.
*/
public Comparable getKey() {
return key;
}

/**
* @param key The key to set.
*/
public void setKey(Comparable key) {
this.key = key;
}

/**
* @return Returns the left.
*/
public BinaryTreeNode getLeft() {
return left;
}

/**
* @param left The left to set.
*/
public void setLeft(BinaryTreeNode left) {
this.left = left;
}

/**
* @return Returns the right.
*/
public BinaryTreeNode getRight() {
return right;
}

/**
* @param right The right to set.
*/
public void setRight(BinaryTreeNode right) {
this.right = right;
}



}

public class BinarySearchTree implements Dictionary {

private BinaryTreeNode mRoot;
private int mNumberItems=0;

/* insert
* -exact same functionality as update, see update (drops the return value though)
*/
public void insert(Comparable key, Object data) {
update(key,data);


}
/*recrusiveUpdateChild
* -runs through the entire tree, and updates a child with new data,
* -if the child doesn't exist, it is add at the appropriate branch ending
*
* returns true if update a node
* returns false if added a child at the end of the branch
*
*/
private boolean recurisiveUpdateChild(BinaryTreeNode parent, Comparable key, Object data)
{
if (key.compareTo(parent.getKey())==0)
{
parent.setData(data);
return true; //replaced an associated data node
}
if (key.compareTo(parent.getKey())<0)
{
if (parent.getLeft()==null)
{

parent.setLeft(new BinaryTreeNode(key,data));
mNumberItems++;
return false; //no replacement, addition to the tree
}
return recurisiveUpdateChild(parent.getLeft(),key,data);
}
else
{
if (parent.getRight()==null)
{
parent.setRight(new BinaryTreeNode(key,data));
mNumberItems++;
return false; // no replacement
}
return recurisiveUpdateChild(parent.getRight(),key,data);
}


}
/*Update
* -Provides add, and modify functionality
*
* -returns true if it did a modify
* -returns false if it did an add
*/
public boolean update(Comparable key, Object data) {
if (mRoot==null)
{
mRoot = new BinaryTreeNode(key,data);
mNumberItems++;
return false;
}
else
{
return recurisiveUpdateChild(mRoot,key,data);
}
}
/*recursiveLookupChild
* -simple lookup, traverses through the tree
*
* returns the associated data of the found node, if it found one
*
* returns null - if no node was found (fell off the tree)
*
*/
private Object recurisiveLookupChild(BinaryTreeNode parent, Comparable key)
{
if (key.compareTo(parent.getKey())==0)
{
return parent.getData();
}
if (key.compareTo(parent.getKey())<0)
{
if (parent.getLeft()==null) //fell off the tree
{
return null;
}
else
{
return recurisiveLookupChild(parent.getLeft(),key);
}
}
else
{
if (parent.getRight()==null) //fell off the tree
{
return null;
}
else
{
return recurisiveLookupChild(parent.getRight(),key);
}
}
}

/*lookup
* -looksup the data from the tree
* returns Data or null if not found
*/
public Object lookup(Comparable key) {
if (mRoot==null) return null;

return recurisiveLookupChild(mRoot,key);
}
/*size
* returns number of items in tree
*/
public int size() {
return mNumberItems;
}
/*print
* does an inorder traversal, printing out a sorted list of items
*/
public void print(PrintWriter p) {
//p.println("Printing Binary Search Tree");
printNode(mRoot,p);
}
/*printnode
* -recursive aux method for the print funcationality
*/
private void printNode(BinaryTreeNode node,PrintWriter p)
{
if (node==null) return;
//simple inorder traversal
printNode(node.getLeft(),p);

p.print(node.getKey());
p.print(" ");
p.println(node.getData());

printNode(node.getRight(),p);
}
}

No comments: