二叉搜索树 - 访问冲突

Question

此方法查找 BST 中最大的节点返回其值并将其删除。我在 prev->rightLink = cur->leftLink; 收到访问违规。 我对C++相对陌生，找不到原因。

int CTree::popLargest(TreeNode* tr)
{   
    int largest;
    TreeNode* prev = NULL;
    TreeNode* cur = tr;
    while (cur->rightLink != NULL)
    {
        prev = cur;
        cur = cur->rightLink;
        largest = cur->info;
        //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);     
    }
    if (cur->leftLink != NULL)
    {
        prev->rightLink = cur->leftLink;
    }
    else 
    {
        prev->rightLink = NULL;
    }
    return largest;
}

Answer 1

如果，否则没有什么意义 -

if (cur->leftLink != NULL)
{
    prev->rightLink = cur->leftLink;
}
else 
{
    prev->rightLink = NULL;
}

您正在尝试做的事情可以通过以下方式完成 - prev->rightLink = cur->leftLink;

您在此语句上收到访问冲突的原因是prev没有指向有效节点，即它被NULL（初始化时）。

Answer 2

如果树没有任何正确的子级，prev 将保持空值并在执行时保持

null

prev->rightLink = cur->leftLink;

您正在尝试访问空变量的属性，因此"访问Voilation"。

Answer 3

原因是 prev 仍然是 NULL。取消引用指针时，应验证指针是否为 NULL。顺便说一句，这个问题很容易通过调试找到。

const int INVALID_VALUE = -1;    // change it by yourself.
int CTree::popLargest(TreeNode* tr)
{  
    int largest = INVALID_VALUE;
    if (tr != NULL)
    {
        TreeNode* prev = NULL;
        TreeNode* cur = tr;
        while (cur->rightLink != NULL)
        {
            prev = cur;
            cur = cur->rightLink;
            largest = cur->info;
            //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);     
        }
        if (prev != NULL)
        {
            if (cur->leftLink != NULL)
            {
                prev->rightLink = cur->leftLink;
            }
            else 
            {
                prev->rightLink = NULL;
            }
        }
    }
    return largest;
}

Answer 4

你没有考虑到tr没有正确的元素（tr->rightLink = NULL，cur = tr）的情况，因此while循环的内容永远不会执行。在这种情况下，prev保持为 NULL ，这意味着您在尝试访问 prev 的 rightLink 元素时尝试取消引用NULL。

尝试取消引用NULL将导致某种访问冲突错误。