二叉搜索树含双子节点的节点删除问题及栈溢出排查

你在删除二叉搜索树中拥有两个子节点的节点时，出现递归打印栈溢出的问题，核心原因是循环引用未被清理。

你的现有逻辑只完成了后继节点的替换，但没有处理后继节点在原右子树中的父节点引用：

• 当后继节点是原节点右子树的深层左节点时，它的父节点的left指针仍然指向它
• 你又将后继节点的right指向原节点的右子树，这就形成了环（父节点→后继节点→原右子树→父节点），最终递归遍历陷入无限循环导致栈溢出

另外，你用tmp->right->index != successor->index判断是否保留原右子树的逻辑不严谨——如果BST存在重复值（虽然规范BST不允许，但代码未限制），或者后继节点不是直接右子节点时，这个判断完全无效。

修复方案 #

处理双子女节点时，必须同时清理后继节点在原位置的引用：

1. 找到后继节点的同时，跟踪它的父节点
2. 将后继节点从原父节点的子链中移除（因为后继是右子树的最左节点，它不可能有左孩子，所以直接把父节点的对应指针指向后继的右孩子即可）
3. 再将后继节点替换到目标位置，继承原节点的左右子树

修复后的代码 #

void _rm_node(Node **n, int i)
{
    if (*n == NULL)
    {
        return;
    }

    if (i < (*n)->index)
    {
        _rm_node(&(*n)->left, i);
    }
    else if (i > (*n)->index)
    {
        _rm_node(&(*n)->right, i);
    }
    else
    {
        // 无子女
        if ((*n)->left == NULL && (*n)->right == NULL)
        {
            free(*n);
            *n = NULL;
        }
        // 仅左子女
        else if ((*n)->left && (*n)->right == NULL)
        {
            Node *tmp = *n;
            *n = (*n)->left;
            free(tmp);
        }
        // 仅右子女
        else if ((*n)->left == NULL && (*n)->right)
        {
            Node *tmp = *n;
            *n = (*n)->right;
            free(tmp);
        }
        // 双子女：用中序后继替换
        else
        {
            Node *tmp = *n;
            Node *successor_parent = tmp;
            Node *successor = tmp->right;
            
            // 找到后继节点及其父节点
            while (successor->left)
            {
                successor_parent = successor;
                successor = successor->left;
            }

            // 把后继节点从原父节点的子链中移除
            if (successor_parent != tmp)
            {
                // 后继是父节点的左孩子，父节点的left指向后继的右子树（后继无左孩子）
                successor_parent->left = successor->right;
                // 让后继继承原节点的右子树
                successor->right = tmp->right;
            }
            
            // 继承原节点的左子树
            successor->left = tmp->left;
            
            // 替换目标节点
            *n = successor;
            free(tmp);
        }
    }
}

关键修改说明 #

• 新增successor_parent跟踪后继节点的父节点，确保能从原位置移除后继节点
• 当后继节点不是原节点的直接右孩子时，将父节点的left指向后继的右子树（因为后继是最左节点，没有左孩子）
• 最后让后继节点继承原节点的左右子树，完成替换，不会留下循环引用

这样修改后，递归打印PrintTree就能正常遍历，不会出现栈溢出问题。

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