7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Code
  2. JavaScript

Структуры данных в JavaScript: дерево

Scroll to top
Read Time: 12 mins
This post is part of a series called Data Structures in JavaScript.
Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List

Russian (Pусский) translation by Masha Kolesnikova (you can also view the original English article)

Final product imageFinal product imageFinal product image
What You'll Be Creating

Деревья являются одной из наиболее часто используемых структур данных в веб-разработке. Это утверждение справедливо как для разработчиков, так и для пользователей. Каждый веб-разработчик, который писал HTML и загружал его в веб-браузер, создавал дерево, которое называется Document Object Model (DOM). Каждый пользователь Интернета, который, в свою очередь, потреблял информацию в Интернете, получал ее в виде дерева - DOM.

Теперь, вот кульминация: статья, которую вы читаете в данный момент, отображается в вашем браузере как дерево! Абзац, который вы читаете, представлен как текст в элементе <p>; Элемент <p> вложен внутри элемента <body>; И элемент <body> вложен внутри элемента <html>.

Вложение данных аналогично генеалогическому дереву. Элемент <html> является родителем, элемент <body> является дочерним, а элемент <p> является дочерним элементом элемента <body>. Если эта аналогия дерева кажется вам полезной, то вам определенно понравится идея того, что во время нашей реализации дерева будет использовано еще больше аналогий.

В этой статье мы создадим дерево, используя два разных метода обхода дерева: поиск по глубине (DFS) и поиск по ширине (BFS). (Если слово обход незнакомо вам, считайте его посещением каждого узла дерева.) Оба этих типа обхода выделяют различные способы взаимодействия с деревом; Более того, оба путешествия включают использование структур данных, которые мы рассмотрели в этой серии. DFS использует стек, а BFS использует очередь для посещения узлов. Это круто!

Дерево (поиск по глубине и поиск по ширине)

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

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

Чтобы представить это соотношение, мы используем стрелки, указывающие от генерального директора на VP. Позиция, такая как генеральный директор, является узлом; Отношения, которые мы создаем от генерального директора к VP, являются указателями. Чтобы создать больше связей в нашем графике, мы просто повторяем этот процесс - у нас есть узел, указывающий на другой узел.

На концептуальном уровне я надеюсь, что узлы и указатели вам и так понятны. На практическом уровне мы можем воспользоваться более техническим примером. Рассмотрим DOM. DOM имеет элемент <html> в качестве позиции верхнего уровня (корневой узел). Этот узел указывает на элемент <head> и <body>. Этот процесс повторяется для всех узлов в DOM.

Красота этого дизайна заключается в способности встраивать узлы: элемент <ul>, например, может содержать много элементов <li>, вложенных в него; Кроме того, каждый элемент <li> может иметь узлы-соседи <li>. Это странно, но забавно и верно!

Операции над деревом

Поскольку каждое дерево содержит узлы, которые могут быть отдельным конструктором из дерева, мы будем описывать операции для обоих конструкторов: Node и Tree.

Узел

  • data хранит значение.
  • parent указывает на родительский элемент узла.
  • children указывают на следующий узел в списке.

Дерево

  • _root указывает на корневой узел дерева.
  • traverseDF(callback) обходит узлы дерева с DFS.
  • traverseBF(callback) перемещает узлы дерева с BFS.
  • contains(data, traversal) ищет узел в дереве.
  • add(data, toData, traverse) добавляет узел в дерево.
  • remove(child, parent) удаляет узел из дерева.

Реализация дерева

Теперь давайте напишем код для дерева!

Свойства узла

Для нашей реализации мы сначала определим функцию с именем Node, а затем конструктор с именем Tree.

Каждый экземпляр узла содержит три свойства: dataparent и children. Первое свойство содержит данные, связанные с узлом. Второе свойство указывает на один узел. Третье свойство указывает на множество дочерних узлов.

Свойства дерева

Теперь давайте определим наш конструктор для Tree, который включает в себя конструктор Node в его определении:

Tree содержит две строки кода. Первая строка создает новый экземпляр Node; Вторая строка назначает node как корень дерева.

Определения Tree и Node требуют только лишь нескольких строк кода. Однако этих строк достаточно, чтобы помочь нам имитировать иерархические данные. Чтобы доказать этот момент, давайте использовать некоторые примеры для создания экземпляра Tree (и, косвенно, Node).

Благодаря существованию parent и children, мы можем добавлять узлы как дочерние элементы _root, а также присваивать _root родителям этих узлов. Другими словами, мы можем имитировать создание иерархических данных.

Методы дерева

Затем мы создадим следующие пять методов:

Tree

  1. traverseDF(callback)
  2. traverseBF(callback)
  3. contains(data, traversal)
  4. add(child, parent)
  5. remove(node, parent)

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

1 из 5: traverseDF(callback)

Этот метод обходит дерево с поиском в глубину.

traverseDF(callback) имеет параметр с именем callback. Если это непонятно из имени, считается, что callback является функцией, которая будет называться позже в traverseDF(callback).

Тело traverseDF(callback) включает в себя другую функцию с именем recurse. Эта функция является рекурсивной функцией! Другими словами, она сама себя вызывает. Используя шаги, упомянутые в комментариях recurse, я опишу общий процесс, который recurse использует для перемещения по всему дереву.

