c++ - 递归删除二叉树中的每个节点

Question

以下是递归删除二叉搜索树中每个节点的代码:

template <class T>
bool BST<T>::clear()
{
    if(root == NULL)
    {
        cout << "Empty" << endl;
        return false;
    }
    else
    {
        clearNodes(root);
        return true;
    }

}

template <class T>
void BST<T>::clearNodes(BTNode<T> *cur)
{
    if(cur == NULL)
    {
        return;
    }

    clearNodes(cur->left);
    clearNodes(cur->right);

    delete cur;
}

在我的主要功能中，当我尝试打印出内容以检查运行我的清除功能后节点是否被删除时，不知何故我在这里遇到了奇怪的显示:

我可以知道我的节点实际上是通过上面的清除函数删除的吗？

感谢您的指导!

Answer 1

我假设“检查节点是否被删除”相当于 clear() 打印空。您的算法缺少重置已删除节点的步骤。

修改后的版本是

template <class T>
void BST<T>::clearNodes(BTNode<T>* &cur) //reference on pointer
{
  if (cur==NULL)
  {
    return;
  }

  clearNodes(cur->left);
  clearNodes(cur->right);

delete cur;
cur = NULL; //neccessary
}

编辑:关于更改的说明 一旦观察到节点未设置为 null 的问题，第一次迭代将是在每次调用后设置有问题的节点，即

clearNodes(cur->right);
cur->right = NULL;

这将责任交给了调用者，并且他有一个潜在的缺陷，因为调用者迟早会忘记设置为 null 或可能会设置错误的值。因此，您想在 clearNodes 中设置。为了修改函数内的指针，您需要传递指向它的指针或引用。在 C++ 中，我更喜欢传递引用。因此签名变成了¨

void BST<T>::clearNodes(BTNode<T>* &cur);