c++ - 二分探索木 - アクセス違反

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 と else はほとんど意味がありません -

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;

null変数のプロパティにアクセスしようとしているため、「アクセス違反」です。

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に逆参照しようとしています。NULLrightLinkprev

逆参照しようとするNULLと、ある種のアクセス違反エラーが発生します。