二叉搜索树递归析构函数
Binary search tree recursive destructor
我检查了其他类似的主题,但 none 似乎对我有帮助。
我正在尝试为这个特定的 BST 实现编写一个析构函数。每个节点都包含一个指向父节点的指针、一个指向左节点的指针、一个指向右节点的指针和一个指向它包含的值的指针。
class 的开头是这样的:
#ifndef BST_H
#define BST_H
#include <iostream>
template <typename T>
class BST{
private:
BST<T> *left;
BST<T> *right;
BST<T> *parent;
T *value;
public:
BST() {
this->parent = NULL;
this->left = NULL;
this->right = NULL;
this->value = NULL;
}
~BST() {
removeRecursively(this);
}
void removeRecursively(BST<T>* node) {
if (node->left != NULL)
removeRecursively(node->left);
if (node->right != NULL)
removeRecursively(node->right);
if (node->left == NULL && node->right == NULL) {
if (node->parent->left == node)
node->parent->left = NULL;
if (node->parent->right == node)
node->parent->right = NULL;
node->parent = NULL;
node->value = NULL;
delete node->value;
delete node;
}
}
void add(T value) {
if (this->value == NULL) { // root-only case
this->value = new T;
*(this->value) = value;
}
else {
if (value < *(this->value)) {
if (this->left != NULL) // has left child
this->left->add(value);
else { // has no left child
this->left = new BST<T>;
this->left->value = new T;
this->left->parent = this;
*(this->left->value) = value;
}
}
else {
if (this->right != NULL) // has right child
this->right->add(value);
else { // has no right child
this->right = new BST<T>;
this->right->value = new T;
this->right->parent = this;
*(this->right->value) = value;
}
}
}
}
void inOrderDisplay() {
if (this->left != NULL)
this->left->inOrderDisplay();
std::cout << *(this->value) << " ";
if (this->right != NULL)
this->right->inOrderDisplay();
}
BST<T>* search(T value) {
if (*(this->value) == value)
return this;
else if (this->left != NULL && value < *(this->value))
return this->left->search(value);
else if (this->right != NULL && value > *(this->value))
return this->right->search(value);
else
return NULL;
}
BST<T>* remove(T value) {
BST<T>* node = search(value);
if (node != NULL) {
if (node->left == NULL && node->right == NULL) { // leaf node
delete node->value;
if (node->parent->left == node) // is left child
node->parent->left = NULL;
else // is right child
node->parent->right = NULL;
delete node;
}
// 1 child nodes
if (node->left != NULL && node->right == NULL) { // has left child
if (node->parent->left == node) // is left child
node->parent->left = node->left;
else // is right child
node->parent->right = node->left;
delete node->value;
node->parent = NULL;
delete node;
}
if (node->left == NULL && node->right != NULL) { // has right child
if (node->parent->left == node) // is left child
node->parent->left = node->right;
else // is right child
node->parent->right = node->right;
delete node->value;
node->parent = NULL;
delete node;
}
// 2 children nodes
if (node->left != NULL && node->right != NULL) {
T aux;
BST<T>* auxNode = node->right;
while (auxNode->left != NULL)
auxNode = auxNode->left;
aux = *(auxNode->value);
if (auxNode->right != NULL) {
*(auxNode->value) = *(auxNode->right->value);
auxNode->right->parent = NULL;
auxNode->right->value = NULL;
auxNode->right = NULL;
delete auxNode->right;
}
else {
if (auxNode->parent->left == auxNode) // is left child
auxNode->parent->left = NULL;
else // is right child
auxNode->parent->right = NULL;
auxNode->value = NULL;
delete auxNode;
}
*(node->value) = aux;
}
}
return this;
}
};
#endif // BST_H
BST class 用法如下:
BST<int>* root = new BST<int>();
root->add(5);
root->add(2);
root->add(-17);
root->inOrderDisplay();
root->remove(5);
我提到所有方法都可以正常工作(我决定不 post 它们,因为它们不是这个问题的主题)。问题是,当我 运行 使用 Valgrind 测试文件时,它检测到一些内存泄漏,我确信它们的发生是因为缺少合适的析构函数(上面的析构函数会产生分段错误)。
编辑: 我添加了其他方法的代码
谢谢!
最难找到的错误是您决定不去查看的代码中的错误,因为您确信它们不相关。
无论如何,你的实现有一个明显的问题:在删除了一堆其他东西之后,你基本上是在做
class foo
{
~foo() { delete this; }
};
你应该换行:
node->value = NULL;
delete node->value;
像这样:
delete node->value;
node->value = NULL;
如果您首先分配 NULL
,则不会删除任何内容。
将 RAII 与 unique_ptr
结合使用可避免这些问题:
template <typename T>
class BST{
public:
BST() = default;
~BST() = default;
BST(const BST&) = delete;
BST& operator =(const BST&) = delete;
BST(BST&&) = delete;
BST& operator =(BST&&) = delete;
private:
std::unique_ptr<BST<T>> left;
std::unique_ptr<BST<T>> right;
BST<T>* parent = nullptr;
std::unique_ptr<T> value;
};
你的基本设计有点破,至少在我看来是这样。也就是说,如果您愿意跳过足够多的障碍,您可能可以让它发挥作用,但即使充其量它也可能总是至少有点笨拙。
我首先为树中的节点定义一个单独的 class。然后树本身将保存一个指向树根的指针,并定义树的大部分接口。
template <class T>
class Tree {
struct node {
node *parent;
node *left;
node *right;
T *value;
node(T *value)
: parent(nullptr), left(nullptr), right(nullptr), value(new T(value))
{
}
~node() {
delete(left);
delete(right);
delete(value);
}
} *root;
Tree() : root(nullptr) {}
~Tree() {
delete(root);
}
};
销毁不必显式递归。 delete(left)
(例如)将为左子节点(如果有的话)调用 dtor,并为其子节点调用 dtor,依此类推。当我们到达叶节点时,我们将得到(相当于)delete nullptr;
,它被定义为什么都不做,停止递归。
我检查了其他类似的主题,但 none 似乎对我有帮助。
我正在尝试为这个特定的 BST 实现编写一个析构函数。每个节点都包含一个指向父节点的指针、一个指向左节点的指针、一个指向右节点的指针和一个指向它包含的值的指针。 class 的开头是这样的:
#ifndef BST_H
#define BST_H
#include <iostream>
template <typename T>
class BST{
private:
BST<T> *left;
BST<T> *right;
BST<T> *parent;
T *value;
public:
BST() {
this->parent = NULL;
this->left = NULL;
this->right = NULL;
this->value = NULL;
}
~BST() {
removeRecursively(this);
}
void removeRecursively(BST<T>* node) {
if (node->left != NULL)
removeRecursively(node->left);
if (node->right != NULL)
removeRecursively(node->right);
if (node->left == NULL && node->right == NULL) {
if (node->parent->left == node)
node->parent->left = NULL;
if (node->parent->right == node)
node->parent->right = NULL;
node->parent = NULL;
node->value = NULL;
delete node->value;
delete node;
}
}
void add(T value) {
if (this->value == NULL) { // root-only case
this->value = new T;
*(this->value) = value;
}
else {
if (value < *(this->value)) {
if (this->left != NULL) // has left child
this->left->add(value);
else { // has no left child
this->left = new BST<T>;
this->left->value = new T;
this->left->parent = this;
*(this->left->value) = value;
}
}
else {
if (this->right != NULL) // has right child
this->right->add(value);
else { // has no right child
this->right = new BST<T>;
this->right->value = new T;
this->right->parent = this;
*(this->right->value) = value;
}
}
}
}
void inOrderDisplay() {
if (this->left != NULL)
this->left->inOrderDisplay();
std::cout << *(this->value) << " ";
if (this->right != NULL)
this->right->inOrderDisplay();
}
BST<T>* search(T value) {
if (*(this->value) == value)
return this;
else if (this->left != NULL && value < *(this->value))
return this->left->search(value);
else if (this->right != NULL && value > *(this->value))
return this->right->search(value);
else
return NULL;
}
BST<T>* remove(T value) {
BST<T>* node = search(value);
if (node != NULL) {
if (node->left == NULL && node->right == NULL) { // leaf node
delete node->value;
if (node->parent->left == node) // is left child
node->parent->left = NULL;
else // is right child
node->parent->right = NULL;
delete node;
}
// 1 child nodes
if (node->left != NULL && node->right == NULL) { // has left child
if (node->parent->left == node) // is left child
node->parent->left = node->left;
else // is right child
node->parent->right = node->left;
delete node->value;
node->parent = NULL;
delete node;
}
if (node->left == NULL && node->right != NULL) { // has right child
if (node->parent->left == node) // is left child
node->parent->left = node->right;
else // is right child
node->parent->right = node->right;
delete node->value;
node->parent = NULL;
delete node;
}
// 2 children nodes
if (node->left != NULL && node->right != NULL) {
T aux;
BST<T>* auxNode = node->right;
while (auxNode->left != NULL)
auxNode = auxNode->left;
aux = *(auxNode->value);
if (auxNode->right != NULL) {
*(auxNode->value) = *(auxNode->right->value);
auxNode->right->parent = NULL;
auxNode->right->value = NULL;
auxNode->right = NULL;
delete auxNode->right;
}
else {
if (auxNode->parent->left == auxNode) // is left child
auxNode->parent->left = NULL;
else // is right child
auxNode->parent->right = NULL;
auxNode->value = NULL;
delete auxNode;
}
*(node->value) = aux;
}
}
return this;
}
};
#endif // BST_H
BST class 用法如下:
BST<int>* root = new BST<int>();
root->add(5);
root->add(2);
root->add(-17);
root->inOrderDisplay();
root->remove(5);
我提到所有方法都可以正常工作(我决定不 post 它们,因为它们不是这个问题的主题)。问题是,当我 运行 使用 Valgrind 测试文件时,它检测到一些内存泄漏,我确信它们的发生是因为缺少合适的析构函数(上面的析构函数会产生分段错误)。
编辑: 我添加了其他方法的代码
谢谢!
最难找到的错误是您决定不去查看的代码中的错误,因为您确信它们不相关。
无论如何,你的实现有一个明显的问题:在删除了一堆其他东西之后,你基本上是在做
class foo
{
~foo() { delete this; }
};
你应该换行:
node->value = NULL;
delete node->value;
像这样:
delete node->value;
node->value = NULL;
如果您首先分配 NULL
,则不会删除任何内容。
将 RAII 与 unique_ptr
结合使用可避免这些问题:
template <typename T>
class BST{
public:
BST() = default;
~BST() = default;
BST(const BST&) = delete;
BST& operator =(const BST&) = delete;
BST(BST&&) = delete;
BST& operator =(BST&&) = delete;
private:
std::unique_ptr<BST<T>> left;
std::unique_ptr<BST<T>> right;
BST<T>* parent = nullptr;
std::unique_ptr<T> value;
};
你的基本设计有点破,至少在我看来是这样。也就是说,如果您愿意跳过足够多的障碍,您可能可以让它发挥作用,但即使充其量它也可能总是至少有点笨拙。
我首先为树中的节点定义一个单独的 class。然后树本身将保存一个指向树根的指针,并定义树的大部分接口。
template <class T>
class Tree {
struct node {
node *parent;
node *left;
node *right;
T *value;
node(T *value)
: parent(nullptr), left(nullptr), right(nullptr), value(new T(value))
{
}
~node() {
delete(left);
delete(right);
delete(value);
}
} *root;
Tree() : root(nullptr) {}
~Tree() {
delete(root);
}
};
销毁不必显式递归。 delete(left)
(例如)将为左子节点(如果有的话)调用 dtor,并为其子节点调用 dtor,依此类推。当我们到达叶节点时,我们将得到(相当于)delete nullptr;
,它被定义为什么都不做,停止递归。