是什么让树遍历预订或有序？

Question

为什么树通过根遍历，左右称为预订？不应该是有序的，因为根始终是第一个？

对我来说，为什么以这种方式调用它是没有意义的，因为根始终是第一个元素。

Answer 1

前缀指的是应该放置根节点的内容。

鉴于此树，您可以通过各种方式表示它：

• 预订：首先放置Root（然后是左右子），因此列表如下所示：

[41, 20, 11, 29, 32, 65, 50, 91, 72, 99]
 ^   --------------  ------------------
 |        |                     |
 |        |                     |-----Right sub-tree
 |        | 
 |        |----Left sub-tree
 |
 |------ Root of the tree

在左侧和右侧子树子列表中，保留了预订。

• 有序：首先放置左孩子（如果你喜欢，分析），然后是根和右孩子。它看起来像这样：

[11, 20, 29, 32, 41, 50, 65, 72, 91, 99]
 --------------  |   ------------------
      |          |            |
      |          |            |------- Right sub-tree
      |          |
      |          |---- Root of the tree
      |
      |----- Left sub-tree

现在，列表的第一部分代表左子树，根放在后面，最后是右子树。在这里，inorder也保留在左右子树的子列表中。

有序遍历可以看作是从左到右的扫描。

• 下订单：左孩子先分析，然后是右孩子，最后是根：

[11, 32, 29, 20, 50, 72, 99, 91, 65, 41]
 --------------  ------------------  |
       |                 |           |---- Root of the tree
       |                 |        
       |                 |----- Right sub-tree
       | 
       |------ Left sub-tree

与其他相同，root在最后，但左右子列表保持相同的postorder属性。

---

另外，其他可行的遍历也可以

• 按级别：元素按树的级别从左到右排序

[41, 20, 65, 11, 29, 50, 91, 32, 72, 99]
 |   ------  --------------  ----------
 |      |          |                |-----Level 3
 |      |          |
 |      |          |----- Level 2
 |      |
 |      |------ Level 1
 |
 |----- Level 0 (aka, the root of the tree)

Answer 2

我们总是有限制，在正确的孩子面前访问左孩子。

主要区别在于根源在哪里。

• 如果根在两个孩子之前，我们称之为预订。（Root，Left，Right）
• 如果根在两个孩子之后，我们称之为后序。 （左，右，根）
• 如果根位于两个孩子之间，我们称之为有序。 （左，根，右）

Answer 3

考虑这个简单的树：

  A
 /  \
B    C

预订遍历：ABC。

该术语包含pre一词。 pre之前的意思。因此根源在于它的任何一个孩子。请注意，A在B和C之前

邮购顺序：BCA

该术语包含post一词。 post意味着之后。所以根源是它的任何一个孩子。请注意，A是在B和C之后

顺序遍历：BAC

该术语包含In一词。 In意思是内部（中间）。所以根源在其子女的中间。请注意，A位于B和C之间