c++ - 二叉搜索树析构函数

Question

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

我在实现析构函数时遇到了问题。我在我的研究中发现，一个人不能真正拥有递归析构函数(由于一个标志不允许在被调用后对同一个对象调用析构函数)，但我真的不确定任何成功清理树中所有节点的其他方法。

作为补偿，我创建了一个辅助函数——但是这会在“delete n”行上抛出一个 Unresolved external 错误。有什么建议吗？

代码:

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;
}

关于 Unresolved external 错误——是在您尝试编译/链接程序时抛出的错误吗？如果是这样，可能是因为 tNode 类的代码(特别是 tNode 析构函数，如果您声明了一个)不存在或没有被编译到您的项目中。