Как сделать обход дерева

Обновлено: 05.07.2024

После испытания функционала нашего дерева, пришло время расмотреть некоторые дополнительные модели использования этой структуры данных. Их можно разделить по трём способам доступа к узлам дерева. Различие будет состоять в порядке посещения каждого узла. Мы будем называть посещение узлов словом “обход”. Три способа обхода, которые будут рассмотрены, называются обход в прямом порядке, симметричный обход и обход в обратном порядке. Начнём с того, что дадим им более точные определения, а затем рассмотрим несколько примеров, где эти модели будут полезны.

Обход в прямом порядке В этом случае мы сначала посещаем корневой узел, затем рекурсивно обходим в прямом порядке левое поддерево, после чего таким же образом обходим правое. Симметричный обход Сначала мы симметрично обходим левое поддерево, затем посещаем корневой узел, затем - правое поддерево. Обход в обратном порядке Сначала делается рекурсивный обратный обход левого и правого поддеревьев, после чего посещается корневой узел.

Рассмотрим несколько примеров, иллюстрирующих каждый из этих типов обхода. Первым будет обход в прямом порядке. В качестве примера дерева возьмём эту книгу. Сама по себе она является корнем, чьи потомки - главы. Каждый раздел главы будет уже её потомком, каждый подраздел - потомком раздела и так далее. Рисунок 5 показывает урезанную версию книги (всего две главы). Обратите внимание, что алгоритм обхода будет работать с любым числом потомков, но мы пока сосредоточимся на двоичном дереве.

Рисунок 5: Представление книги в виде дерева

Предположим, вы хотите прочитать эту книгу от начала до конца. Обход в прямом порядке даст вам в точности такую последовательность. Начиная с корня дерева (узел Book), последуем инструкциям прямого обхода. Мы рекурсивно вызовем preorder к левому потомку Book (Chapter1), а потом уже к его левому потомку (Section 1.1). Section 1.1 является листом, так что больше рекурсивные вызовы не нужны. Закончив с ней, поднимемся по дереву вверх до Chapter 1. Нам по-прежнему надо посетить правое поддрево - Section 1.2. Как и раньше, сначала мы пойдём по его левому потомку (1.2.1), а затем посетим узел Section 1.2.2. Закончив с Section 1.2, мы вернёмся к Chapter 1, потом к Book и проделаем аналогичную процедуру для Chapter 2.

Код для описанного обхода дерева на удивление элегантный - в основном благодаря рекурсии. Листинг 2 демонстрирует код прямого обхода двоичного дерева.

Может возникнуть вопрос: в каком виде лучше написать алгоритм вроде обхода в прямом порядке? Должна ли это быть функция, просто использующая дерево как структуру данных, или это будет метод внутри класса “дерево”? В листинге 2 показан вариант с внешней функцией, принимающей двоичное дерево в качестве параметра. В частности, элегантность такой функции заключается в базовом случае - проверке существования дерева. Если её параметр равен None , то она возвращается без выполнения каких-либо действий.

Листинг 2

Также preorder можно реализовать, как метод класса BinaryTree . Код для этого случая показан в листинге 3. Обратите внимание, что происходит, когда мы перемещаем код “снаружи” “внутрь”. В общем, tree просто заменяется на self . Однако, так же требуется изменить и базовый случай. Внутренний метод проверяет наличие левого и правого потомков до того, как делается рекурсивный вызов preorder .

Листинг 3

Какой из двух способов реализации preorder лучше? Ответ: для данного случая - в виде внешней функции. Причина в том, что вы очень редко хотите просто обойти дерево. В большинстве случаев вам нужно сделать что-то ещё во время использования одной из моделей обхода. Фактически, уже в следующем примере мы увидим, что модель обхода postorder очень близка к коду, который мы писали ранее для вычисления дерева синтаксического разбора. Исходя из изложенного, для оставшихся моделей мы будем писать внешние функции.

Алгоритм обхода postorder показан в листинге 4. Он очень близок к preorder , за исключением того, что мы перемещаем вызов печати в конец функции.

Листинг 4

Мы уже видели распространённое использование обхода в обратном порядке - вычисление дерева синтаксического разбора. Взгляните на листинг 1 ещё раз. Что мы делаем, так это вычисляем левое поддерево, потом правое и собираем их в корне через вызов функции оператора. Предположим, наше двоичное дерево будет хранить только данные для математического выражения. Давайте перепишем функцию вычисления более приближённо к коду postorder из листинга 4 (см. листинг 5).

