Ошибка «System.AccessViolationException» показывает двоичное дерево после вырезания visualc ++

Question

У меня проблема с этим бинарным деревом поиска.

После этого я вырезаю отпуск, если я пытаюсь показать дерево VisualStudio, ответьте мне на это сообщение

Необработанное исключениетипа 'System.AccessViolationException' произошла в ABR1.exe

Дополнительная информация: Попытка чтения или записи в защищенную память.Это часто указывает на то, что другая память повреждена.

Больше 3 дней я пытаюсь понять, может ли кто-нибудь мне помочь ???

// ABR1.cpp : main project file.

#include "stdafx.h"

#include <iostream>

using namespace System;
using namespace std;

template <class T>
class ABR{
private:
    struct Leaf{
        T value;
        struct Leaf *DX;   //
        struct Leaf *SX;   //
    };
    Leaf *root;

public:
    //constructors
    ABR() { root = NULL; }
    //destructor
    //~ABR();
    void appendLeaf(T);
    bool cutLeaf(T);
    bool isInTree(T) const;

    Leaf* findLeaf(T) const;

    void showTreeInOrder() const { showTreeInOrder(root); }
    void showTreeInOrder(Leaf *) const;

    void showTreePreOrder() const { showTreePreOrder(root); }
    void showTreePreOrder(Leaf *) const;
};

template <class T>
void ABR<T>::appendLeaf(T newValue){
    if (isInTree(newValue)){
        cout << "The value is just present..." << endl;
        return;
    }
    Leaf *newLeaf;  // To point to a new leaf
    Leaf *ptrLeaf;  // To move in the tree

    // Allocate the necessary memory

    newLeaf = new Leaf;    //generate the new leaf
    newLeaf-> value = newValue;
    newLeaf-> DX = NULL;
    newLeaf-> SX = NULL;

    if(!root)            //if is the first leaf
        root = newLeaf;
    else{
        ptrLeaf = root;
        //cout<<ptrLeaf->value<<ptrLeaf->SX<<ptrLeaf->DX<<endl;

        while (ptrLeaf != NULL){
            //cout << ptrLeaf->value <<"\t";
            if (ptrLeaf->value < newValue){
                if (ptrLeaf->DX == NULL){
                    ptrLeaf->DX = newLeaf;
                    return;
                }
                else
                    ptrLeaf = ptrLeaf->DX;
            }
            else{
                if(ptrLeaf->SX == NULL){
                    ptrLeaf->SX = newLeaf;
                    return;
                }
                else
                    ptrLeaf = ptrLeaf->SX;
            }
        }
    }
}

template <class T>
bool ABR<T>::isInTree(T toFind) const{
    Leaf *ptrLeaf;

    ptrLeaf = root;

    while (ptrLeaf){
        if (ptrLeaf->value == toFind)
            return true;
        else{
            if (ptrLeaf->value < toFind)
                ptrLeaf = ptrLeaf->DX;
            else
                ptrLeaf = ptrLeaf->SX;
        }
    }
    return false;
}

template <class T>
typename ABR<T>::Leaf * ABR<T>::findLeaf(T toFind) const
{
    Leaf *ptr;
    ptr = root;

    while(ptr != NULL)
    {
        //cout << ptr->value << "#" << endl;
        if (toFind == ptr->value){
            //cout << "Trovato";
            return ptr;
        }
        else if (ptr->value < toFind)
            ptr = ptr->DX;
        else
            ptr = ptr->SX;
    }        cout << "Element don't find" << endl;
    return NULL;
}

template <class T>
void ABR<T>::showTreeInOrder(Leaf *ptr) const
{
    if(ptr != NULL)
    {
        showTreeInOrder(ptr->SX);
        cout << ptr->value << endl;
        showTreeInOrder(ptr->DX);
    }
}

template <class T>
void ABR<T>::showTreePreOrder(Leaf *ptr) const
{
    if(ptr != NULL)
    {
        showTreePreOrder(ptr->DX);
        cout << ptr->value << endl;
        showTreePreOrder(ptr->SX);
    }
}

template <class T>
bool ABR<T>::cutLeaf(T toCut)
{
    Leaf *Leafptr, *tempLeafptr;
    Leafptr = findLeaf(toCut);

    if (Leafptr == NULL)
    {
        cout << "The element is not present..." << endl;
        return false;
    }
    else if (Leafptr->DX == NULL)
    {
        tempLeafptr = Leafptr;
        Leafptr = Leafptr->SX;
        delete tempLeafptr;
        return true;
    }
    else if (Leafptr->SX == NULL)
    {
        tempLeafptr = Leafptr;
        Leafptr = Leafptr->DX;
        delete tempLeafptr;
        return true;
    }
    else
    {
        tempLeafptr = Leafptr->DX;

        while (tempLeafptr->SX)
            tempLeafptr = tempLeafptr->SX;

        tempLeafptr->DX = Leafptr->SX;
        tempLeafptr = Leafptr;
        Leafptr = Leafptr->DX;
        delete tempLeafptr;
        return true;
    }
}

int main(){
    ABR<int> albero;

    for(int a = 0.0; a < 100.0; a+= 3)
        albero.appendLeaf(a);

    albero.appendLeaf(1000);
    albero.appendLeaf(1001);
    albero.showTreePreOrder();
    int b = 75;
    albero.cutLeaf(b);
    albero.showTreePreOrder(); //ERROR
    //albero.showTreeInOrder();//SAME ERROR

    system("PAUSE");

    return 0;
}

Answer 1

Вы возвращаетесь в showTreePreOrder и сталкиваетесь с переполнением стека. Запуск его в отладчике сказал мне об этом менее чем за одну минуту.

EDIT:

Ваша проблема в этом разделе cutLeaf (). Во-первых, вы предполагаете, что Leafptr-> SX не равен нулю, и вы удаляете его, но он равен нулю для последнего листа. Во-вторых, когда вы удаляете лист, вы не устанавливаете указатель DX его родителя в нуль. Поэтому, когда вы пересекаете список, вы пересекаете листья, которые были освобождены.

else if (Leafptr->DX == NULL)
{
    tempLeafptr = Leafptr;
    Leafptr = Leafptr->SX;
    delete tempLeafptr;
    return true;
}

Те же проблемы существуют в предложении else.