| BinarySearchTree.java |
package tree;
/**
* Binary Search Tree
* @author Winston Prakash
*/
public class BinarySearchTree<E extends Comparable<E>> implements Tree<E>{
private Node<E> rootNode;
public boolean isEmpty(){
return rootNode == null;
}
/**
* Traverse the tree and insert the value at the corresponding node
*
*/
public void insert(E item){
if (rootNode == null){
rootNode = new Node<E>(item, null, null);
}else{
insertNode(item, rootNode);
}
}
public void remove(E item){
rootNode = removeNode(item, rootNode);
}
/*
* Try finding the node corresponding to the item
* if node not found then the value does not exist
* in the data structure
*/
public boolean contains(E item){
return find(item, rootNode) != null;
}
/**
* Find the minimum value node and return its value
*/
public E minimum(){
if (rootNode != null){
return findMinimumNode(rootNode).getElement();
}else{
return null;
}
}
/**
* Find the maximum value node and return its value
*/
public E maximum(){
if (rootNode != null){
return findMaximumNode(rootNode).getElement();
}else{
return null;
}
}
public void display() {
printInOrder(rootNode,"T");
System.out.println();
}
/*
* Recursively traverse the right nodes of sub trees until the right child is null
* The current subtree root is the minimum value node
*/
private Node<E> findMaximumNode(Node<E> node){
if (node.getRightNode() == null){
return node;
}else{
return findMaximumNode(node.getRightNode());
}
}
/*
* Recursively traverse the left nodes of sub tree until the left child is null
* The current subtree root is the maximum value node
*/
private Node<E> findMinimumNode(Node<E> node){
if (node.getLeftNode() == null){
return node;
}else{
return findMinimumNode(node.getLeftNode());
}
}
/**
* If the item is less than the root node value, then
* traverse the left node sub trees to find the item.
* If larger, traverse the right node sub trees to find
* the item. If the left or right child node is null and
* still the node is not found then return null, if found
* matching value in the node, then return the node
*/
private Node<E> find(E item, Node<E> node){
if (node == null){
return null;
}else if (item.compareTo(node.getElement()) < 0){
return find(item, node.getLeftNode());
}else if (item.compareTo(node.getElement()) > 0){
return find(item, node.getRightNode());
}else{ //item.compareTo(node.getElement()) == 0
return node; // found
}
}
/**
* If the item is less than the root node value, then
* traverse the left node sub trees until no left child
* exist, then insert the item as left child of that sub tree
* If larger, traverse the right node sub trees until no
* right child found, then insert the item as right child.
*/
private Node<E> insertNode(E item, Node<E> node){
if (node == null){
node = new Node<E>(item, null, null);
}else if (item.compareTo(node.getElement()) < 0){
node.setLeftNode(insertNode(item, node.getLeftNode()));
}else if (item.compareTo(node.getElement()) > 0){
node.setRightNode(insertNode(item, node.getRightNode()));
}else{ //item.compareTo(node.getElement()) == 0
; // Duplicate do nothing
}
return node;
}
/**
* Recursively traverse the root node to find the child to be
* removed. Traverse the left node subtree if value is less than
* root value else the right node sub tree.
* If node is found check its children.
* 1. Has no children, then simply remove the node. In this recursive
* case simply return null, so that left or right of sub root
* will be set to null when recursion unwinds
* 2. Has one child, then return that child, when the recursion unwinds
* then sub root node will be set with that child
* 3. Has both children, then find the minimum node from the right node sub root node
* and sets its value as node value. Then recursively remove the right child node
*/
private Node<E> removeNode(E item, Node<E> node){
if (node == null){
return node;
}else if (item.compareTo(node.getElement()) < 0){
node.setLeftNode(removeNode(item, node.getLeftNode()));
}else if (item.compareTo(node.getElement()) > 0){
node.setRightNode(removeNode(item, node.getRightNode()));
}else{ //item.compareTo(node.getElement()) == 0
if ((node.getLeftNode() != null) && (node.getRightNode() != null)){ // Has both children
Node rightMinNode = findMinimumNode(node.getRightNode());
node.setElement((E)rightMinNode.getElement());
node.setRightNode(removeNode(node.getElement(),node.getRightNode()));
}else if (node.getLeftNode() != null){ // No right child
node = node.getLeftNode();
}else if (node.getRightNode() != null){
node = node.getRightNode(); // No left child
}else{
node = null;
}
}
return node;
}
/**
* Print the tree data in its order
*/
private void printInOrder(Node<E> node, String ordinal) {
if (node != null){
printInOrder(node.getLeftNode(), "L");
System.out.print(ordinal + node + " ");
printInOrder(node.getRightNode(), "R");
}
}
private void printPreOrder(Node<E> node, String ordinal) {
if (node != null){
System.out.print(ordinal + node + " ");
printInOrder(node.getLeftNode(), "L");
printInOrder(node.getRightNode(), "R");
}
}
private void printPostOrder(Node<E> node, String ordinal) {
if (node != null){
printInOrder(node.getLeftNode(), "L");
printInOrder(node.getRightNode(), "R");
System.out.print(ordinal + node + " ");
}
}
private static class Node<E extends Comparable<E>>{
private E element;
private Node<E> leftNode;
private Node<E> rightNode;
Node(E element, Node<E>leftNode, Node<E>rightNode){
this.element = element;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
void setLeftNode(Node<E> leftNode){
this.leftNode = leftNode;
}
Node<E> getLeftNode(){
return leftNode;
}
void setRightNode(Node<E> rightNode){
this.rightNode = rightNode;
}
Node<E> getRightNode(){
return rightNode;
}
E getElement(){
return element;
}
void setElement(E element){
this.element = element;
}
public String toString(){
E left = null;
E right = null;
if (leftNode != null) left = leftNode.getElement();
if (rightNode != null) right = rightNode.getElement();
return " [" + element + "] ";
}
}
}