Просмотр исходного текста страницы Обходы деревьев (in-order, pre-order, post-order)

Обход дерева — это процесс посещения (обработки) каждого узла в дереве ровно один раз. Существуют различные алгоритмы обхода деревьев, которые отличаются порядком посещения узлов. Основные типы обходов для бинарных деревьев включают in-order (центрированный), pre-order (прямой) и post-order (обратный) обходы.

== Основные понятия ==

# '''Обход дерева (Tree Traversal)''': Процесс посещения каждого узла в дереве ровно один раз.
# '''Корень (Root)''': Верхний узел дерева.
# '''Левое поддерево (Left Subtree)''': Поддерево, состоящее из левого потомка узла и всех его потомков.
# '''Правое поддерево (Right Subtree)''': Поддерево, состоящее из правого потомка узла и всех его потомков.
# '''Рекурсия (Recursion)''': Метод решения задачи, при котором функция вызывает саму себя для решения подзадач.
# '''Стек (Stack)''': Структура данных, основанная на принципе LIFO (Last In, First Out), используемая для хранения информации о вызовах функций при рекурсивных обходах.

== Типы обходов ==

# '''In-order (центрированный)''': Обход, при котором сначала посещается левое поддерево, затем корень, затем правое поддерево.
# '''Pre-order (прямой)''': Обход, при котором сначала посещается корень, затем левое поддерево, затем правое поддерево.
# '''Post-order (обратный)''': Обход, при котором сначала посещается левое поддерево, затем правое поддерево, затем корень.

== In-order (центрированный) обход ==

'''In-order''' обход — это обход бинарного дерева, при котором сначала посещается левое поддерево, затем корень, затем правое поддерево.

# '''Алгоритм''':
## 1. Рекурсивно обойти левое поддерево.
## 2. Посетить корень.
## 3. Рекурсивно обойти правое поддерево.
# '''Применение''': In-order обход часто используется для вывода элементов бинарного дерева поиска (BST) в отсортированном порядке.
# '''Пример реализации (Python)''':
## ```python
## class Node:
##     def __init__(self, data):
##         self.data = data
##         self.left = None
##         self.right = None
##
## def inorder_traversal(node):
##     if node:
##         inorder_traversal(node.left)
##         print(node.data, end=" ")
##         inorder_traversal(node.right)
## ```

=== Пример in-order обхода: ===

Для следующего дерева:

```
      1
     / \
    2   3
   / \
  4   5
```

In-order обход будет следующим: 4 2 5 1 3

== Pre-order (прямой) обход ==

'''Pre-order''' обход — это обход бинарного дерева, при котором сначала посещается корень, затем левое поддерево, затем правое поддерево.

# '''Алгоритм''':
## 1. Посетить корень.
## 2. Рекурсивно обойти левое поддерево.
## 3. Рекурсивно обойти правое поддерево.
# '''Применение''': Pre-order обход часто используется для создания копии дерева или для вывода дерева в виде префиксного выражения.
# '''Пример реализации (Python)''':
## ```python
## class Node:
##     def __init__(self, data):
##         self.data = data
##         self.left = None
##         self.right = None
##
## def preorder_traversal(node):
##     if node:
##         print(node.data, end=" ")
##         preorder_traversal(node.left)
##         preorder_traversal(node.right)
## ```

=== Пример pre-order обхода: ===

Для следующего дерева:

```
      1
     / \
    2   3
   / \
  4   5
```

Pre-order обход будет следующим: 1 2 4 5 3

== Post-order (обратный) обход ==

'''Post-order''' обход — это обход бинарного дерева, при котором сначала посещается левое поддерево, затем правое поддерево, затем корень.

# '''Алгоритм''':
## 1. Рекурсивно обойти левое поддерево.
## 2. Рекурсивно обойти правое поддерево.
## 3. Посетить корень.
# '''Применение''': Post-order обход часто используется для удаления дерева или для вывода дерева в виде постфиксного выражения.
# '''Пример реализации (Python)''':
## ```python
## class Node:
##     def __init__(self, data):
##         self.data = data
##         self.left = None
##         self.right = None
##
## def postorder_traversal(node):
##     if node:
##         postorder_traversal(node.left)
##         postorder_traversal(node.right)
##         print(node.data, end=" ")
## ```

=== Пример post-order обхода: ===

Для следующего дерева:

```
      1
     / \
    2   3
   / \
  4   5
```

Post-order обход будет следующим: 4 5 2 3 1

== Сводная таблица обходов ==

{| class="wikitable"
|-
! Обход
! Порядок посещения
! Применение
|-
! In-order
| Левое поддерево -> Корень -> Правое поддерево
| Вывод элементов BST в отсортированном порядке
|-
! Pre-order
| Корень -> Левое поддерево -> Правое поддерево
| Создание копии дерева, вывод дерева в виде префиксного выражения
|-
! Post-order
| Левое поддерево -> Правое поддерево -> Корень
| Удаление дерева, вывод дерева в виде постфиксного выражения
|}

== Обходы без рекурсии ==

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

=== Пример in-order обхода без рекурсии (Python): ===

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder_traversal_iterative(root):
    stack = []
    current = root

    while True:
        if current is not None:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()
            print(current.data, end=" ")
            current = current.right
        else:
            break
```

== Применение ==

Обходы деревьев используются в широком спектре приложений, включая:

# '''Вывод данных в определенном порядке''': Обходы деревьев позволяют выводить данные, хранящиеся в дереве, в определенном порядке (например, в отсортированном порядке для бинарных деревьев поиска).
# '''Копирование и преобразование деревьев''': Обходы деревьев используются для создания копий деревьев или для преобразования деревьев в другие структуры данных.
# '''Вычисление выражений''': Обходы деревьев используются для вычисления выражений, представленных в виде деревьев.
# '''Поиск и замена данных''': Обходы деревьев используются для поиска и замены данных в дереве.

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