c++ - 错误 "System.AccessViolationException"显示切割后的二叉树 Visual C++

Question

我对这个二叉搜索树有疑问。

在那之后我就离开了，如果我尝试显示树，VisualStudio 会回答我这个消息

An unhandled exception of type 'System.AccessViolationException' occurred in ABR1.exe

Additional information: Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

我尝试理解超过 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 中递归并遇到堆栈溢出。在调试器中运行它不到一分钟就告诉我这一点。

编辑:

您的问题出在 cutLeaf() 的这一部分。首先，您假设 Leafptr->SX 不为空并且您要删除它，但最后一片叶子为空。其次，当您删除叶节点时，您不会将其父节点的 DX 指针设置为空。因此，当您遍历列表时，您遍历到已被释放的叶子。

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

else子句也存在同样的问题。