Java BST使用指针强化递归删除时双子女节点删除异常问题

安全阿岳

2026-10-7

BST递归删除故障排查与修复

故障1：removeSuccessor方法缺失返回语句

原因

该方法仅在递归基例（当前节点左子为空）中有返回值，非基例分支完成左子节点重绑定后，没有返回当前节点给上层完成指针强化，导致IDE报语法错误。

修复代码

private BSTNode<T> removeSuccessor(BSTNode<T> current, BSTNode<T> dummy) {
    if (current.getLeft() == null) {
        dummy.setData(current.getData());
        return current.getRight();
    } else {
        current.setLeft(removeSuccessor(current.getLeft(), dummy));
        // 补充返回当前节点，完成递归链路的指针回绑
        return current;
    }
}

故障2：双子女节点删除结果异常

原因

rRemove方法中删除场景的判断顺序逻辑错误：原代码优先判断「左子不为空就返回左子节点」，若待删除节点同时存在左右子节点，会直接进入单子女删除分支，直接丢弃右子树，永远不会触发双子女的后继替换逻辑。

修复代码（替换rRemove中找到待删除节点后的判断分支）

// 找到待删除节点后的逻辑
dummy.setData(current.getData());
size--;
if (current.getRight() == null  && current.getLeft() == null) {
    // 原代码中判断current.equals(root)的逻辑可删除，外层root = rRemove(...)会自动处理根节点为空的情况
    return null;
} else if (current.getLeft() == null) {
    // 仅右子节点存在，返回右子
    return current.getRight();
} else if (current.getRight() == null) {
    // 仅左子节点存在，返回左子
    return current.getLeft();
} else {
    // 双子女节点，才走后继替换逻辑
    BSTNode<T> dummy2 = new BSTNode<>(null);
    current.setRight(removeSuccessor(current.getRight(), dummy2));
    current.setData(dummy2.getData());
}