Листинг 5

Обратите внимание, что код в листинге 4 аналогичен коду из листинга 5, за исключением того, что вместо печати ключей в конце функции, мы их возвращаем. Это позволяет сохранить ответы рекурсивных вызовов в строках 6 и 7. Потом они используются вместе с оператором в строке 9.

Последним рассмотренным в этом разделе обходом будет симметричный обход. В его ходе мы сначала посещаем левое поддерево, затем корень и потом уже правое поддерево. Листинг 6 показывает этот алгоритм в коде. Заметьте: во всех трёх моделях обхода мы просто меняем расположение оператора print по отношению к двум рекурсивным вызовам.

Листинг 6

Если мы применим простой симметричный обход к дереву синтаксического разбора, то получим оригинальное выражение, правда без скобок. Давайте модифицируем базовый алгоритм симметричного обхода, чтобы он позволял восстановить версию выражения с полной расстановкой скобок. Единственное изменение, которое надо внести в базовый шаблон, - это печатать левую скобку до рекурсивного вызова с левым поддеревом и правую скобку после рекурсивного вызова с правым поддеревом. Модифицированный код показан в листинге 7.

Листинг 7

Программирование и разработка

Понимание алгоритмов важно для каждого разработчика программного обеспечения. Алгоритмы — обычная часть любого собеседования по кодированию, решаете ли вы проблемы на JavaScript, Java или Python. Вы можете использовать алгоритмы для прохождения собеседований по кодированию, получить работу или решить специфические проблемы на работе.

Сегодняшнее руководство будет сосредоточено на алгоритмах обхода элементов в дереве. Обход дерева выглядит по-разному на разных языках программирования; мы будем использовать JavaScript. Начнём с обновления наших знаний о деревьях. Далее мы изучим несколько полезных алгоритмов и рассмотрим некоторые общие вопросы интервью.

Какие деревья?

В информатике деревья — это нелинейные структуры данных, представленные как набор узлов, соединённых рёбрами. Каждый узел хранит данные любого типа, и все узлы в дереве имеют один и тот же тип данных.

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

Основные компоненты дерева включают:

Корень, который является самым верхним узлом (он не имеет родительского узла). Обычно это начальная точка вашего дерева.
Родительский узел, который подключён вниз к одному или двум узлам.
Дочерний узел, который имеет входящую ссылку (или соединительную кромку) от родительского узла над ним.
Родственные узлы — это узлы, которые имеют одного и того же родителя.
В листовых узлах имеют родительские узлы, но нет дочерних узлов. Обычно это базовые / нижние узлы.
Поддерево дерево удерживается в рамках большого дерева.
Степень узла относится к числу поддеревьев в дереве.
Глубина дерева относится к числу рёбер между определённым узлом и корнем.
Высота узла относится к числу рёбер в самом длинном пути от заданного узла к узлу листа.

Как пересекать деревья

Пройденное дерево — это дерево, в котором каждый узел дерева был посещён. Обход — это процесс, включающий итерацию по всем узлам определённым образом.

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

Поиск / обход в глубину (DFS).
Поиск / обход в ширину (BFS).

Обход в глубину

Обход в глубину включает обход дерева сверху вниз. Они реализованы по принципу FILO (First In Last Out), как и структура данных стека. Сначала проходят левые поддеревья, затем правые поддеревья.

Это обычно наблюдается при обходе двоичного дерева. Двоичные деревья — это деревья, в которых каждый узел имеет не более 2 дочерних узлов. В приведённом ниже дереве узел со значением 1 будет первым, который будет помещён в стек, за ним последуют узлы со значениями 2, 3 и 4, затем он вернётся наверх к узлу со значением 5 вниз..

Когда достигается конец дерева, значения извлекаются из стека обратно в дерево.

Существует 3 типа обхода в глубину:

1. Обход по порядку

Прежде чем мы рассмотрим образец кода для этого алгоритма, давайте попробуем обрисовать в общих чертах необходимые шаги:

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Подразумевается, что в процессе обхода каждый узел будет затронут только один раз. По большому счёту, всё так же, как и в обходе любой коллекции, используя цикл или рекурсию. Только в случае деревьев способов обхода больше, чем просто слева направо и справа налево.

В данном курсе используется один порядок обхода — обход в глубину, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать на википедии либо в рекомендуемых Хекслетом книгах.

Обход в глубину (Depth-first search)

Один из методов обхода дерева (графа в общем случае). Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.

