为了更加深入了解二叉搜索树，本人用Java写了个二叉搜索树，有兴趣的同学可以一起探讨探讨。
首先，二叉搜索树是啥？它有什么用呢？
二叉搜索树， 也称二叉排序树，它的每个节点的数据结构为1个父节点指针，1个左孩子指针，1个有孩子指针，还有就是自己的数据部分了，因为只有左右两孩子，所以才叫二叉树，在此基础上，该二叉树还满足另外一个条件：每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点。这样，我们队这棵树进行中序遍历，就能把key从小到大排序了……
那么问题来了，我都有线性表有链表了，我还要它干啥？两个字！效率！
相比线性表，你要搜索一个key，就要执行一次线性时间，算法复杂度为O(n)；而用二叉搜索树，算法效率是O(lgn)！这是很诱人的数字。下面我用Java实现以下二叉搜索树，你自然就明白为什么算法复杂度是O(lgn)了。
其次，写一个数据结构，自然而然也要实现对这个数据结构的增、删、查、改了。
下面是我的思路：
创建树：我是通过一个一个结点的插入来建立一棵二叉搜索树。
搜索结点：从根节点开始，进行key的比较，小了就往左走，大了就往右走，最后到了叶子结点都还没有的话，那么该树就不存在要搜索的结点了。
修改结点：修改其实就是查询，在查询之后把结点的数据部分给改了而已，这里我就不重复去实现了。
删除结点：这个应该就是最难的了，所以我有必要详细讲，先上图（不好意思，懒得用软件画图了，将就将就下哈）：
当我们要删除一个结点时，分如下几种情况：
此结点是叶子结点，这个最简单啦，直接把结点给释放掉就行了。（如图删除9）
此结点只有左孩子，这个也简单啦，直接把左子树替换过来就行了。（如图删除3）
此结点只有右孩子，同上。（如图删除8）
此结点有左右孩子，当出现这种情况时（如图删除7），我们就要找出该结点的后继结点（因为右子树肯定存在，所以找肯定在右子树中），然后把这个后继结点替换到要删除的结点中，然后继续执行对这个后继结点的删除操作（递归删除操作就行了）。
发现没？现在我的解题思路是自顶向下去分析……自顶向下，逐级求精是一个很伟大的思想！
现在问题来了！后继结点怎么求？我们来分析一下，当求一个结点的后继结点时，分为以下两种情况：
当该结点有右孩子时，后继结点就在右子树中，就是该右子树的最小结点
当该结点没有右孩子时，那后继结点就满足这个条件：该后继结点是该结点的祖先&&该结点位于该结点的左子树中（如图中的9的后继结点是12）
哎呀呀！问题又来了！最小结点咋办！很简单！
当求一棵树的最小结点时，那么就要从这颗树的根节点开始，一直往左子树走，就能找到它的最小结点了！
好了，现在问题逐步解决了！删除结点的功能也就完成了！
最后，没代码说个锤子，咱上代码！
首先，写个测试类：
public class Test {
public static void main(String[] args) {
int[] datas={12,4,5,7,4,8,3,2,6,9};
BinTree tree=new BinTree(datas);
tree.preOrderTraverse();//先序遍历
tree.midOrderTraverse();//中序遍历
tree.postOrderTraverse();//后序遍历
tree.insert(15); //插入结点
tree.search(7); //查询结点
tree.search(100); //查询一个不存在的结点
tree.getMax(); //获取最大值
tree.getMin(); //获取最小值
tree.getPre(7); //前驱结点
tree.getPre(2); //最前的前驱结点
tree.getPost(7); //后继结点
tree.getPost(15); //最后的后继结点
tree.delete(5); //删除结点
tree.delete(0); //删除一个不存在的结点
}
}
然后，二叉搜索树：