问题标签 [postorder]

我知道当给定二叉树的中序和前序遍历作为字符串时，您可以重建二叉树，但是仅在给定中序遍历的情况下，是否可以找到后序和/或前序遍历？

我有一个如下所示的预购遍历函数：

这实际上是可行的，但我认为使它成为邮政订单就像这样简单

但不幸的是，它的效果并不好。我想知道如何解决这个问题，也许我做错了一些简单的事情。或者它可能是完全错误的。

在二叉树中输入以下值（{18, 26, 52, 78, 45, 16, 67, 58, 73, 11}）时，您会收到此树：

PreOrder 和 InOrder 遍历都像我期望的那样工作。然而，当谈到 PostOrder (PO) 时，我收到的东西与我想象的不同。

据我了解，PO首先搜索左子树，然后搜索右子树，最后搜索节点（以根节点结尾）。

当通过这棵树在 PO 中遍历时，您最终会得到以下结果：{11, 16, 45, 58, 73, 67, 78, 52, 26, 18}。当写出这个结果背后的逻辑时，你会得到以下结果：从根开始，跟随完整的左，你最终在 11 这是你的第一个节点。之后，您上一层并获取其父级 (16)。你继续这样做直到你到达根（它不被包括在内，因为它不是一个leftChild）。一旦你通过了这个初始的左子树，你在右边向下一层并检查那里的 leftChilds。如果没有，你就往下一层，也就是我们找到 45 的地方。

此时我们有一个 {11, 16, 45} 的列表。我们继续这个并最终得到 58，这是我们在结果中的下一个值。这就是我困惑的地方：我们得到的下一个值是 73，与预期的 67 相反。为什么当找到另一个 leftChild（它的父级）时它会跳到 73？

以下代码负责遍历 PostOrder 中的树：

我猜这是因为值 73 的节点在 parentNode 之前处理（左右优先级），但为什么 45-52-78 三角形中不是这种情况呢？

如果 T 是具有多个节点的有序树。T 的前序遍历是否可能与 T 的后序遍历以相同的顺序访问节点？如果“是”，请您举个例子。如果“否”，您能否解释为什么它不会发生？

绘制前序、后序和中序的规则是：

1. 前序遍历：根、左、右
2. 后序遍历：左、右、根
3. 中序遍历：左根，右

例如，如果我们有这样的表达式：

ABCDEFGHIJKL,

我怎样才能为这个表达式分别绘制（预购、后购和有序）。有可能我们对每个都有不同形式的树（预购、后购和有序）。（即两种形式的预购）。如果我们同时拥有 (pre-order and and in-order) 或 (post-order and in-order)，我们就可以拥有唯一的树。在预购中，第一个节点是根节点（即“A”是根节点）。在后序中，最后一个节点是根节点（即“L”是根节点）。

绘制这些树是否有任何总体公式或“规则”？我画不出来

编辑：我的意思是如何从以下遍历的每个前序、后序和中序构造树：

ABCDEFGHIJKL,

我的数据结构和算法课的两个练习听起来像这样

构造前序遍历为：1、2、5、3、6、10、7、11、12、4、8、9，inode遍历为5、2、1、10、6、3、11的树， 7、12、8、4、9。

构造后序遍历为：5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1，inode遍历为5, 2, 1, 10, 6, 3, 11的树， 7、12、8、4、9。

我只需要绘制树的结构，而不用编程语言实现它。使这项任务变得更难的是树不是二叉树。我可以使用什么技术来建造树木？

我搜索了互联网和“you tube”，但没有找到任何好的教程。如何在“后缀”中绘制给定表达式的相应“二叉树”？

这个表达式在中缀和前缀中的外观如何？

我不知道我应该如何一步一步地做到这一点:(

18 5 1 + / 4 * 3 5 18 6 / - + -

笔记：

绘制前序、后序和中序的规则是： 1. 前序遍历：根，左，右 2. 后序遍历：左，右，根 3. 中序遍历：左根， 正确的

请问我考试需要它

N考虑在节点的二叉搜索树上进行后序遍历的时间复杂度。我知道O(N)在一般情况下需要访问所有节点，但是在最坏的情况下，当 BST 是一个列表时，复杂性是多少？我认为它需要O(N^2)，因为它会遍历N节点到达终点，然后N节点回到起点。这意味着N*N = N^2，所以我认为它是O(N^2)。这样对吗？

下面的方法是二叉树的后序遍历方法。我有一个看起来像这样的二叉树：

使用这些值，我预计输出为 8、4、18、17，因为 4 是 18 的根，而 post order 意味着最后打印根；但是，我得到了 4、8、18、17 的输出。感谢您提出任何建议。

我被要求绘制一个二叉搜索树，它的顺序和后序遍历都按顺序处理节点"ATTA"。我尝试了许多不同的方法，但最终只适用于其中一种遍历方法。