程序员的内功心法，你不来看看吗？

最近这阵工作，我越来越感受到基础知识能力的重要性。
之前都是在赶进度、做业务逻辑，逃避自己基础薄弱的事实。
最近下定决心，加强之前薄弱的基础。先从自己之前一直似是而非的搜索树的内容开始吧。

//二叉搜索树的节点定义

//查询算法

//查询极小值，一直向左查询，如果没有左节点，则认为当前节点最小 例子：A节点
public TreeNode<T> findMin(TreeNode<T> node){
    if (Objects.isNull(node.getLeft())) {
        return node;
    }
    return findMin(node.getLeft());
}
//查询极大值，一直向右查询，如果没有右节点，则认为当前节点最大 例子:Z节点
public TreeNode<T> findMax(TreeNode<T> node){
    if (Objects.isNull(node.getRight())) {
        return node;
    }
    return findMax(node.getRight());
}

public void add(T element) {
    if (element == null) {
        throw new RuntimeException("数据不能为NULL");
    }
    TreeNode<T> node = new TreeNode<>();
    node.data = element;
    if (Objects.isNull(root)) {
        root = node;
        return;
    }
    addImpl(root, node);
}
private void addImpl(TreeNode<T> root, TreeNode<T> node) {
    T val = root.data;
    T element = node.data;
    int sub = element.compareTo(val);
    //包含要插入的值，不处理
    if (sub == 0) {
        return;
    }
    //插入的值大于根节点的值，将新节点作为根节点的右子节点
    if (sub > 0) {
        TreeNode<T> right = root.getRight();
        if (Objects.isNull(right)) {
            root.setRight(node);
            return;
        }
        addImpl(right, node);
    } else {        //插入的值小于根节点的值，将新节点作为根节点的左子节点
        TreeNode<T> left = root.getLeft();
        if (Objects.isNull(left)) {
            root.setLeft(node);
            return;
        }
        addImpl(root.getLeft(), node);
    }
}

//移除最小的节点，将返回的值作为根节点
private TreeNode<T> deleteMin(TreeNode<T> node) {
    if (Objects.isNull(node.getLeft())) {   //没有左子节点，返回右子节点
        return node.getRight();
    }
    TreeNode<T> min = deleteMin(node.getLeft());    //递归左子树
    node.setLeft(min);
    return node;
}

//移除node节点的最大值，使用返回值替换原节点

//删除element的节点，返回根结点的引用
public TreeNode<T> delete(T element, TreeNode<T> node){
    if (Objects.isNull(node)) {
        return null;
    }
    T val = node.data;
    int res = val.compareTo(element);
    if (res < 0) {          //被删除节点在node的右子树
        TreeNode<T> rNode = delete(element, node.getRight());
        node.setRight(rNode);
    } else if (res > 0) {   //被删除节点在node的左子树
        TreeNode<T> lNode = delete(element, node.getLeft());
        node.setLeft(lNode);
    } else {                //node为被删除节点
        //包含一个子节点，使用子节点替换父节点
        if (Objects.isNull(node.getLeft())) {   
            return node.getRight();
        }
        if (Objects.isNull(node.getRight())) {
            return node.getLeft();
        }
        //左右节点均存在，使用后继节点代替，移除后继节点
        TreeNode<T> tmp = node;
        node = findMin(node.getRight());
        TreeNode<T> rNode = deleteMin(tmp.getRight());
        node.setRight(rNode);
        node.setLeft(tmp.getLeft());
    }
    return node;
}