什么使树遍历预先排序或有序？

Question

为什么通过根、左和右遍历树称为预排序？这不应该是有序的，因为根总是在第一位吗？

为什么这样称呼它对我来说没有意义，因为根始终是第一个元素。

Answer 1

我们总是有这样的限制：左孩子在右孩子之前被访问。

主要区别在于根在哪里。

• 如果根在两个孩子之前，我们称之为先序。（根，左，右）

• 如果根位于两个孩子之后，我们将其称为后序。（左、右、根）

• 如果根位于两个孩子之间，我们称其为有序。（左、根、右）

Answer 2

前缀是指什么时候应该放置根节点的内容。

给定这棵树，您可以用多种方式表示它：

• 预购：根首先被放置（当时左和右的孩子），所以列表将如下所示：

[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

和其他的一样，根在最后，但左右子列表保持相同的后序属性。

此外，其他可能的遍历可以是

• 按级别：元素按它们在树上的级别从左到右排序

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