Обходы деревьев (in-order, pre-order, post-order)

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

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

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

Типы обходов

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

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

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

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

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

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

```

     1
    / \
   2   3
  / \
 4   5

```

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

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

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

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

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

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

```

     1
    / \
   2   3
  / \
 4   5

```

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

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

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

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

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

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

```

     1
    / \
   2   3
  / \
 4   5

```

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

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

Обход	Порядок посещения	Применение
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

```

Применение

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

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

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