Вот эти шаги:

  1. Сразу вызовите recurse с корневым узлом дерева в качестве аргумента. В настоящий момент currentNode указывает на текущий узел.
  2. Входим в цикл for и проходимся по каждому элементу currentNode, начиная с первого дочернего элемента.
  3. Внутри тела цикла for вызывается recurse с дочерним элементом currentNode. Каждый конкретный дочерний элемент зависит от текущей итерации цикла for.
  4. Когда currentNode больше не имеет дочерних элементов, мы выходим из цикла for и вызываем callback, который мы передали во время вызова traverseDF(callback).

Шаги 2 (выход из функции), 3 (вызов себя) и 4 (callback) повторяются до тех пор, пока мы не пройдем каждый узел дерева.

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

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

В следующем примере показано, как дерево будет пройдено через traverseDF(callback). Чтобы обойти дерево, я создам его в следующем примере. Подход, который я буду использовать в данный момент, не идеален, но он работает. Лучшим подходом было бы использовать add(value), который мы реализуем на шаге 4 из 5.

Теперь давайте обратимся к traverseDF(callback).

2 из 5: traverseBF(callback)

Этот метод использует поиск по ширине для перемещения по дереву.

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

Теперь давайте пройдем traverseBF(callback) тот же обратный вызов, который мы использовали для traverseDF(callback).

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

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

Наше определение traverseBF(callback) содержит много логики. По этой причине я объясню логику в управляемых шагах:

  1. Создайте экземпляр Queue.
  2. Добавьте узел, который вызвал traverseBF(callback) к экземпляру Queue.
  3. Объявите переменную с именем currentNode и инициализируйте ее к node, который мы только что добавили в нашу очередь.
  4. Пока currentNode указывает на узел, выполните код внутри цикла while.
  5. Используйте цикл for для итерации по дочерним элементам currentNode.
  6. Внутри тела цикла for добавьте каждый дочерний элемент в очередь.
  7. Возьмите currentNode и передайте его как аргумент в callback.
  8. Перенесите currentNode на удаляемый узел из очереди.
  9. Пока currentNode не указывает на узел - каждый узел в дереве был посещен - повторите шаги с 4 по 8.

3 из 5: contains(callback, traversal)

Давайте определим метод, который позволит нам искать конкретное значение в нашем дереве. Чтобы использовать любой из наших методов обхода дерева, я определил contains(callback, traversal) таким образом, чтобы он принимал два аргумента: данные для поиска и тип обхода.

В теле contains(callback, traversal), мы используем метод с именем call для передачи this и callback. Первый аргумент связывает traversal с деревом которые вызывало contains(callback, traversal); второй аргумент - это функция, которая вызывается на каждом узле нашего дерева.

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

4 из 5: add(data, toData, traversal)

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

add(data, toData, traversal) определяет три параметра. Первый параметр, data, используется для создания нового экземпляра Node. Второй параметр toData используется для сравнения с каждым узлом в дереве. Третий параметр, traversal, является типом обхода дерева, используемого в этом методе.

В теле add(data, toData, traversal) мы объявляем три переменные. Первая переменная, child  инициализируется как новый экземпляр Node. Вторая переменная, parent, инициализируется как null; Но позже она укажет на любой узел в дереве, который соответствует значению toData. Перераспределение parent происходит в третьей переменной, которую мы объявляем - callback.

callback - это функция, которая сравнивает toData с данными data каждого узла. Если оператор if возвращает значение true, то parent назначается узлу, который сравнивался в инструкции if.

Фактическое сравнение каждого узла с toData происходит в contains(callback, traversal). Тип обхода и callback должны быть переданы в качестве аргументов contains(callback, traversal).

Наконец, если parent существует в дереве, мы помещаем child в parent.children; Мы также назначаем parent родительскому элементу child. Иначе мы выкидываем ошибку.

Давайте воспользуемся add(data, toData, traversal) на примере:

Вот более сложный пример для add(addData, toData, traversal):

5 из 5: remove(data, fromData, traversal)

Чтобы завершить нашу реализацию Tree, мы добавим метод с именем remove(data, fromData, traversal). Подобно удалению узла из DOM, этот метод удалит узел и все его дочерние элементы.

Подобно add(data, toData, traversal), метод remove обходит дерево, чтобы найти узел, содержащий второй аргумент fromData. Если этот узел найден, то parent указывает на него.

В этот момент мы достигаем нашего первого if выражения. Если parent не существует, мы выдаем ошибку. Если parent существует, мы вызываем findIndex() с parent.children и данные, которые мы хотим удалить из дочерних узлов parent. (findIndex() - вспомогательный метод, который я определил ниже.)

Внутри findIndex() происходит следующая логика. Если какой-либо из узлов в parent.children содержит данные, соответствующие data, переменной index присваивается целое число. Если ни одно из данных у дочерних элементов не соответствует data, index сохраняет значение по умолчанию undefined. В последней строке findIndex() мы возвращаем index.

Теперь мы возвращаемся назад к remove(data, fromData, traversal). Если index равен undefined, возникает ошибка. Если index определен, мы используем его для сращивания узла, который хотим удалить из дочерних элементов parent; Мы также присваиваем удаленный дочерний элемент переменной childToRemove.

Наконец, мы возвращаем childToRemove.

Полная реализация дерева

Наша реализация Tree завершена. Взгляните - мы многое сделали:

Вывод

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

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.