非递归析构函数二叉搜索树使用堆栈

我正在考虑使用一堆二进制节点指针来创建非递归析构函数。这段代码会运行吗？非递归析构函数二叉搜索树使用堆栈

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中找到使用二叉搜索树遍历的堆栈实现。

来源

2013-04-27 Jack Smother

什么问题？如果你只是想知道它是否有效，编译并测试它。 – 2013-04-27 08:40:46

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

我遇到的最大问题是你的算法的设计不清楚。获得基于堆栈的递归算法版本的常用方法是首先获取递归版本（至少在纸上），然后将递归排除。在这种情况下，你的标准post-order traversal，实现以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是删除节点。现在，你可以在没有显式递归的情况下实现这个功能（并且如Non recursive Depth first search algorithm的回答所示，对于某些树遍历问题，这可能非常简单）。然而，它可以论证为什么你会想在这种情况下？递归调用使用程序自己的堆栈，而您想隐式地使用自己的数据结构进行递归。只有在删除tail end recursion时，优点是黑白的，因为这里递归确实被消除了，而不是用堆栈模拟。

如果你确实按照去除递归的路线，看起来你的代码可能会变得非常难看：请参阅http://leetcode.com/2010/10/binary-tree-post-order-traversal.html和Non-recursive post order traversal。有可能你的隐式递归代码在时间和/或空间上的表现会比原始的，明确递归的更差。这当然可能是更多的车！

来源

2013-04-27 22:41:23 TooTone

非递归析构函数二叉搜索树使用堆栈

回答

相关问题