C++二叉搜索树删除异常：Node类成员顺序影响问题解析

你在C++实现二叉搜索树时遇到一个特殊问题：当Node类中先声明left指针再声明right指针时，删除100、50这类节点无法正常工作；但仅调换两个指针的声明顺序（先right后left），所有功能就恢复正常。

有问题的Node类代码 #

class Node{
    public:
        int data;
        
        Node* left;
        Node* right;
        Node(){ data=0; right=left=NULL;};
        Node(int x){ data=x; right=left=NULL;};
        bool is_leaf(){ return (left==NULL && right==NULL);
        }
};

完整的BST实现代码 #

class BST{
    
    private:
        Node* root;
        Node * _del(int x,Node* n);
        void _insert_rec(int x,Node*n);
    public:
        BST(){ root=NULL; };
        void insert_rec(int x);
        void print();
        void del(int x);

};

void BST::del(int x)
{
    root = _del(x,root);
}

Node * BST::_del(int x,Node* n)
{
    if(!n)
        return NULL;
    else
    {
        if(x<n->data)
            n->left = _del(x,n->left);
        else if(x>n->data)
            n->right = _del(x,n->right);
        else
        {
            if(n->is_leaf())
            {
                delete n;
                return NULL;
            }
            else
            {
                if(!n->right)
                {
                    delete n;
                    return n->left;
                }
                else if (!n->left)
                {
                    delete n;
                    return n->right;
                }
                else
                {
                    int enb = _max_value(n->left); // 原代码未实现该函数，但不影响当前问题分析
                    n->data = enb;
                    n->left = _del(enb,n->left);
                }
            }
        }
    }
    return n;
}

void BST::insert_rec(int x)
{
    root = _insert_rec(x,root);
}

Node * BST::_insert_rec(int x,Node* r)
{
    if(!r)
        return new Node(x);
    else
    {
        if(x>r->data)
            r->right = _insert_rec(x,r->right);
        else
            r->left = _insert_rec(x,r->left);
    }
    return r;
}

int main(int argc, char** argv) 
{
    BST *bst = new BST();
    bst->insert_rec(50);
    bst->insert_rec(100);
    bst->insert_rec(20);
    bst->insert_rec(10);
    bst->insert_rec(70);


    bst->print();
    bst->del(100);
    cout<<endl;
    bst->print();
    return 0;
}

修改后正常工作的Node类代码 #

class Node{
    public:
        int data;
        
        Node* right;  // 仅调换了指针声明顺序
        Node* left;
        
        Node(){ data=0; right=left=NULL;};
        Node(int x){ data=x; right=left=NULL;};
        bool is_leaf(){ return (left==NULL && right==NULL);
        }
};

问题根源分析 #

这个现象的核心是未定义行为，而非指针声明顺序本身有问题：

在_del函数的这段代码中，你犯了致命错误：在delete n之后，仍然访问了已经被释放的节点的成员指针：

if(!n->right)
{
    delete n;
    return n->left; // 错误：n已被释放，访问n->left属于未定义行为
}
else if (!n->left)
{
    delete n;
    return n->right; // 同样错误：访问已释放内存的成员
}

当delete一个对象后，其占用的内存会被标记为可回收，但内存中的值不会立即清零。此时访问悬空指针的成员，结果完全取决于内存布局和编译器行为——这就是未定义行为的特点：它可能碰巧“正常工作”，也可能崩溃、输出垃圾值，或者引发其他诡异问题。

调换指针顺序后“正常”只是巧合：当right先声明时，delete后内存中残留的指针值刚好是正确的；而left先声明时，残留的值是错误的。但这完全是随机的，不能依赖这种行为。

正确的修复方式 #

先保存需要返回的指针，再执行delete操作：

if(!n->right)
{
    Node* temp = n->left; // 先保存指针
    delete n;
    return temp;
}
else if (!n->left)
{
    Node* temp = n->right; // 先保存指针
    delete n;
    return temp;
}

内容的提问来源于stack exchange，提问作者MUSTAFA ERİŞ