c++ - 从二叉搜索树中删除？

Question

我正在尝试从二叉搜索树中删除并在调试器中不断出现此错误并且不确定如何纠正它。这段代码正确吗？

程序收到信号 EXC_BAD_ACCESS，无法访问内存。原因:KERN_INVALID_ADDRESS 地址:0x0000000000000000std::string::compare () 中的 0x00007fff8cc17fe2

void remove( const Comparable & x, BinaryNode *& t )
{
    if (t != NULL)
    {
        if(t->element.find(x) != std::string::npos)
        {
            if( t->left != NULL && t->right != NULL ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right);
            }
            else
            {
                BinaryNode *oldNode = t;
                t = ( t->left != NULL ) ? t->left : t->right;
                delete oldNode;
                cout << "Successly deleted!" << endl;
            }
        }
        if(x < t->element)
        {
            remove(x, t->left);
        }
        else
        {
            remove(x, t->right);
        }
    }
    else 
    {
        cout << x << "<-could not delete?" << endl;            
    }     
}

Answer 1

首先，使用调试设置编译它，然后在调试器下运行。我几乎可以保证它会准确地在您的失败案例所在的位置。

在那张纸条上，我推测是这一行:

if(x < t->element)  // <==== here
{
    remove(x, t->left);
}
else
{
    remove(x, t->right);
}

出于某种原因，您在此之前的逻辑需要进行以下推导:

• 左边和右边都不为空
• 只有左边或右边为空

您没有考虑到 both left 和 right 都为 null 的情况，例如树叶节点中的情况。因此，这取自您的其他条件:

BinaryNode *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right;
delete oldNode;
cout << "Successly deleted!" << endl;

在叶节点的情况下，会留下t设置为 null，此答案开头的代码会立即取消引用。

您需要为此重新设计您的逻辑，如果取消引用之前的代码会使被取消引用的指针无效，您需要首先检查它。

最后，如果您想知道违规行的提示是什么，您得到的报告字符串比较的具体错误是取消引用空指针。除了通过 operator < 之外，此函数中的其他任何地方都不会进行字符串比较。过载。