二叉搜索树：对于树中任一节点x，其左子树的关键字小于等于x.key，其右子树的关键字大于等于x.key。二叉搜索树其常见操作的最坏时间复杂度度均为O(h)，其中h为树的高度。用于实现linux进程管理和Java TreeMap的红黑树就是一种平衡二叉搜索树。
下面为二叉搜索树的Java实现（参考算法导论的伪代码）
package Tree; import java.util.LinkedList; import java.util.List; class TreeNode { int key; TreeNode parent; TreeNode lchild,rchild; TreeNode() { key=0; parent=null; lchild=null; rchild=null; } TreeNode(int key) { this.key=key; parent=null; lchild=null; rchild=null; } TreeNode(int key,TreeNode parent,TreeNode lchild,TreeNode rchild) { this.key=key; this.parent=parent; this.lchild=lchild; this.rchild=rchild; } } public class BinarySearchTree { TreeNode root=null; List<Integer> treelist=new LinkedList<Integer>(); public void inorderWalk(TreeNode x) { if(x!=null) { inorderWalk(x.lchild); treelist.add(x.key); inorderWalk(x.rchild); } } public TreeNode search(int k) { TreeNode y=root; while(y!=null) { if(y.key==k) { return y; } else if(y.key>k) { y=y.lchild; } else { y=y.rchild; } } return y; } public TreeNode maxNode() { TreeNode p=root; TreeNode max=null; while(p!=null) { max=p; p=p.rchild; } return max; } public TreeNode minNode() { TreeNode p=root; TreeNode min=null; while(p!=null) { min=p; p=p.lchild; } return min; } public TreeNode successor(TreeNode x) { TreeNode s=null; if(x.rchild!=null) { TreeNode min=null; TreeNode p=x.rchild; while(p!=null) { min=p; p=p.lchild; } return min; } else { s=x.parent; while(s!=null&&x==s.rchild) { x=s; s=s.parent; } return s; } } public TreeNode predecessor(TreeNode x) { TreeNode y=null; if(x.lchild!=null) { TreeNode p=x.lchild; TreeNode max=null; while(p!=null) { max=p; p=p.rchild; } return max; } else { y=x.parent; while(y!=null&&x==y.lchild) { x=y; y=y.parent; } return y; } } public void insert(TreeNode x) { TreeNode p=root,q=null; while(p!=null) { q=p; if(p.key>=x.key) { p=p.lchild; } else { p=p.rchild; } } if(q==null) { root=x; return; } x.parent=q; if(q.key>=x.key) { q.lchild=x; } else { q.rchild=x; } } //v replace u private void transplant(TreeNode u, TreeNode v) { if(u.parent==null) { root=v; } else if(u==u.parent.lchild) { u.parent.lchild=v; } else u.parent.rchild=v; if(v!=null) v.parent=u.parent; } public void delete(TreeNode z) { if(z.lchild==null) { transplant(z,z.rchild); } else if(z.rchild==null) { transplant(z,z.lchild); } else { TreeNode y=successor(z); if(y.parent!=z) { transplant(y,y.rchild); y.rchild=z.rchild; y.rchild.parent=y; } transplant(z,y); y.lchild=z.lchild; y.rchild=z.rchild; } } public static void main(String[] args) { BinarySearchTree mbst=new BinarySearchTree(); int[] marray={15,6,18,3,7,17,20,2,4,13,9}; for(int i=0;i<marray.length;i++) { TreeNode mtreenode=new TreeNode(marray[i]); mbst.insert(mtreenode); } mbst.inorderWalk(mbst.root); System.out.println(mbst.treelist); System.out.println(mbst.maxNode().key); System.out.println(mbst.minNode().key); System.out.println(mbst.search(13).key); System.out.println(mbst.successor(mbst.search(13)).key); System.out.println(mbst.predecessor(mbst.search(17)).key); mbst.treelist.clear(); mbst.delete(mbst.search(15)); mbst.inorderWalk(mbst.root); System.out.println(mbst.treelist); } }
