二叉搜索树的Java实现

一.树的概念

树的定义：树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树的特点：
1.每个结点有零个或多个子结点；
2.没有父结点的结点为根结点；
3.每一个非根结点只有一个父结点；
4.每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树;
补：树的检索效率较高！

结点的度：
一个结点含有的子树的个数称为该结点的度； —如E有两个子树，度为2； F有 KLM三个子树，度为3。根节点的度为6。

叶结点： 度为0的结点称为叶结点，也可以叫做终端结点 ，如 B、C

分支结点： 度不为0的结点称为分支结点，即非终端结点

结点的层次： 从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推— 如 P、Q为第四层

结点的层序编号：将树中的结点，按照从上层到下层，然后同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。

树的度： 树中所有结点的度的最大值 —上图中根节点的度最大，也有可能子节点的度更大
树的高度(深度)： 树中结点的最大层次 —4

森林：
m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根
结点，森林就变成一棵树

孩子结点：
一个结点的直接后继结点称为该结点的孩子结点—D是A的孩子结点，H不是。
双亲结点(父结点)：
一个结点的直接前驱称为该结点的双亲结点 —-E为I的父节点
兄弟结点：
同一双亲结点的孩子结点间互称兄弟结点 —-K、L、M的父节点都是F，即K、L、M是兄弟结点

二.二叉树

定义：二叉树就是度不超过2的树 (每个结点最多有两个子结点)
满二叉树：
如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。

完全二叉树：
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
即添加元素的时候都是从左往右依次放，保证叶结点只能出现在最下层or此下层。——L、G，倒数第三层就没有叶结点了

三.二叉查找树的实现

使用链表来实现二叉查找树，链表的首结点即为root根节点

BinaryTree类的实例变量和Node结点内部类 ：

public class BinaryTree <Key extends Comparable,Value> { //泛型继承接口用的extends而不是 implements !

    private Node root; //根节点
    private int N;

    private class Node{ //结点内部类
        private Key key;
        private Value value;
        private Node left; //当前结点的左结点
        private Node right; //当前结点的右结点

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

put方法：
1.如果当前结点中没有任何一个结点，则直接把新结点当做根结点使用 （递归终止条件）
2.如果当前树不为空，则从根结点开始：
2.1如果新结点的key＜当前结点的key，则继续找当前结点的左子结点；
2.2如果新结点的key＞当前结点的key，则继续找当前结点的右子结点；
2.3如果新结点的key等于当前结点的key，则树中已经存在这样的结点，覆盖该结点的value值即可。
put和get都有两个重载的方法，第一个是public修饰供外部使用，第二个private修饰的 有树结点参数的重载的方法是为了内部递归调用，将不同的子树结点作为当前结点依次去和添加的元素进行比较，直到再没有子节点时，用添加的K、V创造为新结点，作为当前结点的子节点，递归结束。

public void put(Key key,Value value){ //向整个树中插入一个键值对
        root = put(root, key, value);// 调用重载的put，从root开始，把根节点传入参数x（指定的某树x）
        //再将新的树更新为根节点root
    }

private Node put(Node x, Key key,Value value){ //在指定树x中添加一个键值对
        //如果x为空，x直接作为根节点
            if(x==null){
                N++;
                return new Node(key,value,null,null);  //返回新的根节点作为上一层的子节点， 递归出口。
            }

        //如果x不为空
        int com = key.compareTo(x.key); //先比较
            if(com>0){//如果key大于x结点的键，就继续找x结点的右子树
                x.right= put(x.right, key, value);
                //递归调用，把x的右子树作为当前结点再进行比较并put，如果右子树为null，则key作为x的右子树
                //在添加了新的子结点后，树结构发生了变化！ 要将当前结点进行更新。而get方法没有改变树结构，就不需要更新。


            }else if(com<0) {//如果key小于x结点的键，就继续找x结点的左子树
                x.left=put(x.left,key,value);
                //递归调用，把x的左子树作为当前结点再进行比较并put，如果左子树为null，则key作为x的右子树

            }else{//如果key等于x结点的键，就覆盖x结点的值
                x.value=value;
                }
        return x;  //返回更改过的x
    }

get方法 ：
查询方法get实现思想：
从根节点root开始：
1.如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
2.如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
3.如果要查询的key等于当前结点的key，则树中返回当前结点的value。
get方法要根据key查找出value，需要从整个树查找，所以入口是root；从根节点开始依次比较key，递归调用重载的get方法，直到发现没有key相同的结点返回null（递归结束条件1）； 或者找到key相同的结点就返回该结点的value（递归结束条件1）。

public Value get(Key key){  //根据key找出value，需要从整个树查找，所以入口是root
        return get(root,key); //调用重载的get方法，从根节点root开始找

    }

private Value get(Node x,Key key){ //从指定的树x中，根据key找出value
    if(x==null) {//如果x为null
        return null; //递归到最后没有key相同结点，直接返回null，递归出口1
    }else{ //如果x不为null时

        int com = key.compareTo(x.key); //先比较
        if(com>0){//如果key大于x结点的键，就继续找x结点的右子树
           return get(x.right, key);
            //递归调用，把x的右子树作为当前结点再进行比较并get，如果右子树为null，则返回null；或者找到key相同的就返回value

        }else if(com<0) {//如果key小于x结点的键，就继续找x结点的左子树
            return get(x.left,key);
            //递归调用，把x的左子树作为当前结点再进行比较并put，如果左子树为null，则返回null;或者找到key相同的就返回value

        }else{//如果key等于x结点的键，就返回value， 递归出口2
            return x.value;
        }
      }
    }

delete删除方法：

1.先找到被删除结点；（这部分和get代码类似）
2.找到被删除结点右子树中的最小结点minNode
3.删除右子树中的最小结点minNode
4.让被删除结点的左子树 变成 最小结点minNode的左子树，让被删除结点的右子树 变成 最小结点minNode的右子
树
5.让被删除结点的父节点指向最小结点minNode
（即让要删除的结点x的右子节点的最小结点minNode，代替被删除的结点）
（若要删除的结点x（如14）没有右子树，则让左子树的最大结点（12）代替x（14）。 左子树的最大结点即x的左结点）
（若要删除的结点x没有左子树，则让右边子树的最小结点代替x。）

