C++二叉树删除函数问题：双子女节点删除时触发段错误

实现二叉树删除函数时，当待删除节点拥有两个子节点，已将后继节点的数据复制到待删除节点，但删除后继节点时出现段错误。

类定义 #

#include <iostream>

template <typename T>
class Set
{
private:
    class Node
    {
        public:
            T data;
            Node *left;
            Node *right;
            Node(T key)
            {
                this->data = key;
                this->left = this->right = nullptr;
            }
    };
    Node *root; int size;

public:
    Set();
    ~Set();
    void insert(T key);
    Node *insert(Node *&ptr, T key);
    void remove(T key);
    Node *remove(Node *&, T key);
    bool contains(T key);
    bool contains(Node *&ptr, T key);
    void cutDown(Node *ptr);
    int getSize();
    void print();
    void print(Node *ptr);
};

构造函数 #

template <typename T>
Set<T>::Set()
{
    root = nullptr; size = 0;
}

插入函数 #

template <typename T>
void Set<T>::insert(T key)
{
    insert(root, key);
}

template <typename T>
typename Set<T>::Node *Set<T>::insert(Node *&ptr, T key)
{
    if (contains(key) == false)
    {
        if (ptr == nullptr)
        {
            ++size;
            Node *temp = new Node(key);
            ptr = temp;
            return ptr;
        }
        else 
        {
            Node *temp = ptr;
            if (key > temp->data)
            {
                temp->right = insert(temp->right, key);
            }
            else if (key < temp->data) 
            {
                temp->left = insert(temp->left, key);
            }
        }
    }
    else  
    {
        return nullptr;
    }
    return ptr;
}

删除函数（原错误实现） #

template <typename T>
void Set<T>::remove(T key)
{
    remove(root, key);
    std::cout << "deleted...\n\n";
    --size;
}

template <typename T>
typename Set<T>::Node *Set<T>::remove(Node *&ptr, T key)
{
    if (key > ptr->data)
    {
        std::cout << "greater...\n";
        ptr->right = remove(ptr->right, key);
    }
    else if (key < ptr->data)
    {
        std::cout << "less...\n";
        ptr->left = remove(ptr->left, key);
    }
    else  
    {
        if (!ptr->left && !ptr->right) //无子女节点
        {
            std::cout << "case 1...\n";
            delete ptr;
            ptr = nullptr;
        }
        else if (ptr->left && ptr->right) //双子女节点
        {
            std::cout << "case 2...\n";
            Node *child = ptr->right;
            Node *p = child;
            while (child->left != nullptr)
            {
                child = child->left;
            }
            ptr->data = child->data;
            std::cout << "next data: " << p->left->data << "\n";
            p->left = remove(p->left, child->data);
        }
        else                             //单子女节点
        {
            std::cout << "case 3...\n";
            Node *node = ptr;
            Node *hold = (ptr->left)? ptr->left : ptr->right;
            node = hold;
            delete hold;
        }
    }
    return ptr;
}

包含判断函数 #

template <typename T>
bool Set<T>::contains(T key)
{
    return contains(root, key);
}

template <typename T>
bool Set<T>::contains(Node *&ptr, T key)
{
    Node *hold = ptr;
    while (hold != nullptr)
    {
        if (hold->data == key)
        {
            return true;
        }
        
            if (hold->data > key)
            {
                hold = hold->left;
            }
            else  
            {
                hold = hold->right;
            }
        
    }
    return false;
}

问题分析与修复 #

错误点： #

1. 双子女节点处理逻辑错误：当后继节点就是待删除节点的右子节点（无左子树）时，p->left为nullptr，调用remove(p->left, child->data)会传入空指针，触发空指针访问错误。
2. 单子女节点处理逻辑错误：仅修改临时变量node的指向，未更新原ptr，且错误删除子节点而非当前节点，导致内存泄漏与逻辑混乱。
3. 未处理空指针情况：当查找的key不存在时，递归过程中会访问空指针的data成员。
4. size计数错误：外部remove函数直接递减size，未判断删除是否成功。

修复后的删除函数 #

template <typename T>
void Set<T>::remove(T key)
{
    // 仅当节点存在时执行删除与size递减
    if (contains(key)) {
        remove(root, key);
        std::cout << "deleted...\n\n";
        --size;
    }
}

template <typename T>
typename Set<T>::Node *Set<T>::remove(Node *&ptr, T key)
{
    // 处理空指针，避免访问错误
    if (ptr == nullptr) {
        return nullptr;
    }

    if (key > ptr->data)
    {
        std::cout << "greater...\n";
        ptr->right = remove(ptr->right, key);
    }
    else if (key < ptr->data)
    {
        std::cout << "less...\n";
        ptr->left = remove(ptr->left, key);
    }
    else  
    {
        if (!ptr->left && !ptr->right) // 无子女节点
        {
            std::cout << "case 1...\n";
            delete ptr;
            ptr = nullptr;
        }
        else if (ptr->left && ptr->right) // 双子女节点
        {
            std::cout << "case 2...\n";
            // 追踪后继节点及其父节点
            Node *successor = ptr->right;
            Node *successorParent = nullptr;
            while (successor->left != nullptr)
            {
                successorParent = successor;
                successor = successor->left;
            }
            // 复制后继节点数据
            ptr->data = successor->data;
            // 直接调整指针删除后继，避免递归空指针问题
            if (successorParent == nullptr) {
                // 后继就是ptr的右子节点，将ptr的右指针指向后继的右子树
                ptr->right = successor->right;
            } else {
                // 后继是右子树的左后代，更新父节点的左指针
                successorParent->left = successor->right;
            }
            delete successor;
        }
        else // 单子女节点
        {
            std::cout << "case 3...\n";
            Node *temp = ptr;
            // 将当前节点替换为子节点
            ptr = (ptr->left) ? ptr->left : ptr->right;
            delete temp;
        }
    }
    return ptr;
}

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