我一直在做一项作业,现在我被有问题的析构函数困住了。我必须创建一个包含所有常用成员函数和一些特殊运算符的通用二叉树。还有一个限制:一切都必须迭代地工作,所以这次没有令人讨厌的递归黑客。
BinTreeNode 类的析构函数显然有一些非常错误的地方,因为如果我像这样删除节点:
BinTreeNode<int> * node = new BinTreeNode<int>();
delete node;
我仍然可以访问其数据:
node->getData(); //should fail miserably
所以删除没有效果,但我不知道应该如何纠正析构函数。
在我看来,该算法应该是正确的,所以我怀疑我使用指针的方式有问题,但此时我很困惑,我什至不理解我自己的代码。
到目前为止我的代码:
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_ */