通过Java函数实现搜索二叉树的插入和删除操作

搜索二叉树是一种特殊的二叉树，其中每个节点都包含一个键，且所有节点的键都大于其左子树中所有节点的键，小于其右子树中所有节点的键。

搜索二叉树的插入和删除操作都是相对比较简单直接的，下面我们就通过Java函数来实现这些操作。

插入操作

插入操作的大致流程如下：

1.首先，比较要插入的节点的键值与当前节点的键值大小，如果小于当前节点，则继续在当前节点的左子树中递归搜索，如果大于或等于当前节点，则在当前节点的右子树中递归搜索。

2.如果搜索到的位置为null，则在此位置新建一个节点，并把键值赋为要插入的键值。

3.如果搜索到的位置的键值与要插入的键值相同，则说明要插入的节点已经存在，不需要再次插入。

4.最后，需要更新整棵树的高度。

下面是Java函数实现：

public TreeNode insert(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    }
    return root;
}

删除操作

删除操作是相对复杂一些的，需要分几种情况进行处理，大致流程如下：

1.首先，通过比较要删除的节点的键值与当前节点的键值大小，递归地查找要删除的节点。

2.如果找到了要删除的节点，则需要考虑三种情况：

（1）要删除的节点没有子节点：直接删除即可。

（2）要删除的节点只有一个子节点：把该子节点上移一层替代要删除的节点。

（3）要删除的节点有两个子节点：先找到该节点的中序后继节点，即该节点右子树中最小的节点，然后把该中序后继节点的值复制到要删除的节点中，并删除该中序后继节点。

3.最后，需要更新整棵树的高度。

下面是Java函数实现：

public TreeNode delete(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        if (root.left == null && root.right == null) {
            root = null;
        } else if (root.left == null) {
            root = root.right;
        } else if (root.right == null) {
            root = root.left;
        } else {
            TreeNode successor = getSuccessor(root.right);
            root.val = successor.val;
            root.right = delete(root.right, successor.val);
        }
    }
    return root;
}
private TreeNode getSuccessor(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

总结

通过Java函数实现搜索二叉树的插入和删除操作是相对比较简单的，需要注意的是，对于删除操作，要分清三种情况，并且要注意更新整棵树的高度。