Java BST递归删除双子女节点时误删子树问题求助

我实现的Java二叉搜索树（BST）递归删除方法，在删除拥有两个子节点的节点时出现异常，会误删整个子树。反复梳理逻辑但未定位到错误，以下是包含后继节点（successor）方法的代码及测试失败的具体结果。

代码实现 #

public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException();
    }
    BSTNode<T> dummy = new BSTNode<>(null);
    root = hRemove(root, data, dummy);
    return dummy.getData();
}

private BSTNode<T> hRemove(BSTNode<T> current, T data, BSTNode<T> dummy) {
    if (current == null) {
        throw new NoSuchElementException();
    } else if (data.compareTo(current.getData()) > 0) {
        current.setRight(hRemove(current.getRight(), data, dummy));
    } else if (data.compareTo(current.getData()) < 0) {
        current.setLeft(hRemove(current.getLeft(), data, dummy));
    } else {
        dummy.setData(current.getData());
        size--;
        if ((current.getLeft() == null) && (current.getRight() == null)) {
            return null;
        } else if (current.getLeft() != null) {
            return current.getLeft();
        } else if (current.getRight() != null) {
            return current.getRight();
        } else {
            BSTNode<T> dummy2 = new BSTNode(null);
            current.setRight(suc(current.getRight(), dummy2));
            current.setData(dummy2.getData());
        }
    }
    return current;
}

private BSTNode<T> suc(BSTNode<T> current, BSTNode<T> dummy2) {
    if (current.getLeft() == null) {
        dummy2.setData(current.getData());
        return current.getRight();
    } else {
        current.setLeft(suc(current.getLeft(), dummy2));
        return current;
    }
}

测试失败结果 #

多个测试用例显示，删除目标节点后实际树结构与预期不符，例如：

• 删除根节点1（左右子节点为0和2），预期树为以2为根、左子节点0，实际仅剩节点0；
• 删除节点4（位于树6->2->4，左右子节点3和5），预期树中4被5替代，实际4的位置被3替代；

详细测试结果如下：

[测试失败: remove] [-0.31] : 删除树中的1后内容不符合预期。

+----------------+
| 初始树:  |
|                |
|   1            |
|  /   \         |
| 0     2        |
|                |
|                |
| 预期树: |
|                |
|   2            |
|  /             |
| 0              |
|                |
|                |
| 实际树:   |
|                |
| 0              |
+----------------+
 

[测试失败: remove] [-0.31] : 删除树中的1后内容不符合预期。

+---------------------------------+
| 初始树:                   |
|                                 |
|               1                 |
|        /               \        |
|       0                 4       |
|                    /            |
|                   3             |
|                  /              |
|                 2               |
|                                 |
|                                 |
| 预期树:                  |
|                                 |
|       2                         |
|    /       \                    |
|   0         4                   |
|          /                      |
|         3                       |
|                                 |
|                                 |
| 实际树:                    |
|                                 |
| 0                               |
+---------------------------------+
 

[测试失败: remove] [-0.31] : 删除树中的1后内容不符合预期。

+-----------------+
| 初始树:   |
|                 |
|       1         |
|    /       \    |
|   0         2   |
|              \  |
|               3 |
|                 |
|                 |
| 预期树:  |
|                 |
|   2             |
|  /   \          |
| 0     3         |
|                 |
|                 |
| 实际树:    |
|                 |
| 0               |
+-----------------+
 

[测试失败: remove] [-0.31] : 删除树中的1后内容不符合预期。

+-----------------------------------------------------------------+
| 初始树:                                                   |
|                                                                 |
|                               1                                 |
|                /                               \                |
|               0                                 5               |
|                                        /                        |
|                                       4                         |
|                                    /                            |
|                                   2                             |
|                                      \                          |
|                                       3                         |
|                                                                 |
|                                                                 |
| 预期树:                                                  |
|                                                                 |
|               2                                                 |
|        /               \                                        |
|       0                 5                                       |
|                    /                                            |
|                   4                                             |
|                  /                                              |
|                 3                                               |
|                                                                 |
|                                                                 |
| 实际树:                                                    |
|                                                                 |
| 0                                                               |
+-----------------------------------------------------------------+
 

[测试失败: remove] [-0.31] : 删除树中的4后内容不符合预期。

+---------------------------------+
| 初始树:                   |
|                                 |
|               6                 |
|        /               \        |
|       2                 7       |
|    /       \                    |
|   1         4                   |
|  /       /   \                  |
| 0       3     5                 |
|                                 |
|                                 |
| 预期树:                  |
|                                 |
|               6                 |
|        /               \        |
|       2                 7       |
|    /       \                    |
|   1         5                   |
|  /       /                      |
| 0       3                       |
|                                 |
|                                 |
| 实际树:                    |
|                                 |
|               6                 |
|        /               \        |
|       2                 7       |
|    /       \                    |
|   1         3                   |
|  /                              |
| 0                               |
+---------------------------------+
 

