二叉查找树

import java.util.Comparator;

/**
 * 二叉查找树
 * 
 * @author Jelly
 * 
 * @param <T>
 */
public class BinarySearchTree<T extends Comparable<? super T>> {

	private BinaryNode<T> root;
	private Comparator<? super T> cmp;

	public BinarySearchTree() {
		root = null;
	}

	public BinarySearchTree(Comparator<? super T> c) {
		root = null;
		cmp = c;
	}

	private int myComparable(T lhs, T rhs) {
		if (cmp != null) {
			return cmp.compare(lhs, rhs);
		} else {
			return lhs.compareTo(rhs);
		}
	}

	public void makeEmpty() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public boolean contains(T x) {
		return contains(x, root);
	}

	public T findMin() {
		if (isEmpty()) {
			System.out.println("UndeclaredThrowableException");
		}
		return findMin(root).element;
	}

	private BinaryNode<T> findMin(BinaryNode<T> t) {
		if (null == t) {
			return null;
		} else if (null == t.left) {
			return t;
		}
		return findMin(t.left);
	}

	public T findMax() {
		if (isEmpty()) {
			System.out.println("UndeclaredThrowableException");
		}
		return findMax(root).element;
	}

	private BinaryNode<T> findMax(BinaryNode<T> t) {
		if (null != t) {
			while (t.right != null) {
				t = t.right;
			}
		}
		return t;
	}

	public void insert(T x) {
		insert(x, root);
	}

	public void remove(T x) {
		root = remove(x, root);
	}

	public void printTree() {
		if (isEmpty()) {
			System.out.println("Empty tree");
		} else {
			printTree(root);
		}
	}

	public boolean contains(T x, BinaryNode<T> t) {
		if (t == null) {
			return false;
		}
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0) {
			return contains(x, t.left);
		} else if (compareResult < 0) {
			return contains(x, t.right);
		} else {
			return true;
		}
	}

	private BinaryNode<T> insert(T x, BinaryNode<T> t) {
		if (t == null) {
			return new BinaryNode<T>(x, null, null);
		}
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0) {
			t.left = insert(x, t.left);
		} else if (compareResult > 0) {
			t.right = insert(x, t.right);
		}
		return t;
	}

	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
		if (t == null) {
			return t;
		}
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0) {
			t.left = remove(x, t.left);
		} else if (compareResult > 0) {
			t.right = remove(x, t.right);
		} else if (t.left != null && t.right != null) {
			t.element = findMin(t.right).element;
			t.right = remove(t.element, t.right);
		} else {
			t = (t.left != null) ? t.left : t.right;
		}
		return null;
	}

	private void printTree(BinaryNode<T> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}

	private static class BinaryNode<T> {
		BinaryNode(T theElement) {
			this(theElement, null, null);
		}

		public BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
			this.element = theElement;
			this.left = lt;
			this.right = rt;
		}

		T element; // The data in the node
		BinaryNode<T> left; // Left child
		BinaryNode<T> right; // Right child
	}
}