Что делает обход дерева предзаказом или в порядке?

Question

Почему обход дерева через корень, левый и правый называется предварительным заказом?Разве это не должно быть в порядке, потому что корень всегда первый?

Мне не имеет смысла, почему он так называется, потому что корень всегда первый элемент.

Answer 1

Префикс относится к , когда должно быть помещено содержимое корневого узла.

Учитывая это дерево, выможет представлять его различными способами:

• Предварительный заказ : Root размещается первым (затем влево и вправо children), поэтому список будет выглядеть следующим образом:

[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 также хранится в подсписках левого и правого поддеревьев.

^{Обход по порядку можно рассматривать как слева направо сканирование.}

• Пост-заказ : Левый дочерний анализ сначала, затем правый дочерний и, наконец, root :

[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

Рассмотрим это простое дерево:

  A
 /  \
B    C

Обход предзаказа : ABC.

Термин содержит слово pre.pre означает раньше.Таким образом, корень перед любым из его детей.Обратите внимание, что A предшествует как B, так и C

Обход после отправки заказа : BCA

Термин содержит слово post.post означает после.Таким образом, корень после любого из его детей.Обратите внимание, что A следует после B и C

Обход Inorder : BAC

Термин содержит слово In.In означает внутри (посередине).Таким образом, корень в середине своих детей.Обратите внимание, что A находится между B и C

Answer 3

У нас всегда есть ограничение на посещение левого ребенка перед правым ребенком.

Основное различие заключается в том, где находится корень.

• Если корень равен до обоим дочерним элементам, мы называем его предварительным порядком. (Root, Left, Right)

• Если корень равен после обоих потомков, мы называем его порядком.(Слева, справа, корень)

• Если корень находится между обоими дочерними элементами, мы называем его по порядку.(Слева, корень, справа)