是什么使树遍历有序或有序? [英] What makes a tree traversal pre-order or in-order?

问题描述

为什么通过根，左和右遍历树称为预排序?难道不是有序的，因为根始终是第一个?

Why is a tree traversal via root, left and right called pre-order? Shouldn't that be in-order, because the root is always first?

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

It does not makes sense to me why it is called that way, because the root is always the first element.

推荐答案

前缀是指何时应放置根节点的内容.

The prefix refers to when the content of the root node should be placed.

鉴于这棵树，您可以用多种方式表示它:

Given this tree, you can represent it in various ways:

• 预订: Root (第 left 和 right 个子级)放在第一位，因此该列表将如下所示:

• Pre-order: Root is placed first (then left and right children), so the list will look as follows:

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

在左侧和右侧子树子列表中，保留了预购.

Inside left and right sub-tree sublists the preorder is kept.

• 有序:首先放置左子对象(如果需要，可以分析)，然后放置 root 和右孩子.看起来像这样:

• In-order: Left child is placed (analized if you like) first, then root and right child. It will look like this:

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

现在，列表的第一部分表示左侧的子树，将根放在其后，最后是右侧的子树.在这里，顺序也保留在左右子树子列表中.

Now, first part of the list represents the left sub tree, the root is placed after, and finally, the right sub-tree. Here, inorder is also kept inside left and right sub-trees sublists.

^{顺序遍历可以看作是从左到右扫描.}

^{In-order traversal can be seen as a left-to-right scanning.}

• 后订单:首先对左子进行分析，然后对 right 子进行分析，最后对 root :

• Post-order: Left child analized first, then the right child and finally the root:

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

与其他相同，根在末尾，但左右子列表保留相同的 postorder 属性.

Same as the others, root is at the end, but left and right sublist keep the same postorder property.

另外，其他可能的遍历可以

Additionally, other posible traversal can be

• 按级别:元素按级别从左到右排列在树上

• By levels: elements are placed sorted by their level on the tree, left to right

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

这篇关于是什么使树遍历有序或有序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！