Java实现二叉搜索树的插入、删除功能

public class Treenode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
    }

List<TreeNode> list = new ArrayList<>();
    public void inorder_traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorder_traversal(root.left);
        }
        list.add(root);
        if (root.right != null) {
            inorder_traversal(root.right);
        }
    }

public TreeNode search(TreeNode root, int val) {
        // 节点不为空，且不等于特定值
        while(root != null && root.val != val){
            if(root.val > val){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return root;
    }

 public TreeNode insertInto(TreeNode root, int val) {
        
        if (root == null) {
            // 树为空树的情况
            return new TreeNode(val);
        }
        // 一个临时节点指向根节点，用于返回值
        TreeNode tmp = root;
        TreeNode pre = root;
        
        while (root != null && root.val != val) {
            // 保存父节点
            pre = root;
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 通过父节点添加
        if (val > pre.val) {
            pre.right = new TreeNode(val);
        } else {
            pre.left = new TreeNode(val);
        }
        return tmp;
    }

public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode tmp = root;
        TreeNode pre = root;
        // 寻找要删除的节点
        while (root != null && root.val != key) {
            pre = root;
            if (key > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 找不到符合的节点值
        if (root == null) {
            return tmp;
        }
        // 只有一个子节点或者没有子节点的情况
        if (root.left == null || root.right == null) {
            if (root.left == null) {
                // 要删除的是根节点，返回它的子节点
                if (root == tmp) {
                    return root.right;
                }
                // 使用父节点连接子节点，实现删除当前节点
                if (pre.left == root) {
                    pre.left = root.right;
                } else {
                    pre.right = root.right;
                }
            } else {
                if (root == tmp) {
                    return root.left;
                }
                if (pre.left == root) {
                    pre.left = root.left;
                } else {
                    pre.right = root.left;
                }
            }
            return tmp;
        }
        // 第一种方式
        // 寻找中序遍历的后一个节点，也就是右子树进行中序遍历的第一个节点，右子树的最左节点
        pre = root;
        TreeNode rootRight = root.right;
        while (rootRight.left != null) {
            pre = rootRight;
            rootRight = rootRight.left;
        }
        // 节点的值进行交换
        int tmpVal = rootRight.val;
        rootRight.val = root.val;
        root.val = tmpVal;
        // 中序遍历的第一个节点肯定是没有左子树的，但是可能有右子树，将右子树连接到父节点上（相当于删除有一个子节点的节点）
        if (pre.left == rootRight) {
            pre.left = rootRight.right;
        }else {
            pre.right = rootRight.right;
        }
        // 第二种方式
        // 寻找中序遍历的前一个节点，也就是左子树进行中序遍历的最后一个节点，左子树的最右节点
//        pre = root;
//        TreeNode rootLeft = root.left;
//        while (rootLeft.right != null){
//            pre = rootLeft;
//            rootLeft = rootLeft.right;
//        }
//
//        int tmpVal = rootLeft.val;
//        rootLeft.val = root.val;
//        root.val = tmpVal;
//
//        // 中序遍历的最后一个节点肯定是没有右子树的，但是可能有左子树，将左子树连接到父节点上（相当于删除有一个子节点的节点）
//        if (pre.left == rootLeft) {
//            pre.left = rootLeft.left;
//        }else {
//            pre.right = rootLeft.left;
//        }
        return tmp;
    }