通用二叉树节点析构函数问题 [英] Generic binary tree node destructor issue
问题描述
我一直在做一个作业，现在我被卡住了buggy析构函数。我必须创建一个通用的二叉树与所有常用的成员函数和一些特殊的操作符。还有一个限制：一切都必须重复工作，所以这次没有讨厌的递归黑客。
BinTreeNode类的析构函数显然有些错误，因为如果我删除节点像这样：
BinTreeNode< int> * node = new BinTreeNode< int>（）;
删除节点;
我仍然可以访问其数据：
node-> getData（）; //应该失败
所以删除没有影响，但我没有可用的想法我应该如何纠正析构函数
在我看来，算法应该是正确的，所以我怀疑我使用指针有什么问题，但在这一点上，我很困惑，我甚至不明白我自己的代码。
代码我有这么远：
BinTree.h
#ifndef BINTREE_H_
#define BINTREE_H_
#ifndef NULL
#define NULL 0
#endif
#includeBinTreeNode.h
template< class T>
class BinTree
{
private：
BinTreeNode< T> * 根;
public：
//构造函数和析构函数
BinTree（）：
root（NULL）{}
BinTree（T data）：
root（new BinTreeNode< T>（data））{}
〜BinTree（）;
// search
BinTreeNode< T> *搜索（T数据）;
// insert
bool insert（T data）;
//删除
bool remove（T data）;
};
模板< class T>
BinTree< T> ::〜BinTree（）
{
删除根;
}
模板< class T>
BinTreeNode< T> * BinTree< T> :: search（T data）
{
BinTreeNode< T> * node = new BinTreeNode< T>（data）;
BinTreeNode< T> * current = root;
while（current！= NULL）
{
if（* current == * node）
{
delete node;
返回根;
}
else if（* node< * current）
{
current = current-> getLeft（）;
}
else
{
current = current-> getRight（）;
}
}
删除节点;
返回NULL;
}
模板< class T>
bool BinTree< T> :: insert（T data）
{
BinTreeNode< T> * node = new BinTreeNode< T>（data）;
BinTreeNode< T> * current = root;
while（current！= NULL）
{
if（* current == * node）
{
delete node;
返回false;
}
else if（* node< * current）
{
if（current-> getLeft（）== NULL）
{
current-> setLeft（node）;
返回true;
}
else
{
current = current-> getLeft（）;
}
}
else
{
if（current-> getRight（）== NULL）
{
current-> setRight（node）;
返回true;
}
else
{
current = current-> getRight（）;
}
}
}
return false;
}
#endif
BinTreeNode.h
#ifndef BINTREENODE_H_
#define BINTREENODE_H_
#ifndef NULL
#define NULL 0
#endif
模板< class T>
class BinTreeNode
{
private：
T data;
BinTreeNode< T> *左，*右，*父母;
public：
//构造函数和析构函数
BinTreeNode（）：
数据（NULL），左（NULL），右（NULL），父（NULL）{}
BinTreeNode（T数据）：
数据（数据），左（NULL），右（NULL），父（NULL）{}
〜BinTreeNode（）;
//设置并获取数据成员
T getData（）const;
void setData（T data）;
//设置并获取左右分支
BinTreeNode< T> * getLeft（）const;
BinTreeNode< T> * getRight（）const;
void setLeft（BinTreeNode< T> * node）;
void setRight（BinTreeNode< T> * node）;
//设置并获取父
BinTreeNode< T> * getParent（）const;
void setParent（BinTreeNode< T> * node）;
//比较运算符
bool运算符<（const BinTreeNode< T>& node）const;
bool operator>（const BinTreeNode< T&& Node）const;
bool operator ==（const BinTreeNode< T>& node）const;
};
模板< class T>
BinTreeNode< T> ::〜BinTreeNode（）
{
BinTreeNode< T> * current = this;
BinTreeNode< T> * parent = NULL;
while（current！= NULL）
{
parent = current-> getParent（）;
if（current-> getLeft（）== NULL）
current = current-> getLeft（）;
else if（current-> getRight（）== NULL）
current = current-> getRight（）;
else
{
if（parent-> getRight（）== current）
parent-> setRight（NULL）;
else
parent-> setLeft（NULL）;
current = NULL; //这行（等等）非常可疑
}
current = parent;
}
}
模板< class T>
T BinTreeNode< T> :: getData（）const
{
返回数据;
}
模板< class T>
void BinTreeNode< T> :: setData（T data）
{
this-> data = data;
}
模板< class T>
BinTreeNode< T> * BinTreeNode< T> :: getLeft（）const
{
return left;
}
模板< class T>
BinTreeNode< T> * BinTreeNode< T> :: getRight（）const
{
return right;
}
模板< class T>
void BinTreeNode< T> :: setLeft（BinTreeNode< T> * node）
{
node-> setParent（this）;
left = node;
}
模板< class T>
void BinTreeNode< T> :: setRight（BinTreeNode< T> * node）
{
node-> setParent（this）;
right = node;
}
模板< class T>
BinTreeNode< T> * BinTreeNode< T> :: getParent（）const
{
return parent;
}
模板< class T>
void BinTreeNode< T> :: setParent（BinTreeNode< T> * node）
{
parent = node;
}
模板< class T>
bool BinTreeNode< T> :: operator<（const BinTreeNode< T& Node）const
{
return this-> data< node.data;
}
模板< class T>
bool BinTreeNode< T> :: operator>（const BinTreeNode< T& Node）const
{
return this-> data> node.data;
}
模板< class T>
bool BinTreeNode< T> :: operator ==（const BinTreeNode< T&& Node）const
{
return this-> data == node.data;
}
#endif / * BINTREENODE_H_ * /
你的 BinTreeNode 析构函数应该是：
template< class T>
BinTreeNode< T> ::〜BinTreeNode（）{
delete left;
删除权限;
}
这将递归调用左右的析构函数，释放为这些节点分配的内存和他们的子节点。这将使整个树免费。
将 NULL 分配给指针不释放其指向的内存。 / p>
另一方面，你提到的删除后，这一行：
node-> getData（）;
仍然返回数据，是完全正常的。删除释放内存，但存储在其中的数据可能仍然可用一段时间，直到新内存写入该内存地址。访问已经空闲的内存地址意味着未定义的行为。
BTW，您应该在C ++中使用0（不带引号），而不是 NULL 。因此，没有必要使用 #ifndef NULL （...）。
编辑：我没有看到不递归的评论。这是非递归算法：
#include< deque>
/ * ... * /
模板< class T>
BinTreeNode< T> ::〜BinTreeNode（）{
std :: deque deq;
//我们要删除我们的孩子
deq.push_back（this）;
while（deq.size（））{
BinTreeNode< T> * ptr = deq.front（）;
deq.pop_front（）;
if（ptr）{
deq.push_back（ptr-> left）;
deq.push_back（ptr-> right）;
//我们不希望子节点
//双重删除子节点
ptr-> left = 0;
ptr-> right = 0;
//避免自己删除
if（ptr！= this）
delete ptr;
}
}
}
我还没有测试，但它应该工作。
I've been working on an assignment and now I'm stuck with buggy destructors. I have to create a generic binary tree with all the usual member functions and some special operators. There's also a restriction: everything must work iteratively so no nasty recursive hacks this time.
There is obviously something very wrong with the destructor of BinTreeNode class because if I delete the node like this:
BinTreeNode<int> * node = new BinTreeNode<int>();
delete node;
I can still access its data:
node->getData(); //should fail miserably
so deletion has no effect but I have no usable idea how I should correct the destructor. It seems to me that the algorithm should be about right so I suspect there's something wrong with how I use pointers but at this point I'm so confused that I don't even understand my own code.
Code I have this far:
BinTree.h
#ifndef BINTREE_H_
#define BINTREE_H_
#ifndef NULL
#define NULL 0
#endif
#include "BinTreeNode.h"
template <class T>
class BinTree
{
private:
BinTreeNode<T> * root;
public:
//constructors and destructor
BinTree():
root(NULL){}
BinTree(T data):
root(new BinTreeNode<T>(data)){}
~BinTree();
//search
BinTreeNode<T> * search(T data);
//insert
bool insert(T data);
//remove
bool remove(T data);
};
template <class T>
BinTree<T>::~BinTree()
{
delete root;
}
template <class T>
BinTreeNode<T> * BinTree<T>::search(T data)
{
BinTreeNode<T> * node = new BinTreeNode<T>(data);
BinTreeNode<T> * current = root;
while (current != NULL)
{
if (*current == *node)
{
delete node;
return root;
}
else if (*node < *current)
{
current = current->getLeft();
}
else
{
current = current->getRight();
}
}
delete node;
return NULL;
}
template <class T>
bool BinTree<T>::insert(T data)
{
BinTreeNode<T> * node = new BinTreeNode<T>(data);
BinTreeNode<T> * current = root;
while (current != NULL)
{
if (*current == *node)
{
delete node;
return false;
}
else if (*node < *current)
{
if (current->getLeft() == NULL)
{
current->setLeft(node);
return true;
}
else
{
current = current->getLeft();
}
}
else
{
if (current->getRight() == NULL)
{
current->setRight(node);
return true;
}
else
{
current = current->getRight();
}
}
}
return false;
}
#endif
BinTreeNode.h
#ifndef BINTREENODE_H_
#define BINTREENODE_H_
#ifndef NULL
#define NULL 0
#endif
template <class T>
class BinTreeNode
{
private:
T data;
BinTreeNode<T> *left, *right, *parent;
public:
//constructors and destructor
BinTreeNode():
data(NULL), left(NULL), right(NULL), parent(NULL){}
BinTreeNode(T data):
data(data), left(NULL), right(NULL), parent(NULL){}
~BinTreeNode();
//set and get data member
T getData() const;
void setData(T data);
//set and get left and right branches
BinTreeNode<T> * getLeft() const;
BinTreeNode<T> * getRight() const;
void setLeft(BinTreeNode<T> * node);
void setRight(BinTreeNode<T> * node);
//set and get parent
BinTreeNode<T> * getParent() const;
void setParent(BinTreeNode<T> * node);
//comparison operators
bool operator<(const BinTreeNode<T>& node) const;
bool operator>(const BinTreeNode<T>& node) const;
bool operator==(const BinTreeNode<T>& node) const;
};
template <class T>
BinTreeNode<T>::~BinTreeNode()
{
BinTreeNode<T> * current = this;
BinTreeNode<T> * parent = NULL;
while (current != NULL)
{
parent = current->getParent();
if (current->getLeft() == NULL)
current = current->getLeft();
else if (current->getRight() == NULL)
current = current->getRight();
else
{
if (parent->getRight() == current)
parent->setRight(NULL);
else
parent->setLeft(NULL);
current = NULL; // this line (among others) is very suspicious
}
current = parent;
}
}
template <class T>
T BinTreeNode<T>::getData() const
{
return data;
}
template <class T>
void BinTreeNode<T>::setData(T data)
{
this->data = data;
}
template <class T>
BinTreeNode<T> * BinTreeNode<T>::getLeft() const
{
return left;
}
template <class T>
BinTreeNode<T> * BinTreeNode<T>::getRight() const
{
return right;
}
template <class T>
void BinTreeNode<T>::setLeft(BinTreeNode<T> * node)
{
node->setParent(this);
left = node;
}
template <class T>
void BinTreeNode<T>::setRight(BinTreeNode<T> * node)
{
node->setParent(this);
right = node;
}
template <class T>
BinTreeNode<T> * BinTreeNode<T>::getParent() const
{
return parent;
}
template <class T>
void BinTreeNode<T>::setParent(BinTreeNode<T> * node)
{
parent = node;
}
template <class T>
bool BinTreeNode<T>::operator<(const BinTreeNode<T>& node) const
{
return this->data < node.data;
}
template <class T>
bool BinTreeNode<T>::operator>(const BinTreeNode<T>& node) const
{
return this->data > node.data;
}
template <class T>
bool BinTreeNode<T>::operator==(const BinTreeNode<T>& node) const
{
return this->data == node.data;
}
#endif /* BINTREENODE_H_ */
Your BinTreeNode destructor should simply be:
template <class T>
BinTreeNode<T>::~BinTreeNode() {
delete left;
delete right;
}
That will call left and right's destructors recursively, freeing the memory allocated for those nodes and their child nodes. This will as a consequence free the entire tree.
Assigning NULL to a pointer does not free the memory pointed by it.
On the other hand, what you mention, that after deletion, this line:
node->getData();
Still returns data, is perfectly normal. Deletion frees the memory, but the data stored in it might still be available for a while, until something new is written in that memory address. Accessing an already free'd memory address implies undefined behaviour.
BTW, you should use "0"(without quotes) in C++ instead of NULL. Therefore, there it's not necessary to use the #ifndef NULL(...).
EDIT: I hadn't seen the "no recursion" comment. Here's a non-recursive algorithm:
#include <deque>
/* ... */
template <class T>
BinTreeNode<T>::~BinTreeNode() {
std::deque deq;
// we're going to delete our children
deq.push_back(this);
while(deq.size()) {
BinTreeNode<T> *ptr = deq.front();
deq.pop_front();
if(ptr) {
deq.push_back(ptr->left);
deq.push_back(ptr->right);
// we don't want the child nodes
// to double delete the children
ptr->left = 0;
ptr->right = 0;
// avoid deleteing ourselves
if(ptr != this)
delete ptr;
}
}
}
I haven't tested it, but it should work.
这篇关于通用二叉树节点析构函数问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
