二分搜索树析构函数

Question

致力于用 C++ 实现我自己的 BST，以获得处理此类结构的经验。

我在实现析构函数时遇到了麻烦。我在我的研究中发现，一个人不能真正拥有递归析构函数（由于一个标志不允许在调用后在同一个对象上调用析构函数），但我不太确定其他方法可以成功清理树中的所有节点。

为了补偿，我创建了一个辅助函数 - 但是这会在“delete n”行上引发未解决的外部错误。有什么建议吗？

代码：

void BinSearchTree::Clear(tNode* n)
{
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    n = NULL;
    size--;
}

Answer 1

你可以有一个递归析构函数；你不能做的是两次删除同一个对象。

在 C++ 中删除树的典型方法可能是这样的：

BinSearchTree::~BinSearchTree()
{
   delete _rootNode;  // will recursively delete all nodes below it as well
}

tNode::~tNode()
{
   delete left;
   delete right;
}

关于未解决的外部错误 - 当您尝试编译/链接程序时是否抛出该错误？如果是这样，可能是因为 tNode 类的代码（特别是 tNode 析构函数，如果您声明了的话）不存在或没有编译到您的项目中。

Answer 2

之前的答案指出，未解决的外部错误可能是由链接器可以看到的翻译单元中声明但未定义的 tNode 析构函数引起的。

但是，您遇到了第二个错误：您似乎认为将 n 设置为 null 会执行一些实际无法执行的操作。指针值n 按值传递，而不是按引用传递，因此更改其值（例如通过分配NULL）在函数返回后不会产生任何影响。

当您清除树并期望根节点指针已设置为 NULL（此时它仍然是指向已释放内存的悬空指针）时，这可能会给您带来错误。结果将是运行时错误，而不是链接器错误。

void BinSearchTree::Clear(tNode **N)
{
    tNode * n = *N;
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    *N = NULL;
    size--;
}

会做你所期望的。

Answer 3

问题是，在您的类中，您可能声明节点结构具有自定义析构函数，但您没有提供它，因此在链接时编译器会抱怨缺少一块。

如果您不需要在析构函数中添加任何自定义代码，那么您只需从结构声明中删除析构函数，您的程序就可以正常编译。

但请注意，使用析构函数来销毁子节点完全没有问题（请参阅 Brendan Long 答案）。如果您在尝试时遇到问题，那么您遇到的问题一定是其他问题。

Answer 4

只需使用析构函数。听起来你的问题是你试图直接调用析构函数，但语言会为你处理这个问题。当您离开堆栈分配对象的范围或删除对象时，将调用它们。

您所需要的只是：

~BinSearchTree() {
    delete left;
    delete right;
}

delete 将调用它们的析构函数。

注意：删除 NULL 是完全安全的，它 没有效果。

Answer 5

自动化怎么样：

class BinSearchTree
{
    std::auto_ptr<tNode>   left;
    std::auto_ptr<tNode>   right;

    BinSearchTree(BinSearchTree const&);
    BinSearchTree& operator=(BinSearchTree const&); // private
};

现在破坏是自动的。 :-)

Answer 6

也可以使用递归，只需要将函数头改为：

void remove(node*& root) 

即可。