一）二叉查找树定义
二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.
摘自维基百科：http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
二）二叉查找树的实现（java）
节点实现类：
package com.fox.bst.o2;
public class BinaryNode<T> {
T element;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
super();
this.element = element;
this.left = left;
this.right = right;
}
public BinaryNode(T element) {
this(element, null, null);
}
}
BST实现类：
package com.fox.bst.o2;
public class BinarySearchTree<T extends Comparable<? super T>> {
private BinaryNode<T> root;
public BinarySearchTree() {
root = null;
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(T x) {
return contains(x, root);
}
private boolean contains(T x, BinaryNode<T> t) {
if (x == null)
throw new IllegalArgumentException("参数异常！");
if (t == null)
return false;
int compareResult = x.compareTo(t.element);
if (compareResult == 0)
return true;
else if (compareResult < 0)
return contains(x, t.left);
else
return contains(x, t.right);
}
public T findMax() {
if (isEmpty())
return null;
return findMax(root);
}
// 递归
private T findMax(BinaryNode<T> t) {
if (t.right == null)
return t.element;
else
return findMax(t.right);
}
public T findMin() {
if (isEmpty())
return null;
return findMin(root);
}
// 非递归
private T findMin(BinaryNode<T> t) {
while (t.left != null) {
t = t.left;
}
return t.element;
}
public void insert(T x) {
root = insert(x, root);
}
// 递归
private BinaryNode<T> insert(T x, BinaryNode<T> t) {
if (x == null)
throw new IllegalArgumentException("参数异常！");
if (t == null)
return new BinaryNode<T>(x);
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);
else
;
return t;
}
public void remove(T x) {
root = remove(x, root);
}
private BinaryNode<T> remove(T x, BinaryNode<T> t) {
if (x == null)
throw new IllegalArgumentException("参数异常！");
if (t == null)
return null;
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 = remove(t.element, t.right);
} else
t = (t.left != null) ? t.left : t.right;
return t;
}
public static void main(String[] f) {
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
System.out.println(bst.contains(1));
// System.out.println(bst.contains(null));
bst.insert(1);
bst.insert(3);
bst.insert(6);
bst.insert(5);
System.out.println(bst.contains(1));
System.out.println(bst.findMax());
System.out.println(bst.findMin());
System.out.println(bst.contains(5));
bst.remove(5);
System.out.println(bst.contains(5));
}
}
这里注意删除操作，根据节点的特点分成三种情况区别对待。
1）叶子节点，直接删除；
2）只有一个孩子节点，那么就让其父节点直接“牵手”其唯一子节点；
3）有两个孩子节点，那么用其右子树的最小节点N代替他，然后递归删除节点N。（这只是其中一种策略）
如果嫌麻烦，可以标记删除，那么在其他操作就要复杂一点。