我对这个二叉搜索树有疑问。
在那之后我就离开了,如果我尝试显示树,VisualStudio 会回答我这个消息
An unhandled exception of type
'System.AccessViolationException'
occurred in ABR1.exeAdditional 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;
}
最佳答案
您在 showTreePreOrder 中递归并遇到堆栈溢出。在调试器中运行它不到一分钟就告诉我这一点。
编辑:
您的问题出在 cutLeaf() 的这一部分。首先,您假设 Leafptr->SX 不为空并且您要删除它,但最后一片叶子为空。其次,当您删除叶节点时,您不会将其父节点的 DX 指针设置为空。因此,当您遍历列表时,您遍历到已被释放的叶子。
else if (Leafptr->DX == NULL)
{
tempLeafptr = Leafptr;
Leafptr = Leafptr->SX;
delete tempLeafptr;
return true;
}
else子句也存在同样的问题。
关于c++ - 错误 "System.AccessViolationException"显示切割后的二叉树 Visual C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7638404/