pta二叉搜索树的删除操作

### 关于二叉搜索树删除操作的实现 #### 删除操作概述 对于二叉搜索树中的删除操作，其复杂度取决于要删除节点的具体位置以及该节点是否有子节点。删除过程可以分为三种情况处理： - **删除叶子节点**：如果目标节点没有任何子节点，则可以直接将其移除。 - **删除只有一个子节点的节点**：此时只需让父节点指向待删节点唯一的那个孩子。 - **删除有两个子节点的节点**：这种情况下较为复杂一些，通常做法是从右子树中寻找最小值来替代被删除节点的位置；或者从左子树找最大值替换也可以达到相同效果[^1]。 #### Java代码示例 以下是基于上述原则编写的`BinarySearchTree`类的部分方法用于执行删除功能： ```java public void delete(int key){ root = deleteRec(root, key); } /* A recursive function to insert a new key in BST */ private TreeNode deleteRec(TreeNode root, int key) { /* Base Case: If the tree is empty */ if (root == null) return root; // Otherwise, recur down the tree if (key < root.val) root.left = deleteRec(root.left, key); else if (key > root.val) root.right = deleteRec(root.right, key); // if key is same as root's key, then This is the node to be deleted else { // Node with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // Node with two children: Get the inorder successor (smallest in the right subtree) root.val = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.val); } return root; } // Utility method to find minimum value from given node. int minValue(TreeNode root) { int minv = root.val; while (root.left != null) { minv = root.left.val; root = root.left; } return minv; } ``` 此段程序实现了完整的删除逻辑，并考虑到了所有可能的情况。通过递归的方式定位到需要删除的目标节点并按照既定策略调整指针关系完成实际删除动作[^2]。