 public void delete(Key key){// 删除结点 ※
        delete(root,key);    //需要从整个树查找，所以从root开始
    }

    private Node delete(Node x,Key key){// 删除指定树x上的键值对，并返回该树
        // 树x为null，即找不到该结点,直接返回null
        if(x==null){
            return null;
        //即最后没有找到该结点，返回null，即树并没有任何变化！

        }else{
            N--;
            int com = key.compareTo(x.key); //先比较
            if(com>0){//如果key大于x结点的键，就继续找x结点的右子树
                x.right= delete(x.right, key);
                //递归调用，把x的右子树作为当前结点再进行比较，如果右子树为null，则返回null；或者找到key相同的进入删除部分的逻辑，
                //最后若删除了结点，则树的结构改变，需要更新x.right

            }else if(com<0) {//如果key小于x结点的键，就继续找x结点的左子树
                x.left= delete(x.left,key);
                //同理

            }else{//如果key等于x结点的键，就用要删除的结点x的右子树的最小结点代替 要删除的结点x
                //删除结点的逻辑: 令右子树中最小的结点minNode 替换被删除的结点

                if(x.right==null){ //若没有右结点，则令x的左结点代替X
                return x.left;
                }

                if(x.left==null){   //若没有左结点，则令x的右结点代替X
                    return x.right;
                }
                //以上两种情况特殊，和两边都有结点的情况不一样

                //如果左右结点都不为空，找有右子树的最小值来代替x；
                //找minNode：即右子树最左边的结点，只需要在右子树中一直找左子结点

                Node minNode=x.right;//默认为右子树的第一个
                while(minNode.left!=null){
                    minNode=minNode.left;
                }
                //删除minNode，
                Node n=x.right;
                while(n.left.left!=null){
                    if(n.left.left==null){ //即证明n为倒数第二个结点
                        n.left=null; //即删除了一个结点minNode
                    }else{
                        n=n.left; //如果还没到则继续向下更新n
                    }
                }
                //让x结点的左子树成为minNode的左子树
                    minNode.left=x.left;
                //让x节点的右子树成为minNode的右子树
                    minNode.right=x.right;
                //让x结点的父结点指向minNode
                    x=minNode; //把x重新赋值为minNode，此时minNode的左右结点已更新

            }
                return x;
        }
    }

二叉树的其他便捷方法：

• 查找二叉树中最小的键key： 查找最小即从根节点开始找子左边的结点

//查找树中最小的key
    public Key min(){
        return min(root).key; //查找则需要从根节点root开始查找
    }

    //在指定的树中找出最小key所在的结点
    public Node min(Node x){
        if(x.left!=null){
            return min(x.left);  //递归

        }else{   //x.left=null ，即已经找到最小结点，递归结束条件
            return x;
        }
    }