二进制搜索树析构函数

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析构函数,如果你声明了它)不存在或者没有被编译到你的项目中.