二叉搜索树

    public boolean find(int val){
        //根节点为空，说明是一棵空树
        if (root==null)return false;
        Node cur = root;
        while (cur!=null){
            if(val>cur.val){//说明在数的右边
                cur=cur.right;
            }else if(val== cur.val){//找到了
                return true;
            }else{//说明在树的左边
                cur=cur.left;
            }
        }
        //说明没有找到
        return false;
    }

    public boolean insert(int val){
        if (root==null){
            //头结点为空，则刚插入进来的节点就是根节点
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = null;//用来记录cur上一个位置
        while (cur!=null){
            if (val>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                return false;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
        Node node = new Node(val);
        if (val>parent.val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        return true;
    }

    public void remove(int val){
        if(root==null)return;
        Node cur = root;
        Node parent = null;
        //找要删除的值
        while (cur!=null){
            if (val>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(val== cur.val){
                toremove(cur,parent);
                break;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
    }
    public void toremove(Node cur,Node parent){
        if(cur.left==null){
            if(cur.left==null){
                if(cur==root){
                    root=root.right;
                }
                if(parent.left==cur){
                    parent.left=cur.right;
                }
                if (parent.right==cur){
                    parent.right=cur.right;
                }
            }else if(cur.right==null){
                if(cur==root){
                    root=root.right;
                }
                if(parent.right==cur){
                    parent.right=cur.left;
                }
                if(parent.left==cur){
                    parent.left=cur.left;
                }else{
                    Node tmp = cur;
                    Node tag = cur.right;
                    while (tag.left!=null){
                        tmp=tag;
                        tag=tag.left;
                    }
                    //交换
                    cur.val= tag.val;
                    //删除tag
                    if (tmp.right==tag){
                        tmp.right=tag.right;
                    }else{
                        tmp.left=tag.right;
                    }
                }
        }
    }