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