一、二叉排序树核心特性

1. 左子树所有节点值<根节点值
2. 右子树所有节点值>根节点值
3. 中序遍历结果为升序数组
4. 核心操作：新增、查找、遍历、删除（重难点）

二、删除节点三大场景（核心思路）

设待删除节点为target

场景 1：target 是叶子节点（无左、无右孩子）

直接把父节点指向 target 的引用置为null，释放节点。

场景 2：target 只有单侧子树（只有左 / 只有右）

用 target 唯一的子节点顶替 target，父节点直接指向该孩子。

场景 3：target 同时有左、右子树（最复杂）

两种经典方案任选一种，这里采用右子树最小值顶替：

1. 找到 target右子树最小节点（右子树最左下节点）
2. 把最小节点的val赋值给 target（覆盖待删值）
3. 递归删除右子树中原来的最小节点（最小节点一定满足场景 1/2）

替代方案：取左子树最大值顶替，逻辑完全对称。

三、完整 Java 代码实现

java

运行

/** * 二叉排序树节点类 */ class BSTNode { int val; BSTNode left; BSTNode right; public BSTNode(int val) { this.val = val; this.left = null; this.right = null; } } /** * 二叉排序树工具类，封装增、删、查、遍历 */ public class BinarySortTree { private BSTNode root; public BinarySortTree() { this.root = null; } // ===================== 1. 添加节点 ===================== public void add(int val) { root = addRecursion(root, val); } /** * 递归新增节点 */ private BSTNode addRecursion(BSTNode node, int val) { // 递归终止：找到空位，新建节点返回 if (node == null) { return new BSTNode(val); } // 小于当前节点，往左子树递归 if (val < node.val) { node.left = addRecursion(node.left, val); } // 大于当前节点，往右子树递归 else if (val > node.val) { node.right = addRecursion(node.right, val); } // 相等：二叉排序树不允许重复值，直接返回原节点 else { return node; } return node; } // ===================== 2. 查找节点 ===================== public boolean search(int val) { return searchRecursion(root, val); } private boolean searchRecursion(BSTNode node, int val) { if (node == null) { return false; } if (val == node.val) { return true; } else if (val < node.val) { return searchRecursion(node.left, val); } else { return searchRecursion(node.right, val); } } // ===================== 3. 中序遍历（升序） ===================== public void inOrder() { System.out.print("中序遍历(升序)："); inOrderRecursion(root); System.out.println(); } private void inOrderRecursion(BSTNode node) { if (node == null) return; inOrderRecursion(node.left); System.out.print(node.val + " "); inOrderRecursion(node.right); } // ===================== 4. 删除节点（核心方法） ===================== public void delete(int val) { root = deleteRecursion(root, val); } /** * 递归删除目标值节点，返回处理后的子树根节点 * @param node 当前递归节点 * @param val 待删除值 * @return 删除后该分支新根 */ private BSTNode deleteRecursion(BSTNode node, int val) { // 递归终止：未找到待删除节点 if (node == null) { return null; } // 1. 待删值 < 当前节点，向左递归删除 if (val < node.val) { node.left = deleteRecursion(node.left, val); return node; } // 2. 待删值 > 当前节点，向右递归删除 else if (val > node.val) { node.right = deleteRecursion(node.right, val); return node; } // 3. val == node.val，找到待删除节点，分3种情况处理 else { // 情况1：叶子节点，直接删除返回null if (node.left == null && node.right == null) { return null; } // 情况2：只有右孩子，右孩子顶替当前节点 else if (node.left == null) { return node.right; } // 情况2：只有左孩子，左孩子顶替当前节点 else if (node.right == null) { return node.left; } // 情况3：同时存在左右子树，取右子树最小值顶替 else { // 步骤1：获取右子树最小节点 BSTNode minNode = getMinNode(node.right); // 步骤2：用最小值覆盖待删除节点的值 node.val = minNode.val; // 步骤3：递归删除右子树中原最小节点 node.right = deleteRecursion(node.right, minNode.val); return node; } } } /** * 获取一棵子树中的最小节点（最左下节点） */ private BSTNode getMinNode(BSTNode node) { while (node.left != null) { node = node.left; } return node; } // 测试主方法 public static void main(String[] args) { BinarySortTree bst = new BinarySortTree(); // 构建树：5,3,7,2,4,6,8 int[] arr = {5, 3, 7, 2, 4, 6, 8}; for (int num : arr) { bst.add(num); } bst.inOrder(); // 输出：2 3 4 5 6 7 8 System.out.println("=== 删除叶子节点 2 ==="); bst.delete(2); bst.inOrder(); // 3 4 5 6 7 8 System.out.println("=== 删除单侧子树节点7（只有右孩子8） ==="); bst.delete(7); bst.inOrder(); // 3 4 5 6 8 System.out.println("=== 删除左右都有子树的根节点5 ==="); bst.delete(5); bst.inOrder(); // 3 4 6 8 } }

四、代码逻辑逐段解析

1. 节点类 BSTNode

存储数值、左右子节点引用，基础实体类。

2. add 新增逻辑

递归向下查找空位：

• 小于当前节点 → 左子树
• 大于当前节点 → 右子树
• 相等直接忽略（不支持重复值）

3. deleteRecursion 删除核心递归

1. 递归定位待删除节点：小往左、大往右；
2. 匹配到目标节点后分 3 种场景：
   1. 无左右孩子（叶子）：return null，父节点指向空；
   2. 只有单侧孩子：直接返回唯一子节点，完成顶替；
   3. 左右孩子都存在：
      • getMinNode找到右子树最小值；
      • 覆盖当前节点值，等价于 “删除原节点，替换成最小值”；
      • 递归删除右子树里原来的最小节点（最小节点必然无左孩子，属于场景 1/2）。

4. getMinNode 工具方法

循环遍历左子树，直到左为空，得到当前子树最小值。

5. 中序遍历验证

二叉排序树中序遍历一定升序，用来校验增删是否正确。

五、运行输出结果

plaintext

中序遍历(升序)：2 3 4 5 6 7 8 === 删除叶子节点 2 === 中序遍历(升序)：3 4 5 6 7 8 === 删除单侧子树节点7（只有右孩子8） === 中序遍历(升序)：3 4 5 6 8 === 删除左右都有子树的根节点5 === 中序遍历(升序)：3 4 6 8

六、拓展补充

1. 删除方案替换：如果想用「左子树最大值顶替」，写getMaxNode取左子树最右节点即可；
2. 非递归删除：递归写法简洁易理解，面试优先写递归；非递归需要额外记录父节点、标记左右分支，代码冗余；
3. 重复值处理：如需支持重复数字，可在节点新增count计数，删除时先减计数，计数为 0 再执行删除逻辑。