从 Just Inorder Traversal 中找到 Preoder？

Question

我运行考了4天前的一道中考题，看不懂！

假设我们在对一棵树进行中序遍历时得到了答案，那么我们如何在先序遍历的情况下找到解决方案。我有以下示例：When inorder traversing a tree resulted E A C K F H D B G;

前序遍历是什么return？

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

谁能帮我学习一下？

编辑：我知道答案是：FAEKCDHGB。但是这是怎么计算的？

Answer 1

答案未定义。

看看那两棵树：

并且：

这两棵树的中序遍历相同，但是第一棵树的前序遍历为EACKFHDBG，而第二棵树的中序遍历为AECKFHDBG

因此，给定一个中序遍历，存在不止一种可能适合该遍历的二叉树。这是因为存在 n! 可能的排列（因此是有序遍历），而 there are much more binary trees. This guarantees (pigeonhole principle) 存在（至少一个）适合多棵树的有序遍历。

Answer 2

所以顺序是：

E A C K F H D B G

并且预订必须来自：

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

您应该继续为这些选项中的每一个绘制树，同时使其适合中序遍历，看看哪一个是可能的。

为此，对于前序遍历中的每个字符，围绕该字符将中序遍历分成两部分。

a.

我们知道 F 一定是根。围绕 F:

拆分中序遍历

        | F | 
 E A C K     H D B G

前序遍历的下一个字符是A。在 A:

附近拆分包含 A 的子树

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

下一个是E。没什么可分的。接下来是 K:

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

下一个是C。没有什么可拆分的。

下一个是D:

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

下一个是B:

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

我们已经完成了，不会再有拆分的可能了。现在运行在这棵树上进行前序遍历，你会得到：

F A E C K D H B G

这不是我们的出发点，所以我们就矛盾了。所以它不能是a。对其他人做同样的事情。

Answer 3

可能的 b 树之一是：

所以，前序遍历returns:

H K A E C F B D G

另一个是：

前序遍历给出：

H A E K C F B D G

还有一个是：

前序遍历给出：

K A E C H F B D G

，这是您的 none 个选项。欢迎任何人发表评论，因为我无法为给定的中序遍历给出任何其他二叉树..

我在考试中也遇到过这道题，但后来 google 搜索该题才知道答案是 b。哈哈

从 Just Inorder Traversal 中找到 Preoder？

Finding Preoder from Just Inorder Traversal?

algorithm

data-structures

tree

traversal

inorder