排序二叉树　　

　　排序二叉树的概念是按照中序遍历的方式 left < D < right，这样有序的插入排序,一些基本的概念就不说了。

代码实现:
　　新增：如果比当前节点小就left / 否则right --- 在这个前提下需要判断left/right == null直接插入否则需要递归遍历
　　　　if(node.no < hour.no){

            if(hour.left == null){
                hour.left = node;
            }else {
                addNode_1(node,hour.left);
            }
        }
　　    这里的就是如果小于当前节点的代码,如果大于只需要修改left变成right即可
　　删除: 
　　　　删除的情况就会复杂一点了
　　　　1.如果删除的节点是非叶子节点
　　　　2.如果删除的节点是叶子节点但是子节点只有left || right
 　　　 3.如果删除的节点是叶子节点但是有left && right
   1.1需要删除的节点是否存在
   1.2二叉树和单链表是很类似的(这里可以去看一下区别),有一个很明显的缺点就是他们是没法知道parent的节点的,所以当需要删除的时候我们需要去查找到当前节点的parent节点
　　1.1和1.2我们可以抽取出来改成两个方法
   非叶子节点我们只需要找到parent确定是left还是right就可以进行删除了
　　叶子结点的第一种情况只需要parent.left/right = 当前节点.left/right
   叶子结点的第二种情况需要找打当前节点的right节点的最小值/left节点的最大值即可

/**
 * 排序二叉树
 * */
public class sortTree {

    Node head;
    Node pre;

    class Node{
        private Node left;
        private Node right;
        int no;

        public Node(int no){
            this.no = no;
        }

        public String toString() {
            return "节点是:"+no;
        }

        public void zx_bl(){
            if(this.left != null){
                this.left.zx_bl();
            }
            System.out.println(this);
            if(this.right != null){
                this.right.zx_bl();
            }
        }

        /**
         * 查找是否有当前的节点
         * 如果找到了就返回当前节点
         * */
        public Node cz_1(int no){
            Node hour = null;
            if(this.no == no){
                return hour = this;
            }
            else if(this.left != null && this.no > no){
                return hour = this.left.cz_1(no);
            } else{
                if(this.right == null){
                    return  hour;
                }
                return  hour = this.right.cz_1(no);
            }
        }

        /**
         * 找到父节点
         * 我这里的root节点未判定,判定在进行删除的时候做了判断,这里是可以修改的
         * */
        public Node cz_parent(int no){
            Node hour = null;
            if((this.left!=null && this.left.no == no) || (this.right!=null && this.right.no == no)){
                return hour = this;
            } else if(this.left !=null && this.no > no){
                return hour = this.left.cz_parent(no);
            } else{
                if(this.right ==null){
                    return hour;
                }
                return hour = this.right.cz_parent(no);
            }
        }

        /**
         * 找到right的最小值 / left的最大值
         * */
        public Node end(){
            Node hour = null;
            if(this.left == null){
                del_1(this.no);
                return hour = this;
            }
            if(this.left != null){
               return hour = this.left.end();
            }
            return hour;
        }
    }

    /**
     * 删除操作
     * 1.叶子节点
     * 2.单个节点:
     *     2.1如果删除的节点子节点在left 2.2如果删除的子节点在右边
     * 3.两个节点:
     *     3.1如果删除的节点是左边的
     * */
    public Node del_1(int no){
        if(head == null || head.no == no){
            return head = new Node(-1);
        }
        Node ch = head.cz_1(no);
        if(ch == null){
            return null;
        }
        Node par = head.cz_parent(no);
        if (ch.left == null && ch.right == null){ //删除的节点为空节点
            if(par.left.no == no){
                par.left = null;
            }else{
                par.right = null;
            }
            return head;
        }else if(ch.left != null && ch.right != null){ //删除的节点为一棵树 我们需要找到最大的一个数
            if(par.left.no == no){
                Node hour = ch.right.end();
                hour.left = ch.left;
                hour.right = ch.right;
                par.left = hour;
            }else{
                Node hour = ch.right.end();
                hour.left = ch.left;
                hour.right = ch.right;
                par.right = hour;
            }
            return head;
        }
        else{ //删除的节点为半棵树  如果par为空的话会出现bug
            if(ch.left!=null){
                par.left = ch.left;
            }else if(ch.right != null){
                par.right = ch.right;
            }
            return head;
        }
    }


    /**
     * 添加节点
     * */
    public Node addNode(int no){
        Node node = new Node(no);
        Node hour = head;
        if(head == null){
            head = node;
            return hour;
        }else{
            hour = addNode_1(node,hour);
        }
        return hour;
    }

    /**
     * 添加节点
     * 1.如果小于当前节点并且left为空直接添加 2.如果大于当前节点并且right为null直接添加
     * */
    public Node addNode_1(Node node,Node hour){
        if(node.no < hour.no){
            if(hour.left == null){
                hour.left = node;
            }else {
                addNode_1(node,hour.left);
            }
        }

        if(node.no > hour.no){
            if(hour.right == null){
                hour.right = node;
            }else {
                addNode_1(node,hour.right);
            }
        }
        return hour;
    }

    /**
     * 这种删除是不管节点下是否有叶子或者非叶子节点直接删除。pre = 上一个节点
     * */
    public void delete_1(int no,Node node){

        if(node != null && pre != null && pre.left.no == no){
            pre.left = null;
            return;
        }

        if(node != null && pre != null && pre.right.no == no){
            pre.right = null;
            return;
        }

        if(node != null && node.no > no){
            pre = node;
            delete_1(no,node.left);
        }
        if(node != null && node.no < no){
            pre = node;
            delete_1(no,node.right);
        }

    }

}