0

我正在考虑使用一堆二进制节点指针制作一个非递归析构函数。这段代码会运行吗？

binaryNode* parent = root;
while (!empty())
{
  if (parent->left)
  {
    stack1.push(parent)
    parent = parent->left;
  }
  else if (parent->right)
  {
    stack1.push(parent)
    parent = parent->right;
  } else 
  {
    delete parent;
    parent = stack1.pop();
  }
}

我还没有完成基本程序，所以上面的代码没有经过测试。我觉得应该没什么问题。虽然它没有经过测试运行，但我跟踪了一个二叉搜索树，它运行得很好。另外，我在 stackoverflow 中找不到具有二叉搜索树遍历的堆栈实现。

4

1 回答 1

0

对我来说，看起来你的代码有很多问题，但也很难确定你在实现代码时的意图是什么（即哪些问题是 C++ 的问题，哪些是“设计”的问题-level”伪代码）。代码中的一个问题是，delete parent唯一释放了引用的对象所占用的空间parent。因此，当您弹出堆栈时，您最终可能会重新执行if (parent->left)分支，因此delete再次 ing 相同的对象。而你似乎只是delete叶节点。

我遇到的最大问题是您的算法设计不清楚。获得基于堆栈的递归算法版本的常用方法是首先获得递归版本（至少在纸面上），然后分解递归。在这种情况下，您的标准后订单遍历，实现为对do_action, 下面的调用，与node = root, 是沿线

do_action(node)
    if node has left descendant
        do_action(left descendant)
    if node has right descendant
        do_action(right descendant)
    perform action on node

在您的情况下，action是删除节点。现在，您可以在没有显式递归的情况下实现这一点（正如对非递归深度优先搜索算法的回答所示，对于某些树遍历问题来说，这可能非常简单）。但是，在这种情况下您为什么要这样做是有争议的？递归调用使用程序自己的堆栈，而您希望使用自己的数据结构隐式递归。只是在去掉尾端递归的情况下，优点是非黑即白的，因为这里真正去掉了递归，而不是用栈来模拟。

如果您确实走上了删除递归的路线，那么您的代码似乎会变得非常难看：请参阅http://leetcode.com/2010/10/binary-tree-post-order-traversal.html和Non-recursive post顺序遍历。您的隐式递归代码在时间和/或空间上的性能可能会比原始的显式递归代码更差。它肯定有更多的错误！

于 2013-04-27T22:41:23.513 回答