- Обход в глубину (DFS) с использованием стека. Идея: идём до конца по одной ветке, возвращаемся назад (к последнему «развилку») с помощью стека.
- Варианты DFS (порядок посещения корня):
- Прямой (Pre-order). Корень -＞ Левый -＞ Правый.
- Симметричный (In-order). Левый -＞ Корень -＞ Правый.
- Обратный (Post-order). Левый -＞ Правый -＞ Корень.
- Алгоритм на примере Pre-order:
- Создать пустой стек.
- Положить в стек корень дерева.
- Пока стек не пуст:
- Извлечь верхний узел из стека (top -＞ pop) и обработать его.
- Положить в стек его правого потомка (если есть).
- Положить в стек его левого потомка (если есть).
- Обход в ширину (BFS) с использованием очереди. Идея: Посещаем узлы уровень за уровнем. Сначала корень, потом всех его непосредственных потомков, потом потомков потомков и т.д.
- Алгоритм:
- Создать пустую очередь.
- Положить в очередь корень дерева.
- Пока очередь не пуста:
- Извлечь узел из начала очереди (front -＞ pop) и обработать его.
- Положить в конец очереди всех его потомков (сначала левого, потом правого).
- Результат: узлы в порядке уровней.
Информатика • 11 класс
30
Использование стека и очереди для обхода дерева (Python)
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках