问题标签 [postorder]

为什么有必要为迭代后序遍历而不是为中序或前序迭代遍历保留已访问标志。

是否可以在不保留已访问标志的情况下进行后订单遍历？

我很好地理解了前序、中序和后序树遍历算法。（参考）。我了解一些用途：按顺序遍历二叉搜索树的顺序，克隆树的预顺序。但是我一辈子都无法想出一个需要后序遍历才能完成的现实世界任务。

你可以给我一个例子吗？并且：你能给我更好的预购遍历用途吗？

编辑：除了表达式树和 RPN，谁能给我一个例子？这真的是所有后订单都有好处吗？

我试图使用堆栈进行后序遍历.....但是我遇到了一个错误，类型为无效操作数到二进制，，，，，，，，，请告诉我如何克服这种情况。下面是代码。

给定起始根节点，我有一个递归函数返回所有子树节点。

对于以下树结构：

当我尝试这样迭代时：

该函数返回唯一的 A 值。

我希望使用带有递归的 yield-return 并检索 Preorder 中的元素（在本例中为 A、B、C、D、E）。

（如果我将收益回报放在 foreach 之前，foreach 将永远不会发生）。

这可能吗？

是否可以仅通过操作 ast.NodeVisitor.generic_visit() 在 Python 中对 ast.NodeVisitor 的实例进行后序遍历？我这样做了：

这给了我：

我希望它给我：

我该怎么做？请我被困住了。

我想采用这种非递归后序二叉树遍历的伪代码算法，并将其实际实现到代码中。本质上，我假设创建两个并行堆栈，一个用于保存对节点的引用，另一个用于保存整数值 1 或 2，以判断是否访问了左子树或右子树。我根据他们给我的内容创建了算法，但由于某种原因，它只打印了一些数字，并且没有按正确的顺序打印，我觉得我按照它应该的方式解释了它，但它刚刚开始工作，任何帮助都会很好。

这是他们想让我做的事情：

这是我的实现：

是否存在这种情况为真的二叉树？

我不这么认为，除非二叉树只包含一个根节点。

我给出了二叉树（不是二叉搜索树）的有序遍历的结果：

E、D、B、A、G、F、H、C

现在我必须找出给定有序遍历的同一棵树的后序遍历结果。

任何人都可以为此建议我任何算法吗？

PS：有没有办法从有序结果中勾勒出树本身？

我对不同站点上的许多文章感到非常困惑，这些文章涉及Binary Search Tree从任何一个遍历（pre，post或in-order）或其中任何两个的组合构建一个。例如，在这个页面上，它说给定pre,post或level顺序遍历，连同in-order遍历，可以构造BST. 但是在这里和那里，他们向我们展示了如何单独构建一个BST。pre-order此外，他们在这里向我们展示了如何构造BSTfrom givenpre和post-ordertraversals。在其他一些站点中，我找到了一个BST仅从post-order遍历构造 a 的解决方案。

现在我知道给定inorder和pre-order遍历，可以唯一地形成一个BST. 至于我提供的第一个链接，虽然他们说我们不能构造BSTfrompre-order和post-order，但我不能对post-order数组进行排序以获取它的inorder遍历，然后使用它和pre-order数组来形成BST? 这与第四个链接中的解决方案相同还是不同？并且pre-order仅给出，我可以对它进行排序以获得in-order，然后使用它和pre-order来获得BST. 同样，这是否必须与链接 2 和 3 的解决方案不同？

具体来说，什么足以唯一地生成BST？如果不需要唯一性，那么我可以简单地对其进行排序以获取遍历，并从中递归地in-order构建 N 个可能的 s 之一。BST

I have read that one of the applications of postorder traversal in trees is to compute disk space. Why can't we use preorder traversal? Won't we get the same answer?