binary-tree - 当中序遍历一棵树的结果是 E A C K F H D B G 时，前序等价物是多少？

Question

我在绘制这棵树时遇到了麻烦，因为我不知道何时将值放在树的右侧或左侧，因为它由字母组成。

我如何确定这一点？

编辑添加: 我有以下选择作为可能的预序遍历:

A.  F A E K C D B H G
B.  F A E K C D H G B
C.  E A F K H D C B G
D.  F E A K D C H B G 

Answer 1

此中序遍历有多个前序等价物。您无法仅根据字母判断原始树结构是什么，因为没有括号将字母分组。

例如，这里有两种可能的树，它们会产生您所说的中序遍历，但具有不同的先序遍历。还有很多其他的。

顺序:E A C K F H D B G
预购:F K A E C D H B G

顺序:E A C K F H D B G
预购:K A E C H F D G B

---

更新

根据您的评论，我发现这实际上是某种测试或家庭作业问题。由于给定了中序遍历和一些可能的前序遍历，问题就变成了，我们可以重建一棵满足这两种排序的树吗？事实证明，是的，这绝对是可行的；你只需尝试每一个并解决它即可。

那么我们应该如何处理这个问题呢？那么，我们对中序和前序遍历了解多少？
我们知道，中序遍历给出了树上从左到右的节点的绝对顺序。相反，前序遍历从根开始向下列出节点，始终首先列出当前节点，然后是左子树，然后是右子树。因此，一种方法是遍历前序遍历(因为第一个字母为我们提供了根节点)，并尝试将每个节点添加到树中，使用中序遍历作为指导来决定是否应该将该节点放置到前一个的左侧或右侧。

我们从哪个答案开始并不重要，所以我们先尝试答案 (D):F E A K D C H B G

1. 首先放置根节点 F:

                                 F
   

2. 显然，下一个节点 E 连接到 F，但它是左节点还是右节点？我们来看一下中序遍历。 E是在F之前还是之后？它位于前面，因此这意味着它必须是左节点。

                                 F
                                /
                               E
   

3. 接下来我们有 A。现在树中存在三个空点:E 的左侧、E 的右侧和 F 的右侧。在中序遍历中，A 在 E 之后但在 F 之前。所以这意味着它必须位于 E 的右侧。

                                 F
                                /
                               E
                                \
                                 A
   

4. K 在预订中排在第二位。它应该去树的哪里？中序表示 K 在 A 之后但在 F 之前。树中与前序一致的 3 个开放点(A 的左侧、A 的右侧或 F 的右侧)中，唯一可以容纳的位置是 A 的右侧.

                                 F
                                /
                               E
                                \
                                 A
                                  \
                                   K
   

5. 下一个是D。中序遍历表明 D 必须在 F 之后，并且我们的树中只有一个空位适用于此:F 的右侧。

                                 F
                                / \
                               E   D
                                \
                                 A
                                  \
                                   K
   

6. 现在我们遇到了麻烦。根据先序，下一个要放置的节点是 C。根据中序，C 必须位于 K 之前、A 之后，这意味着将它放在 K 的左侧。但是，我们不能这样做，因为这会改变预序!请记住，预排序是从上到下、从左到右，因此放置的每个新节点要么必须直接位于最后放置的节点的下方，要么位于树中该节点的上方和右侧。我们放置的最后一个节点是 D，这意味着 C 必须连接到它才能满足先序。但如果C与D相连，它就不能与K相连。所以我们有一个矛盾。这意味着答案 (D) 不是正确的解决方案。

希望现在您了解如何遍历遍历并从中构建树。我将让您尝试其他三个答案并找出哪个是正确的。