为了更加深入了解二叉搜索树，本人用Java写了个二叉搜索树，有兴趣的同学可以一起探讨探讨。
首先，二叉搜索树是啥？它有什么用呢？
二叉搜索树， 也称二叉排序树，它的每个节点的数据结构为1个父节点指针，1个左孩子指针，1个有孩子指针，还有就是自己的数据部分了，因为只有左右两孩子，所以才叫二叉树，在此基础上，该二叉树还满足另外一个条件：每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点。这样，我们队这棵树进行中序遍历，就能把key从小到大排序了……
那么问题来了，我都有线性表有链表了，我还要它干啥？两个字！效率！
相比线性表，你要搜索一个key，就要执行一次线性时间，算法复杂度为O(n)；而用二叉搜索树，算法效率是O(lgn)！这是很诱人的数字。下面我用Java实现以下二叉搜索树，你自然就明白为什么算法复杂度是O(lgn)了。
其次，写一个数据结构，自然而然也要实现对这个数据结构的增、删、查、改了。
下面是我的思路：
?
?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);? ? ? ? //删除一个不存在的结点
? ? }
}
然后，二叉搜索树：
public class BinTree {
? ? Node root=null;
? ? private class Node{
? ? ? ? Node parent=null;
? ? ? ? Node leftChild=null;
? ? ? ? Node rightChild=null;
? ? ? ? int key;
? ? ? ? public Node(int data) {
? ? ? ? ? ? this.key=data;
? ? ? ? }
? ? }
? ? public BinTree(int[] datas) {
? ? ? ? buildTree(datas);
? ? }
? ? private void buildTree(int[] datas) {
? ? ? ? for (int i = 0; i < datas.length; i++) {
? ? ? ? ? ? Node node=new Node(datas[i]);
? ? ? ? ? ? insertNode(node);
? ? ? ? }
? ? }
? ? private void insertNode(Node node) {? ? //插入结点
? ? ? ? Node next=this.root;? ?
? ? ? ? Node cur=null;? ? //用来保存当前结点
? ? ? ? while(next!=null){? ? //当到达叶子结点时，确认位置！
? ? ? ? ? ? cur=next;
? ? ? ? ? ? if(node.key>=cur.key){
? ? ? ? ? ? ? ? next=next.rightChild;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? next=next.leftChild;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? node.parent=cur;? ? //插入该结点！
? ? ? ? if(cur==null){
? ? ? ? ? ? this.root=node;? //该树为空树，所以这个是根节点
? ? ? ? }else if(node.key>=cur.key){
? ? ? ? ? ? cur.rightChild=node;
? ? ? ? }else{
? ? ? ? ? ? cur.leftChild=node;
? ? ? ? }
? ? }
? ? /*
? ? * 插入一个数
? ? */
? ? public void insert(int data){? ?
? ? ? ? Node node=new Node(data);
? ? ? ? System.out.println("插入结点："+data);
? ? ? ? insertNode(node);
? ? ? ? this.midOrderTraverse();
? ? }
? ?
? ? /*
? ? * 先序遍历
? ? */
? ? public void preOrderTraverse(){? ?
? ? ? ? System.out.println("先序遍历：");
? ? ? ? preOrderTraverse(root);
? ? ? ? System.out.println();
? ? }
? ? private void preOrderTraverse(Node node){? ? //先序遍历
? ? ? ? if(node!=null){
? ? ? ? ? ? System.out.print("-"+node.key+"-");
? ? ? ? ? ? preOrderTraverse(node.leftChild);
? ? ? ? ? ? preOrderTraverse(node.rightChild);
? ? ? ? }
? ? }
? ? /*
? ? * 中序遍历
? ? */
? ? public void midOrderTraverse(){? ?
? ? ? ? System.out.println("中序遍历：");
? ? ? ? midOrderTraverse(root);
? ? ? ? System.out.println();
? ? }
? ? private void midOrderTraverse(Node node){? ? //中序遍历
? ? ? ? if(node!=null){
? ? ? ? ? ? midOrderTraverse(node.leftChild);
? ? ? ? ? ? System.out.print("-"+node.key+"-");
? ? ? ? ? ? midOrderTraverse(node.rightChild);
? ? ? ? }
? ? ? ?
? ? }
? ?
? ? /*
? ? * 后序遍历
? ? */
? ? public void postOrderTraverse(){
? ? ? ? System.out.println("后序遍历：");
? ? ? ? postOrderTraverse(root);
? ? ? ? System.out.println();
? ? }
? ? private void postOrderTraverse(Node node){? ? //后序遍历
? ? ? ? if(node!=null){
? ? ? ? ? ? System.out.print("-"+node.key+"-");
? ? ? ? ? ? postOrderTraverse(node.leftChild);
? ? ? ? ? ? postOrderTraverse(node.rightChild);
? ? ? ? }
? ? }
? ?
? ? /*
? ? * 搜索结点
? ? */
? ? public void search(int data){? ?
? ? ? ?