Рассмотрим данный алгоритм на примере следующего дерева:

Каждая нелистовая вершина обозначена звёздочкой. Обход начинается с корневого узла.

Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребёнка независимо;
Внутри первого рекурсивного вызова оказывается следующее поддерево:

Повторяем логику первого шага. Проваливаемся на уровень ниже.

Внутри оказывается листовой элемент E . Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх.
Снова оказываемся в ситуации:

В этом месте, как мы помним, рекурсивный вызов запускался на каждом из детей. Так как первый ребёнок уже был посещён, второй рекурсивный вызов заходит в узел F и выполняет там свою работу. После этого происходит возврат выше, и всё повторяется до тех пор, пока не дойдёт до корня.

Печать на экран в примере выше — это лишь демонстрация. В реальности же нас интересует либо изменение дерева, либо агрегация данных по нему. Агрегацию данных рассмотрим позже, а сейчас разберём изменение.

Допустим, мы хотим реализовать функцию, которая меняет владельца для всего дерева, то есть всех директорий и файлов. Для этого нам придётся соединить две вещи: рекурсию, разобранную выше, и код обновления узлов, который изучался в прошлом уроке.

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

Алгоритмов обхода дерева в глубину (хоть с рекурсией, хоть без рекурсии) существует множество. В этом посте мне интересно рассмотреть практическую реализацию на языке JavaScript одного из них.

Я постараюсь реализовать на JavaScript обход дерева в глубину без рекурсии. На развилках при выборе пути приоритет будем отдавать правой (с позиции читателя, наблюдателя) ветви (ссылке).

Возьмем пример дерева из предыдущих постов. Вообще, по идее, задача любого алгоритма обхода дерева — это трансформация дерева из ветвящейся структуры в линию:

На этой иллюстрации сверху изображено дерево, рядом с которым нарисованы разноцветные линии (линии заглублений) со стрелками, показывающие порядок обхода дерева в глубину выбранным нами выше способом. Внизу эти же линии со стрелками и соответствующие им узлы выстроены в линию в том порядке, в котором производится обход узлов дерева. Каждая линия (из разноцветных) начинается в развилке дерева (кроме первой, которая начинается со ссылки на корневой узел) и заканчивается концевым узлом (листом дерева).

Запомним ссылку на наше дерево, которая является ссылкой на корень этого дерева:

Мы оказались в узле 3. Это один из концевых узлов дерева (лист дерева), глубже здесь пройти уже нельзя. Проход красной линии (см. иллюстрацию выше) закончен. Для того, чтобы продолжить обход дерева, вернемся к последней развилке. Для этого извлечем последнюю ссылку из стека. Это ссылка . Перейдем в узел по этой ссылке.

Мы оказались в узле 4. Это еще один лист дерева, глубже здесь пройти уже нельзя. Проход оранжевой линии (см. иллюстрацию выше) закончен. Для того, чтобы продолжить обход дерева, вернемся к последней развилке. Для этого извлечем последнюю ссылку из стека. Это ссылка .

И так далее.

Давайте посмотрим ход изменения состояния стека с самого начала и до самого конца обхода дерева с иллюстрации выше. Теперь каждое состояние стека изобразим вертикально, чтобы всё было компактно (состояния тут идут слева направо: первое состояние, второе состояние и так далее):
Состояние стека, в котором он пуст, тут изображено двоеточием. Всего тут изображено 12 различных состояний стека во время обхода нашего дерева.

Думаю, будет логичным реализовать такой обход дерева на языке JavaScript с помощью двух вложенных циклов. Внешний цикл будет перебирать разноцветные линии (см. иллюстрацию выше), а внутренний цикл будет перебирать узлы на каждой из этих линий.

Таким образом, условием окончания внешнего цикла должна быть пустота стека, обнаруженная после неудачной попытки извлечения из него очередной ссылки.

Возьмем для тестирования будущей функции обхода дерева реализацию на JavaScript нашего дерева, написанную в одном из моих предыдущих постов:
Только в данном случае ссылки, находящиеся в начале массива ссылок refs , мы будем считать левыми, а ссылки, находящиеся в конце массива refs — правыми.

Пишем на JavaScript функцию обхода дерева в глубину без рекурсии:

Запуск обхода дерева:

В консоли из инструментов разработчика (в браузере) в результате должно быть выведено 10 строк, на каждой строке — данные (в данном случае — целое число) отдельного узла дерева. В данном случае — числа 1, 2, 3, . 10.

Читайте также: