从中序遍历中找到先序遍历？

Question

我遇到了一道期中考试题，四天前出的，但我不理解它！

假设我们已经有了树的中序遍历结果，那么如果是先序遍历，我们如何找出解决方案呢？我有以下例子：当中序遍历结果为E A C K F H D B G时；

那么先序遍历将返回什么？

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

谁能以学习的方式帮助我？

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

- user4627889

Answer 1

所以中序遍历是：

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. 其他也同理。

- IVlad

---

@Prof.KosiNoura - 是的。 - IVlad

哇，今天我选错答案后终于明白怎么做了... :) - sigdelsanjog

在第三步中，子树的根元素不应该是K，其左子节点是C吗？ - Vishist Varugeese

Answer 2

答案是未定义的。

看看这两棵树：

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

并且：

   A
 /  \
E    C 
      \
       K
        \
         F 
          \
           H 
            \
             D 
              \
               B
                \
                 G

那两棵树的中序遍历相同，但第一棵树的先序遍历为EACKFHDBG，而第二棵树的中序遍历为AECKFHDBG。

因此，对于给定的中序遍历，有很多可能的二叉树符合该遍历。这是因为有n!种可能的排列（因此中序遍历也有这么多种），而二叉树的数量则更多。这保证了（鸽笼原理）存在至少一个适合多个树的中序遍历。

- amit

---

感谢您的有用回答，但我认为我们必须考虑多种选择！我想。 - user4627889

实际上，你把最后一句话倒过来了。二叉树的数量是一个卡特兰数，它只呈指数增长（大约是4^n）。n!要大得多（事实上，很容易看出任何排列都只会产生一棵二叉搜索树，但多个排列可以适用于同一未标记的树）。 - Erick Wong

@ErickWong 这个（加泰罗尼亚语）是具有相同节点的二叉树数量（即您只关心拓扑结构，而不关心每个节点的标记）。 - amit

Answer 3

其中一种可能的B树是：

因此，前序遍历返回：

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

这些都不是你的选项。欢迎任何人发表评论，因为我无法想出给定中序遍历的其他二叉树。

我在考试中也有过这个问题，但是通过谷歌搜索得知答案是b。哈哈。

- vinaych