Блог

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

После этого я отключаю отпуск, если я попытаюсь показать дерево 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;
}
  

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

Редактировать:

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

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

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