一、什么是二叉搜索树？

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

二、相关操作

属性

class Node {
    public int val;
    public Node left;
    public Node right;

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

2.1 查找

若根节点不为空：
如果根节点key == 查找key 返回true；
如果根节点key > 查找key 在其左子树查找
如果根节点key < 查找key 在其右子树查找
否则 返回false

public Node root = null;

    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val == key) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }

2.2 插入(建树操作)

1. 如果树为空树，即根 == null，直接插入
2. 如果树不为空树，按照查找逻辑确定插入位置，插入新节点

public boolean insert(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val < 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 (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

2.3 删除

1. 若删除的结点是叶结点：直接删除；
2. 若删除的结点仅有一个子树：直接将子树根节点替换到删除结点的位置上；
   直接用儿子结点替换删除结点是不会影响中序遍历有序性的。假设待删除结点只有左子树，则左子树上所有结点都是小于删除结点、大于或等于待删除结点的父结点的，因此用左子树的根替换待删除结点并不会破坏整棵树中序遍历的有序性。
3. 若删除的结点同时拥有左右子树：则将待删除结点的前驱结点（或后继结点）的值直接覆盖到待删除结点上，然后删除前驱结点（或后继结点）。这里的前驱结点是指“待删除结点的左子树中最大结点”，后继结点指的是“待删除结点右子树中最小结点”。

public void removeNode(Node cur, Node parent) {
        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 = cur.left;
            }
        } else {
            Node targetParent = cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

三、BinarySearchTree.java

class Node {
    public int val;
    public Node left;
    public Node right;

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

@SuppressWarnings({"all"})
public class BinarySearchTree {
    public Node root = null;

    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val == key) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }


	/**
	 * 插入
	 * @param key
	 * @return true 表示插入成功, false 表示插入失败
	 */
    public boolean insert(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val < 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 (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val == key) {
                // 这里开始删除
                removeNode(cur, parent);
                break;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur, Node parent) {
        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 = cur.left;
            }
        } else {
            Node targetParent = cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }
}