[测试失败: remove] [-0.31] : 删除树中的2后内容不符合预期。

+---------------------------------+
| 初始树:                   |
|                                 |
|               6                 |
|        /               \        |
|       2                 7       |
|    /       \                    |
|   1         4                   |
|  /       /   \                  |
| 0       3     5                 |
|                                 |
|                                 |
| 预期树:                  |
|                                 |
|               6                 |
|        /               \        |
|       3                 7       |
|    /       \                    |
|   1         4                   |
|  /           \                  |
| 0             5                 |
|                                 |
|                                 |
| 实际树:                    |
|                                 |
|       6                         |
|    /       \                    |
|   1         7                   |
|  /                              |
| 0                               |
+---------------------------------+
 

[测试失败: remove] [-0.31] : 删除树中的2后内容不符合预期。

+---------------------------------+
| 初始树:                   |
|                                 |
|               5                 |
|        /               \        |
|       2                 6       |
|    /       \                    |
|   1         3                   |
|  /           \                  |
| 0             4                 |
|                                 |
|                                 |
| 预期树:                  |
|                                 |
|               5                 |
|        /               \        |
|       3                 6       |
|    /       \                    |
|   1         4                   |
|  /                              |
| 0                               |
|                                 |
|                                 |
| 实际树:                    |
|                                 |
|       5                         |
|    /       \                    |
|   1         6                   |
|  /                              |
| 0                               |
+---------------------------------+
 

[测试失败: remove] [-0.31] : 删除树中的2后内容不符合预期。

+-----------------------------------------------------------------+
| 初始树:                                                   |
|                                                                 |
|                               6                                 |
|                /                               \                |
|               2                                 7               |
|        /               \                                        |
|       1                 5                                       |
|    /               /                                            |
|   0               3                                             |
|                      \                                          |
|                       4                                         |
|                                                                 |
|                                                                 |
| 预期树:                                                  |
|                                                                 |
|               6                                                 |
|        /               \                                        |
|       3                 7                                       |
|    /       \                                                    |
|   1         5                                                   |
|  /       /                                                      |
| 0       4                                                       |
|                                                                 |
|                                                                 |
| 实际树:                                                    |
|                                                                 |
|       6                                                         |
|    /       \                                                    |
|   1         7                                                   |
|  /                                                              |
| 0                                                               |
+-----------------------------------------------------------------+

问题分析与修复 #

核心错误 #

hRemove方法中处理节点删除的条件判断逻辑错误：
当待删除节点同时拥有左右子节点时，代码会先触发else if (current.getLeft() != null)分支，直接返回左子节点，完全跳过了处理后继节点的逻辑，导致右子树被直接丢弃，这就是测试中出现子树丢失的根本原因。

原来的条件判断顺序错误地覆盖了“同时有左右子节点”的场景——只要左子节点不为null，就会直接返回左子树，不管右子树是否存在。

修复方案 #

调整条件判断逻辑，先处理叶子节点，再处理只有单侧子节点的情况，最后处理同时有左右子节点的场景：

修改后的hRemove方法：

private BSTNode<T> hRemove(BSTNode<T> current, T data, BSTNode<T> dummy) {
    if (current == null) {
        throw new NoSuchElementException();
    } else if (data.compareTo(current.getData()) > 0) {
        current.setRight(hRemove(current.getRight(), data, dummy));
    } else if (data.compareTo(current.getData()) < 0) {
        current.setLeft(hRemove(current.getLeft(), data, dummy));
    } else {
        dummy.setData(current.getData());
        size--;
        if ((current.getLeft() == null) && (current.getRight() == null)) {
            // 叶子节点，直接删除
            return null;
        } else if (current.getRight() == null) {
            // 只有左子节点，返回左子树
            return current.getLeft();
        } else if (current.getLeft() == null) {
            // 只有右子节点，返回右子树
            return current.getRight();
        } else {
            // 同时有左右子节点，找右子树的后继节点（最小节点）
            BSTNode<T> dummy2 = new BSTNode<>(null);
            current.setRight(suc(current.getRight(), dummy2));
            current.setData(dummy2.getData());
        }
    }
    return current;
}

说明 #

• 调整后的条件判断确保“同时有左右子节点”的场景能触发后继节点处理逻辑，不会跳过；
• suc方法逻辑正确：它会找到右子树的最小节点（后继），删除该节点，并将后继的值赋值给待删除节点，保证BST的性质不变。

内容的提问来源于stack exchange，提问作者VIZ