1.二叉搜索树（Binary Search Tree）：

（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
在这里插入图片描述

2.建二叉树

static class TreeNode {
        public int val;//值
        public TreeNode left;//左边
        public TreeNode right;//右边

        public TreeNode(int val) {//构造方法，用于赋值
            this.val = val;
        }
    }

在这里插入图片描述

3.搜索操作

//搜索操作
    public TreeNode search(int key) {//查找key
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == key) {
                return cur;
            } else if(cur.val < key) {
                cur = cur.right;
            }else  {
                cur = cur.left;
            }
        }
        return null;
    }

4.插入操作

//插入操作
    public void insertTree(int val) {
    //如果二叉搜索树为空，直接插入值
        if(root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null) {
             if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(val);
        if(parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    }

5.删除操作

5.1：cur.lelf == null 左子树为空

cur 是root,则root = cur.right

在这里插入图片描述

cur不是root,cur是parent.left,则parent.left=cur.right

在这里插入图片描述

cur不是root,cur是parent.right,则parent.right=cur.right

在这里插入图片描述

5.2：cur.right == null 右子树为空

右子树为空与左子树为空大致相同，可以自行推理。

5.3：cur.lelf ！= null&&cur.right ！= null 左右子树都不为空

思路：

左树找最大数据
右树找最小数据

这里演示右树找最小数据

top1:找的树在左边
在这里插入图片描述
**top2:**找的树在右边

//删除操作
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;//查找相应结点然后删除
        while(cur != null) {
            if(cur.val == key) {
                removeNode(parent,cur);//删除函数
                return ;
            } else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
    }
    //通过removeNode函数进行删除
    public void removeNode(TreeNode parent,TreeNode cur) {
        if(cur.left == null) {//左子树为空
            if(cur == root) {
                root = cur.right;
            } else if(cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if(cur.right == null) {
            if(cur == root) {//右子树为空
                root = cur.left;
            } else if(cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = parent.left;
            }
        } else {//替罪羊的删除*//左边找最大，右边找最小
            TreeNode targetparent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
                targetparent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetparent.left == target) {
                targetparent.left = target.right;
            } else {
                targetparent.right = target.right;
            }
        }
    }