Основная цель этого поста - объяснить, как создавать, просматривать и искать деревья в javascript, используя реальный пример.

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

1. Администратор магазина должен иметь возможность добавлять, удалять и редактировать категории.
2. Категория может иметь одну или n подкатегорий.
3. Товар должен иметь название, цену и категорию, к которой он принадлежит. к. (Категория является обязательным полем здесь, нет смысла иметь товар без категории)

Из этого списка требований можно представить себе следующую диаграмму классов:

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

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

Вы можете спросить себя: «Где деревья занимают место во всей этой чепухе?». Что ж, нам нужно подумать о способе структурирования наших категорий и подкатегорий, и для этого мы собираемся использовать деревья. Взгляните на следующий пример:

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

  1. Добавьте в дерево категорию (узел). Для этой операции мы возьмем родительский узел, к которому мы хотим добавить категорию, в качестве параметра. Примерно так: / _addNode (parentNode) {…} /
  2. Удалите категорию (узел) из дерева. Для этого нам понадобится только узел, который нужно удалить в качестве параметра.
  3. Операция поиска, которая принимает категорию в качестве параметра и возвращает узел.
  4. Я также хотел бы знать листы конкретного узла. Это пригодится, когда пользователь нажимает на категорию, мы будем искать листы, а затем перебирать список продуктов и смотреть, есть ли у какого-либо продукта хотя бы один из листов (категорий), в случае, если он есть, мы должны показать это. Например, пользователь щелкает категорию «Ноутбуки». Концы этого узла: Asus, MacBook Air и MacBook Pro. Мы просматриваем список продуктов и отображаем только те продукты, которые имеют одну из подкатегорий этого дерева.

Наконец, давайте напишем код для хранения структуры нашего дерева.

Траверс

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

Он определяет функцию goThrough, которая принимает узел, в нашем случае при первом вызове этой функции мы собираемся передать корневой узел.

Внутри функции goThrough первое, что нужно сделать, - это вызвать функцию обратного вызова с этим конкретным узлом, затем она перебирает все дочерние элементы узла и выполняет рекурсивный вызов с каждым дочерним элементом. Чтобы пролить свет на этот код, давайте посмотрим, как мы будем использовать эту функцию.

Добавить узел

Метод _addNode принимает значение и parentValue, к которому мы хотим добавить узел.

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

Мы проверяем, является ли наш корневой узел нулевым, если это так, мы просто устанавливаем наш корневой узел так, чтобы он указывал на наш недавно созданный узел.

Если наш корневой узел не равен нулю, мы проходим по дереву, чтобы найти parentValue, и как только мы находим его, мы проталкиваем наш вновь созданный узел нашим потомкам parentNode.

Удалить узел

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

Узел поиска

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

Показать листы

Метод display leafs принимает parentValue, например, «Notebooks», и нацелен на отображение всех конечных категорий этого узла, в нашем примере это «Asus», «MacBook Pro» и «MacBook Air».

Первая строка проверяет, является ли параметр, передаваемый функции, строкой или узлом. Если это строка, мы выполняем операцию поиска для получения фактического узла.

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

Мы храним каждый лист в массиве и, наконец, сглаживаем этот массив непосредственно перед возвратом. Таким образом, результатом будет что-то вроде [«Asus», Macbook Pro »,« MacBook Air »].

Теперь у нас есть все операции, необходимые для выполнения некоторых тестов.

Надеюсь, вы нашли этот пост полезным! Если у вас есть вопросы или предложения, не стесняйтесь их размещать!