/*
* BinarySearchTree.java
*/
import java.util.LinkedList;
import java.util.List;
public class BinarySearchTree <Key extends Comparable<Key>, Data> {
// name of root
Key name = null;
// data of root
Data value = null;
// left subtree
BinarySearchTree<Key, Data> leftSubtree = null;
// right subtree
BinarySearchTree<Key, Data> rightSubtree = null;
/**
* Creates a new empty binary search tree
*/
public BinarySearchTree() {
}
/**
* Determines if tree is empty or not
* @return
* boolean describing if tree is empty or not
*/
public boolean isEmptyTree(){
return name == null;
}
/**
* Determines the smallest right child/successor
* @return
* leftest node in right subtree
*/
public BinarySearchTree<Key, Data> findSmallestChild(){
// no left subtree exist -> found leftest node
if (leftSubtree.isEmptyTree())
return this;
// left subtree found -> go on with recursion
else
return leftSubtree.findSmallestChild();
}
/**
* Determines the greatest left child/successor
* @return
* rightest node in left subtree
*/
public BinarySearchTree<Key, Data> findGreatestChild(){
// right subtree is empty -> found rightest node
if (rightSubtree.isEmptyTree())
return this;
// there is another right subtree -> go further on with recursion
else
return rightSubtree.findGreatestChild();
}
/**
* Adds the specified key and the related data to the tree.
* If the specified key already exists an KeyAlreadyExistsException should be thrown.
*/
public void add(Key key, Data data) {
// check if key already contained in tree
if (contains(key))
throw new KeyAlreadyExistsException();
// (sub)tree is empty -> add key
if (isEmptyTree()){
name = key;
value = data;
// subtrees are new empty trees
leftSubtree = new BinarySearchTree<Key, Data>();
rightSubtree = new BinarySearchTree<Key, Data>();
}
// key is less than root -> go on with left subtree
if (name.compareTo(key) > 0)
// subtree is empty -> add key
if (leftSubtree.isEmptyTree()){
leftSubtree.name = key;
leftSubtree.value = data;
// subtrees are new empty trees
leftSubtree.leftSubtree = new BinarySearchTree<Key, Data>();
leftSubtree.rightSubtree = new BinarySearchTree<Key, Data>();
}
// go on with left subtree
else
leftSubtree.add(key, data);
// key is greater than root -> go on with right subtree
if (name.compareTo(key) < 0)
// subtree is empty -> add key
if (rightSubtree.isEmptyTree()){
rightSubtree.name = key;
rightSubtree.value = data;
// subtrees are new empty trees
rightSubtree.leftSubtree = new BinarySearchTree<Key, Data>();
rightSubtree.rightSubtree = new BinarySearchTree<Key, Data>();
}
// go on with right subtree
else
rightSubtree.add(key, data);
}
/**
* Removes the specified key and its related data from the tree.
* If the tree does not contain the specified key, an KeyNotInTreeException should be thrown.
*/
public void remove (Key key) {
// check if key exists in tree
if (!contains(key))
throw new KeyNotInTreeException();
// check if key is less than root (-> left subtree)
if (name.compareTo(key) > 0)
leftSubtree.remove(key);
// check if key is greater than root (-> right subtree)
else if (name.compareTo(key) < 0)
rightSubtree.remove(key);
// key is wether in left nor in right subtree -> key must be root of actual subtree
else{
// left subtree is empty
if (leftSubtree.isEmptyTree()){
// replace key with right subtree
name = rightSubtree.name;
value = rightSubtree.value;
leftSubtree = rightSubtree.leftSubtree;
rightSubtree = rightSubtree.rightSubtree;
}
// right subtree is empty
else if (rightSubtree.isEmptyTree()){
// replace key with left subtree
name = leftSubtree.name;
value = leftSubtree.value;
leftSubtree = leftSubtree.leftSubtree;
rightSubtree = leftSubtree.rightSubtree;
}
// both subtrees are non-empty
else{
// get leftest(smallest) right(greater) child/successor
BinarySearchTree<Key, Data> child = rightSubtree.findSmallestChild();
// replace key with leftest right child
name = child.name;
value = child.value;
// no left subtree exist because got leftest right child -> take right one
child.name = child.rightSubtree.name;
child.value = child.rightSubtree.value;
}
}
}
/**
* Returns the data of the specified key.
* If the tree does not contain the specified key, an KeyNotInTreeException should be thrown.
*/
public Data getData (Key key) {
// tree is empty
if (isEmptyTree())
throw new KeyNotInTreeException();
// key belongs to left subtree
if (name.compareTo(key) > 0)
return leftSubtree.getData(key);
// key belongs to right subtree
if (name.compareTo(key) < 0)
return rightSubtree.getData(key);
// found key (key doesn't belong to left or right subtree but exists)
else
return value;
}
/**
* Returns true, if the tree contains the specified key and false otherwise
*/
public boolean contains (Key key){
// tree is empty -> key can't be contained
if (isEmptyTree())
return false;
// search for key in left subtree
if (name.compareTo(key) > 0)
return leftSubtree.contains(key);
// search for key in right subtree
if (name.compareTo(key) < 0)
return rightSubtree.contains(key);
// key found
else
return true;
}
/**
* Returns a List with all the keys saved in pre-order (WLR)
*/
public List <Key> getPreOrder(){
// initialize list
LinkedList<Key> result = new LinkedList<Key>();
// first add root
result.add(name);
// then add left subtree
if (!leftSubtree.isEmptyTree())
result.addAll(leftSubtree.getPreOrder());
// and last add right subtree
if (!rightSubtree.isEmptyTree())
result.addAll(rightSubtree.getPreOrder());
return result;
}
/**
* Returns a List with all the keys saved in in-order (LWR)
*/
public List <Key> getInOrder(){
// initialize list
LinkedList<Key> result = new LinkedList<Key>();
// first add left subtree
if (!leftSubtree.isEmptyTree())
result.addAll(leftSubtree.getInOrder());
// then add root
result.add(name);
// and last add right subtree
if (!rightSubtree.isEmptyTree())
result.addAll(rightSubtree.getInOrder());
return result;
}
/**
* Returns a List with all the keys saved in post-order (LRW)
*/
public List <Key> getPostOrder(){
// initialize list
LinkedList<Key> result = new LinkedList<Key>();
// first add left subtree
if (!leftSubtree.isEmptyTree())
result.addAll(leftSubtree.getPostOrder());
// then add right subtree
if (!rightSubtree.isEmptyTree())
result.addAll(rightSubtree.getPostOrder());
// and last add root
result.add(name);
return result;
}
}