二叉树的一个重要应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有项的值都大于X中的项。注意，这意味着该树所有的元素都可以用某种一致的方式排序。
现在给出通常对二叉查找树进行的操作的简单描述。注意，由于树的递归定义，通常是递归地编写这些操作的例程。因为二叉查找树的平均深度是O(logN)，所以一般不必担心栈空间耗尽。
二叉查找树要求所有的项都能够排序。要写出一个一般的类，我们需要提供一个接口来表示这个性质。这个接口就是Comparable，它告诉我们树中的两项总可以使用compareTo()方法进行比较。由此我们可以确定所有可能关系，特别是以compareTo()返回0来替代equal()判断相等。BinarySearchTree类还包含一个嵌套类BinaryNode，用来表示树的节点。
以下是相关代码及实现：
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
private BinaryNode<AnyType> root;
private static class BinaryNode<AnyType> {
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode<AnyType> lt,
BinaryNode<AnyType> rt) {
element = theElement;
left = lt;
right = rt;
}
}
public BinarySearchTree() {
makeEmpty();
}
/**
* 使树为空树
*/
public void makeEmpty() {
root = null;
}
/**
* 该树是否为空树
*
* @return 是否空
*/
public boolean isEmpty() {
return root == null;
}
/**
* 该树是否存在含有参数值的节点
*
* @param value
* 元素值
* @return 是否含该元素
*/
public boolean contains(AnyType value) {
return contains(value, root);
}
/**
* 某个节点及它的子节点是否存在含有参数值的节点
*
* @param value
* 元素值
* @param node
* 节点
* @return
*/
private boolean contains(AnyType value, BinaryNode<AnyType> node) {
if (node == null) {
return false;
}
int compareResult = value.compareTo(node.element);
if (compareResult < 0) { // 插入节点值小于节点值，则递归查找左子树下
return contains(value, node.left);
} else if (compareResult > 0) { // 插入节点值大于节点值，则递归查找右子树下
return contains(value, node.right);
} else {
return true;
}
}
/**
* 查找该树最小元素值
*
* @return 最小元素值
*/
public AnyType findMin() {
if (isEmpty()) {
throw new NullPointerException();
}
return findMin(root).element;
}
/**
* 查找某节点及其子树中的最小元素
*
* @param node
* 父节点
* @return 最小元素所在节点
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> node) {
if (node == null) {
return null;
} else if (node.left == null) {
return node;
}
return findMin(node.left);
}
/**
* 查找该树最大元素值
*
* @return 最大元素值
*/
public AnyType findMax() {
if (isEmpty()) {
throw new NullPointerException();
}
return findMavalue(root).element;
}
/**
* 查找某节点及其子树中的最大元素
*
* @param node
* 父节点
* @return 最大元素
*/
private BinaryNode<AnyType> findMavalue(BinaryNode<AnyType> node) {
if (node == null) {
return null;
} else if (node.right == null) {
return node;
}
return findMavalue(node.right);
}
/**
* 向树中插入某元素
*
* @param value
* 插入元素值
*/
public void insert(AnyType value) {
root = insert(value, root);
}
/**
* 向某个节点下插入元素
*
* @param value
* 元素值
* @param node
* 父节点
* @return 元素插入的节点
*/
private BinaryNode<AnyType> insert(AnyType value, BinaryNode<AnyType> node) {
if (node == null) {
return new BinaryNode<AnyType>(value);
}
int compareResult = value.compareTo(node.element);
if (compareResult < 0) {
node.left = insert(value, node.left);
} else if (compareResult > 0) {
node.right = insert(value, node.right);
}
return node;
}
/**
* 向树中删除某元素
*
* @param value
* 元素值
*/
public void remove(AnyType value) {
root = remove(value, root);
}
/**
* 在某个节点下删除元素
*
* @param value
* 元素值
* @param node
* 父节点
* @return 删除元素的节点
*/
private BinaryNode<AnyType> remove(AnyType value, BinaryNode<AnyType> node) {
if (node == null) {
return node;
}
int compareResult = value.compareTo(node.element);
if (compareResult < 0) {
node.left = remove(value, node.left);
} else if (compareResult > 0) {
node.right = remove(value, node.right);
} else if (node.left != null && node.right != null) {
node.element = findMin(node.right).element;
node.right = remove(node.element, node.right);
} else {
node = (node.left != null) ? node.left : node.right;
}
return node;
}
/**
* 遍历输出树
*/
public void printTree() {
if (isEmpty()) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}
/**
* 先序遍历输出某节点下元素
*
* @param node
* 节点
*/
private void printTree(BinaryNode<AnyType> node) {
if (node != null) {
printTree(node.left);
System.out.print(node.element + " ");
printTree(node.right);
}
}
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
tree.insert(8);
tree.insert(6);
tree.insert(2);
tree.insert(4);
tree.insert(1);
tree.insert(3);
tree.printTree();
tree.remove(2);
tree.remove(6);
tree.insert(5);
tree.insert(7);
System.out.println("\n------------");
tree.printTree();
}
}
执行结果：
1 2 3 4 6 8
------------
1 3 4 5 7 8