Javascript обход всего дерева

JS. Путешествие по деревьям

Деревья в программировании — это способ организации структур данных, в которых присутствуют уровни вложенности. Это действительно чем-то похоже на разветвленное дерево: от ствола отходят самые толстые ветки, на них растут веточки поменьше, и на самых тоненьких — листья. Чтобы добраться до самых дальних, приходится следовать за ними от самого корня (привет, «новая папка», созданная в 2012 на дне папки с фотографиями).

Если вы проходили курс «JS. Деревья» на Хекслете, то помните, что знакомство с такими структурами происходит на примере виртуальной файловой системы. Вооружившись рекурсией, как сборщик сахарного тростника – мачете, вы пробираетесь к новым знаниям через дебри папок и файлов, не подозревая, что на том конце вас ждут ОНИ — объекты и массивы!

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

I. Дерево — объект!

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

, >, country: < city: 'a citizen', >, 'Internet': < 'Hexlet.io': < 'Frontend JS': < 'Trees': 'this lesson' >, 'Blog': 'this post', >, >, >; 

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

  < const iter = (obj, path) => < const keys = _.keys(obj); return keys.flatMap((key) => < if (_.isObject(objJavascript обход всего дерева)) < const updatedPath = `$—> $`; return iter(objJavascript обход всего дерева, updatedPath); > const finalPath = `$ —> $` return `Follow the path [ $ ] to find $`; >); >; return iter(tree, '').join('\n'); >; 

Поскольку мы хотим получить целый маршрут, составленный из отдельных звеньев пути, нам не обойтись без аккумулятора. Первым делом добавим внутреннюю функцию iter, которая будет принимать на вход кусочки нашего пути и складывать их в маршрут через переменную path. Основная функция findPath должна вернуть iter, вызванную с нашим деревом и начальным отрезком пути в качестве аргументов (в нашем случае путь начинается с пустой строки », но мы могли бы написать здесь какую-то точку отсчета, если бы захотели).

Теперь проработаем внутреннюю логику iter. Чтобы обойти наше дерево-объект, нам понадобятся ключи. Получим их с помощью функции _.keys() из библиотеки Lodash, и применим к каждому наши условия, используя flatMap, поскольку от вложенности мы хотим избавиться.

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

  < if (_.isObject(objJavascript обход всего дерева)) < const updatedPath = `$—> $`; return iter(objJavascript обход всего дерева, updatedPath); > const finalPath = `$ —> $` // поскольку мы начинали с пустой строки, // в начале образовалась лишняя стрелка, // которую мы обрежем методом .slice return `Follow the path [ $ ] to find $`; // последнее значение и есть цель маршрута >); 

Обход дерева закончен, осталось соединить массив методом .join() и вот он, наш результат:

 trunk —> branch ] to find a leaf Follow the path [ roots —> trunk —> hollow ] to find a squirrel Follow the path [ country —> city ] to find a citizen Follow the path [ Internet —> Hexlet.io —> Frontend JS —> Trees ] to find this lesson Follow the path [ Internet —> Hexlet.io —> Blog ] to find this post 

Отлично! Все маршруты на месте, и выстроены в нужной последовательности. Согласитесь, это было несложно!

II. Дерево — массив!

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

Представьте себе, что, устав от изучения программирования, вы решили прогуляться по такому лесу. Вы внимательно смотрите на деревья — не покажется ли белочка? Если пушистая прыгунья действительно покажет ушки, нужно крикнуть «Смотри, там белка!» — надо же как-то развлекаться — ну и неплохо бы запомнить, где мы видели всех этих зверьков. (Просто оцените, как образно я рисую для вас картину происходящего, чтобы отвлечь от этого жуткого массива, брр. ).

Напишем функцию по поиску белок, и будем разбираться:

  < const [root, branches] = tree; if (!branches) < return []; >const flatBranches = _.flatten(branches); if (flatBranches.includes('squirrel')) < console.log(`Look at the $! There's a squirrel!`); return root; > return branches.flatMap((branch) => findSquirrels(branch)); >; 

Главное и самое неочевидное в работе с массивом — это выделить базовую структуру, на основании которой можно будет запустить рекурсию. В нашем случае она выглядит так: [‘узел’, [его потомки]]. Вынесем эти составляющие в константы, используя деструктуризацию. Теперь определим условие, при котором рекурсия должна остановиться. Очевидно, что если у элемента нет потомков, мы не можем продолжить движение по этой ветви, поэтому в такой ситуации мы будем возвращать пустой массив — все равно мы планируем избавиться от вложенности, и пустые массивы просто исчезнут.

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

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

 return branches.flatMap((branch) => findSquirrels(branch)); 

Наш обход завершен! В консоли — сообщения об увиденных нами белках, а функция вернула список мест, в которых прятались зверьки.

Осталось привести наш результат к более-менее информативному виду:

 squirrels in these locations: $!`); // Вот так выглядит финальный вывод: I found 3 squirrels in these locations: branch, hollow, trunk! 

Все белки найдены, и это победа!

P.S. В моем варианте лес получился немного безликим. Если хотите потренироваться с обходом деревьев самостоятельно, придумайте для каждого элемента уникальное имя (для ленивых подойдет что-то вроде ‘branch1-1’, ‘branch1-2’) и соберите полный «адрес» местонахождения белки — от корня дерева, до кончика беличьего хвоста, так, как мы делали в примере с объектом.

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

А если серьезно, обход деревьев должен стать для вас легкой задачкой, особенно, если немного поэкспериментировать с похожими примерами.

Удачи в освоении JavaScript!

Источник

Алгоритмы 101: как реализовать обход дерева в JavaScript

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В обходе по порядку мы проходим левый дочерний элемент и его поддерево (я), затем посещаем корень, а затем проходим правый дочерний элемент и его поддерево (я). Требуется порядок «влево-корень-вправо».

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

• Начиная с корневого узла, мы рекурсивно проходим левый узел и его поддеревья.
• Мы начинаем чтение с левого листового узла, за которым следует его родительский и родственный узел.
• Мы делаем это рекурсивно, пока не вернёмся к корневому узлу, затем повторяем процесс для правого узла, начиная чтение с его самого левого листового узла.

Источник