二叉搜索树是以一颗二叉树来组织的。这棵树可以使用链表数据结构表示。每个节点除了key和卫星数据外。每个节点包含属性left、right、parent。二叉搜索树中树，如果x是一个节点，则x.left.key < x.key < x.right.key。
中序遍历、前序遍历、后续遍历
InorderTreeWalk(x) { if(x != null) { InorderTreeWalk(x.left); print x.key; InorderTreeWalk(x.right); } } PreorderTreeWalk(x) { if(x != null) { print x.key; InorderTreeWalk(x.left); InorderTreeWalk(x.right); } } PostorderTreeWalk(x) { if(x != null) { InorderTreeWalk(x.left); InorderTreeWalk(x.right); print x.key; } }
查询-递归
TreeSearch(x, k) { if(x == null || k == x.key) return x; if(k < x.key) return TreeSearch(x.left, k); return TreeSearch(x.right, k); }
查询-循环
TreeSearch(x, k) { while(x != null && k != x.key) { if(k < x.key) x = x.left; else x = x.right; } return x; }
最大
TreeMaximum(x) { while(x != null) { x = x.right; } return x; }
最小
TreeMinimum(x) { while(x != null) { x = x.left; } return x; }
后继和前驱
右子树不空，则x后继为右子树最小节点。右子树为空，那x后继就是其最底层祖先。总的来说就是，后继就是x大的最小的数。
TreeSuccessor(x) { if(x.right != null) return TreeMinimum(x.right); y=x.parent; while(y != null && x==y.right) { x=y; y=y.parent } return y; }
插入
TreeInsert(T, z) { y=null; x=T.root; while(x != null) { y=x; if(z.key < x.key) x=x.left; else x=x.right;
} x.parent=y; if(y == null) T.root=z; else if(z.key < y.key) y.left=z; else y.right=z; } }
删除z
Transplant(T, u, v) { if (u.parent == null) t.root = v else if (u == u.parent.left) u.p.left = v; else u.p.right = v; if (v != null) v.parent = u.partent; } TreeDelete(T, z) { if (z.left == null) Transplant(T, z, z.right); else if (z.right == null) Transplant(T, z, z.left); else { y = TreeMinimum(z.right);//z有双子，则后继为右侧最小 if (y.parent != z) { Transplant(T, y, y.right); y.right = z.right; y.right.parent = y; } Transplant(T, z, y); y.left = z.left; y.left.parent = y; } }
原文：http://www.cnblogs.com/qiusuo/p/5218777.html