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

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

我猜树的根没有设置为 Null，因此它包含垃圾，而 print 函数正在迭代随机垃圾树。确保在清除方法结束时将 NULL 设置为树根。

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

  else
  {
    clearNodes(root);
    root = NULL;
    return true;
  }     

}

我假设当你打印时 - 你检查树根是否为空以确定树是否为空。

Answer 2

我假设 "checking that the nodes are deleted" 等同于 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
}

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

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

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

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

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

recursively delete every nodes in binary tree

c++

recursion

binary-search-tree