3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

Деревья и алгоритмы обхода для ЕГЭ по информатике

Разберем ключевые концепции работы с деревьями, которые встречаются в заданиях ЕГЭ.

1. Реализация дерева с помощью ссылочных структур

Дерево — это связный ациклический граф, состоящий из вершин (узлов) и рёбер (ссылок).

Ссылочные структуры — способ реализации дерева, где каждый узел содержит данные и ссылки на дочерние узлы.

Реализация на Python:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        
    def add_child(self, child_node):
        self.children.append(child_node)

Структура дерева:

A (корень)

2. Двоичные (бинарные) деревья

Двоичное дерево — дерево, где каждый узел имеет не более двух дочерних элементов (левый и правый).

Реализация бинарного дерева:

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Пример бинарного дерева:

Типы бинарных деревьев

Тип	Описание	Пример
Полное	Все уровни полностью заполнены	A B C
Сбалансированное	Высоты поддеревьев отличаются не более чем на 1	A B C
Вырожденное	Каждый узел имеет только одного потомка	A B C

3. Построение дерева для арифметического выражения

Арифметическое выражение можно представить в виде дерева, где:

Листья — операнды (числа)
Внутренние узлы — операторы (+, -, *, /)

Пример: (2 + 3) * (5 — 1)

—

Алгоритм построения:

1. Найти оператор с наименьшим приоритетом (обычно это корень)

2. Левое поддерево — выражение слева от оператора

3. Правое поддерево — выражение справа от оператора

4. Рекурсивно применить алгоритм к подвыражениям

4. Рекурсивные алгоритмы обхода дерева

Обход дерева — процесс посещения всех узлов дерева в определенном порядке.

Типы обходов бинарного дерева:

Прямой (pre-order)

1. Посетить корень

2. Обойти левое поддерево

3. Обойти правое поддерево

Центрированный (in-order)

1. Обойти левое поддерево

2. Посетить корень

3. Обойти правое поддерево

Обратный (post-order)

1. Обойти левое поддерево

2. Обойти правое поддерево

3. Посетить корень

Реализация рекурсивных обходов:

def pre_order(node):
    if node:
        print(node.value)  # Посещаем корень
        pre_order(node.left)  # Обходим левое поддерево
        pre_order(node.right)  # Обходим правое поддерево

def in_order(node):
    if node:
        in_order(node.left)  # Обходим левое поддерево
        print(node.value)  # Посещаем корень
        in_order(node.right)  # Обходим правое поддерево

def post_order(node):
    if node:
        post_order(node.left)  # Обходим левое поддерево
        post_order(node.right)  # Обходим правое поддерево
        print(node.value)  # Посещаем корень

5. Использование стека и очереди для обхода дерева

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

Стек — для обхода в глубину (DFS)
Очередь — для обхода в ширину (BFS)

Обход в глубину (DFS) с использованием стека:

1. Поместить корень в стек

2. Пока стек не пуст:

— Извлечь узел из стека

— Обработать узел

— Добавить правого потомка в стек

— Добавить левого потомка в стек

Реализация DFS на стеке:

def dfs_stack(root):
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)  # Обрабатываем узел
        if node.right:     # Сначала добавляем правого потомка
            stack.append(node.right)
        if node.left:      # Затем левого (будет обработан первым)
            stack.append(node.left)

Обход в ширину (BFS) с использованием очереди:

1. Поместить корень в очередь

2. Пока очередь не пуста:

— Извлечь узел из очереди

— Обработать узел

— Добавить левого потомка в очередь

— Добавить правого потомка в очередь

Реализация BFS на очереди:

from collections import deque

def bfs_queue(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)  # Обрабатываем узел
        if node.left:      # Добавляем левого потомка
            queue.append(node.left)
        if node.right:     # Добавляем правого потомка
            queue.append(node.right)

Сравнение обходов

Тип обхода	Структура данных	Порядок	Применение
DFS (в глубину)	Стек	Вертикальный	Поиск решения, копирование дерева
BFS (в ширину)	Очередь	Горизонтальный	Поиск кратчайшего пути, минимальная глубина

Примеры задач

Пример 1: Построение дерева выражения

Постройте дерево для выражения: a * b + c / d

Решение:

Пример 2: Обход дерева

Дано дерево:

Результат обхода in-order: B, A, D, C, E

Пример 3: Реализация BFS

Реализуйте обход в ширину для данного дерева:

def bfs(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        for child in node.children:
            queue.append(child)

Заключение

Деревья — фундаментальная структура данных в информатике. Понимание принципов работы с деревьями, их обхода и реализации необходимо для успешной сдачи ЕГЭ.

Для закрепления материала рекомендуется решать практические задачи на построение деревьев и реализацию алгоритмов обхода.