C++普通二叉树删除双子女节点 采用交换叶子值方案触发程序崩溃

当前复现的问题表现 #

• 已可正常完成的操作：无子女叶子节点删除、仅单子女的节点删除
• 异常场景：删除拥有两个子节点的节点时，程序直接崩溃退出，报错为 exited with code=3221225725 in 0.474 seconds
• 已验证的对照结论：
  • 跳过delete操作、仅完成"待删节点值与右子树最右叶子节点值交换"流程时，程序可正常运行、值交换逻辑无错误
  • 完全相同的"值交换后删除最右叶子节点"思路，在二叉搜索树场景下删除功能可正常运行

核心崩溃原因 #

报错码3221225725对应Windows平台的内存访问违例错误，触发点来自两处代码逻辑漏洞：

1. 删除最右节点时产生悬空指针
   现有last_right_node函数仅返回右子树最末端节点的指针，完全没有追踪该节点的父节点信息。代码交换值后直接delete该叶子节点，但该节点的父节点的孩子指针域，仍然存储着已被释放的内存地址。后续不管是执行遍历输出、还是类析构时递归销毁整棵树，顺着这个悬空指针访问内存时就会直接触发崩溃。
   为什么跳过delete操作时程序能正常运行？因为不执行内存释放时，被找到的最右节点的内存仍然是合法可访问的，就算父节点指针没更新，顺着指向访问内存也不会触发权限错误，和之前的对照测试现象完全吻合。
   此前相同逻辑在二叉搜索树中可正常运行，本质是二叉搜索树的删除实现中，会同步更新被删叶子节点的父节点指针、将父节点对应孩子域置空，没有残留悬空指针。
2. remove公共方法未接收递归删除函数的返回值
   现有deletion函数的设计是递归返回当前子树的新根节点，来完成单子女场景下的指针替换；但对外暴露的remove方法仅调用deletion(root, data)，没有用返回值更新类成员root。如果待删除的节点是整棵树的根节点，哪怕删除流程执行完成，类内的root指针也不会被更新为新的根节点，后续访问时同样会触发内存访问错误。

修复方案 #

1. 调整双子女分支的删除逻辑：在寻找右子树最右节点的过程中，同步记录该节点的父节点位置，删除最右节点前先将父节点对应的孩子指针置为NULL，从根源上消除悬空指针。
2. 修正remove方法的调用逻辑，用deletion的返回值更新类成员root，保证根节点被删除时根指针可正确同步。

关键代码修复示例 #

• 修正后双子女删除分支逻辑：

else // 双子女节点删除场景
{
    // 从当前待删节点的右子树，找最右节点及其父节点
    Node* parent = root;
    Node* successor = root->right_child;
    while (successor->right_child != nullptr)
    {
        parent = successor;
        successor = successor->right_child;
    }
    // 完成值交换
    root->data = successor->data;
    // 将父节点的对应孩子指针置空，避免悬空指针
    if (parent->right_child == successor)
    {
        parent->right_child = nullptr;
    }
    else
    {
        parent->left_child = nullptr;
    }
    // 安全释放successor节点内存
    delete successor;
}

• 修正后remove方法实现：

void remove(int data)
{
    // 用返回值更新类的根指针，保证删除根节点场景下指针正确
    root = deletion(root, data);
}

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