Обход дерева в глубину без рекурсии
Алгоритмов обхода дерева в глубину (хоть с рекурсией, хоть без рекурсии) существует множество. В этом посте мне интересно рассмотреть практическую реализацию на языке JavaScript одного из них.
Я постараюсь реализовать на JavaScript обход дерева в глубину без рекурсии. На развилках при выборе пути приоритет будем отдавать правой (с позиции читателя, наблюдателя) ветви (ссылке).
Возьмем пример дерева из предыдущих постов. Вообще, по идее, задача любого алгоритма обхода дерева — это трансформация дерева из ветвящейся структуры в линию:
На этой иллюстрации сверху изображено дерево, рядом с которым нарисованы разноцветные линии (линии заглублений) со стрелками, показывающие порядок обхода дерева в глубину выбранным нами выше способом. Внизу эти же линии со стрелками и соответствующие им узлы выстроены в линию в том порядке, в котором производится обход узлов дерева. Каждая линия (из разноцветных) начинается в развилке дерева (кроме первой, которая начинается со ссылки на корневой узел) и заканчивается концевым узлом (листом дерева).
В предыдущем посте я писал, что для обхода дерева в глубину в качестве «памяти» используют стек. Посмотрим, как при обходе дерева в глубину меняется содержимое стека. В стеке будем сохранять ссылки на узлы из развилок дерева. Ссылку на узел я буду обозначать так: . К примеру, обозначение ссылки на корневой узел дерева будет таким: .
Запомним ссылку на наше дерево, которая является ссылкой на корень этого дерева:
Начнем обход дерева. Извлечем ссылку из памяти, перейдем в узел по ссылке. Мы оказались в узле 1. Далее путь разветвляется. Мы пойдем по правой ветке, то есть по ссылке , а левую ветку, то есть ссылку запомним в «памяти»:
Мы оказались в узле 2. Тут путь разветвляется. Мы пойдем по правой ветке, то есть по ссылке , а левую ветку, то есть ссылку запомним в «памяти»:
Мы оказались в узле 3. Это один из концевых узлов дерева (лист дерева), глубже здесь пройти уже нельзя. Проход красной линии (см. иллюстрацию выше) закончен. Для того, чтобы продолжить обход дерева, вернемся к последней развилке. Для этого извлечем последнюю ссылку из стека. Это ссылка . Перейдем в узел по этой ссылке.
Мы оказались в узле 4. Это еще один лист дерева, глубже здесь пройти уже нельзя. Проход оранжевой линии (см. иллюстрацию выше) закончен. Для того, чтобы продолжить обход дерева, вернемся к последней развилке. Для этого извлечем последнюю ссылку из стека. Это ссылка .
Давайте посмотрим ход изменения состояния стека с самого начала и до самого конца обхода дерева с иллюстрации выше. Теперь каждое состояние стека изобразим вертикально, чтобы всё было компактно (состояния тут идут слева направо: первое состояние, второе состояние и так далее):
Состояние стека, в котором он пуст, тут изображено двоеточием. Всего тут изображено 12 различных состояний стека во время обхода нашего дерева.
Думаю, будет логичным реализовать такой обход дерева на языке JavaScript с помощью двух вложенных циклов. Внешний цикл будет перебирать разноцветные линии (см. иллюстрацию выше), а внутренний цикл будет перебирать узлы на каждой из этих линий.
Каким должно быть условие окончания внешнего цикла? Во внешнем цикле должна происходить работа с «памятью» (стеком). По идее, внешний цикл должен закончиться, когда стек опустеет. Но как мы видим выше, в нашем примере стек пустел четырежды. В первый раз стек был пуст до начала обхода дерева, поэтому это состояние не будем учитывать. Во второй, третий и четвертый разы стек становился пуст после успешного извлечения из него информации о последней развилке (ссылке). Но у нас в руках уже была только что извлеченная ссылка для продолжения обхода дерева. Вот после обработки узла 10, если бы мы попытались продолжить обход дерева и попытались бы извлечь из «памяти» еще какую-либо информацию о развилках дерева, стек (естественно) оказался бы пуст, а это и стало бы сигналом к окончанию цикла.
Таким образом, условием окончания внешнего цикла должна быть пустота стека, обнаруженная после неудачной попытки извлечения из него очередной ссылки.
Возьмем для тестирования будущей функции обхода дерева реализацию на JavaScript нашего дерева, написанную в одном из моих предыдущих постов:
Только в данном случае ссылки, находящиеся в начале массива ссылок refs , мы будем считать левыми, а ссылки, находящиеся в конце массива refs — правыми.
Пишем на JavaScript функцию обхода дерева в глубину без рекурсии:
function traversal(tree) < let cur_ref; // текущая ссылка let memory = [tree]; // память (стек) // в начале память содержит ссылку на корень заданного дерева // внешний цикл, перебирающий линии заглублений // закончить цикл, если не получается извлечь ссылку из памяти (стека) while ( cur_ref = memory.pop() ) < // внутренний цикл обхода каждой линии заглубления дерева до листа while ( true ) < // . обработка данных узла. console.log(cur_ref.data); // просто выводим в консоль // если это лист, выйти из цикла if ( !cur_ref.refs ) break; // помещаем ветви, ведущие налево, в память (стек) for (let i = 0; i < cur_ref.refs.length - 1; i++) < memory.push( cur_ref.refs[i] ); >// переходим по ветви, ведущей направо cur_ref = cur_ref.refs[cur_ref.refs.length - 1]; > > >
В консоли из инструментов разработчика (в браузере) в результате должно быть выведено 10 строк, на каждой строке — данные (в данном случае — целое число) отдельного узла дерева. В данном случае — числа 1, 2, 3, . 10.
Источник
Алгоритмы 101: как реализовать обход дерева в JavaScript
Программирование и разработка
Понимание алгоритмов важно для каждого разработчика программного обеспечения. Алгоритмы — обычная часть любого собеседования по кодированию, решаете ли вы проблемы на JavaScript, Java или Python. Вы можете использовать алгоритмы для прохождения собеседований по кодированию, получить работу или решить специфические проблемы на работе.
Сегодняшнее руководство будет сосредоточено на алгоритмах обхода элементов в дереве. Обход дерева выглядит по-разному на разных языках программирования; мы будем использовать JavaScript. Начнём с обновления наших знаний о деревьях. Далее мы изучим несколько полезных алгоритмов и рассмотрим некоторые общие вопросы интервью.
Какие деревья?
В информатике деревья — это нелинейные структуры данных, представленные как набор узлов, соединённых рёбрами. Каждый узел хранит данные любого типа, и все узлы в дереве имеют один и тот же тип данных.
Древовидные структуры данных обычно используются для хранения информации с сохранением её иерархии, для реализации быстрого поиска, работы в сети и наследования.
Основные компоненты дерева включают:
- Корень, который является самым верхним узлом (он не имеет родительского узла). Обычно это начальная точка вашего дерева.
- Родительский узел, который подключён вниз к одному или двум узлам.
- Дочерний узел, который имеет входящую ссылку (или соединительную кромку) от родительского узла над ним.
- Родственные узлы — это узлы, которые имеют одного и того же родителя.
- В листовых узлах имеют родительские узлы, но нет дочерних узлов. Обычно это базовые / нижние узлы.
- Поддерево дерево удерживается в рамках большого дерева.
- Степень узла относится к числу поддеревьев в дереве.
- Глубина дерева относится к числу рёбер между определённым узлом и корнем.
- Высота узла относится к числу рёбер в самом длинном пути от заданного узла к узлу листа.
Как пересекать деревья
Пройденное дерево — это дерево, в котором каждый узел дерева был посещён. Обход — это процесс, включающий итерацию по всем узлам определённым образом.
В отличие от линейных структур данных (таких как массивы, связанные списки или очереди ), которые имеют только один логический способ обхода с помощью рекурсии, деревья можно обходить разными способами. Обычно существует 2 итерационных способа обхода деревьев:
Обход в глубину
Обход в глубину включает обход дерева сверху вниз. Они реализованы по принципу FILO (First In Last Out), как и структура данных стека. Сначала проходят левые поддеревья, затем правые поддеревья.
Это обычно наблюдается при обходе двоичного дерева. Двоичные деревья — это деревья, в которых каждый узел имеет не более 2 дочерних узлов. В приведённом ниже дереве узел со значением 1 будет первым, который будет помещён в стек, за ним последуют узлы со значениями 2, 3 и 4, затем он вернётся наверх к узлу со значением 5 вниз..
Когда достигается конец дерева, значения извлекаются из стека обратно в дерево.
Существует 3 типа обхода в глубину:
1. Обход по порядку
В обходе по порядку мы проходим левый дочерний элемент и его поддерево (я), затем посещаем корень, а затем проходим правый дочерний элемент и его поддерево (я). Требуется порядок «влево-корень-вправо».
Прежде чем мы рассмотрим образец кода для этого алгоритма, давайте попробуем обрисовать в общих чертах необходимые шаги:
- Начиная с корневого узла, мы рекурсивно проходим левый узел и его поддеревья.
- Мы начинаем чтение с левого листового узла, за которым следует его родительский и родственный узел.
- Мы делаем это рекурсивно, пока не вернёмся к корневому узлу, затем повторяем процесс для правого узла, начиная чтение с его самого левого листового узла.
Источник