1

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

我如何确定这一点？

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

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
4

3 回答 3

3

这种中序遍历有多个预序等价物。您不能仅从字母中看出原始树结构是什么，因为没有括号对字母进行分组。

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

树 1

订购： EACKFHDBG
预购：FKAECDHBG

树 2

订购： EACKFHDBG
预购：KAECHFDGB

更新

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

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

我们从哪个答案开始并不重要，所以让我们先尝试答案（D）：FEAKDCHBG

  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）不是正确的解决方案。

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

于 2016-05-25T18:28:36.917 回答
0

这个问题的答案是 b) FAEKCDHGB

于 2018-11-04T17:09:53.403 回答
0

使用从中序和前序遍历构造树的技术，并使用选项 A、B、D { C 中给出的中序和前序遍历绘制树，因为从给定的顺序中我们可以看到 F（最内层或中间节点）是根节点，因为在中序遍历中，根位于左右子节点的中间。因此，从这 4 个选项中，C 选项不能为真，因为预购 Root 在开始时，但在选项 C 中，根是 E，这是不可能的。

于 2021-12-22T10:32:58.523 回答