Сегодня мы поговорим об удивительном мире деревьев… разумеется, о деревьях структур данных. Один из способов представления дерева данных — это набор узлов, которые начинаются с корневого или родительского узла, у которого затем есть дочерние элементы, а у некоторых из этих дочерних элементов есть дочерние элементы. Это семейное созвездие можно увидеть во вложенном объекте или в DOM. Узлы, не имеющие потомков, часто называются «листьями», продолжающими ссылку на дерево, или «внешними узлами». Узлы, имеющие одних и тех же родителей, называются «братьями».
Деревья представляют собой нелинейную структуру данных, в отличие от линейных структур данных, таких как стеки, очереди и связанные списки. Деревья могут быть пустыми без узлов или могут иметь несколько «поддеревьев». В этой статье мы сосредоточимся на неупорядоченных деревьях и рассмотрим, как мы можем перемещаться по дереву. В каждом узле хранится какая-то информация, например число или элемент DOM.
Допустим, у нас есть объект, который имеет «древовидную» структуру, и мы хотим пройтись и выяснить, какие узлы имеют нечетное значение. В этом дереве каждый узел будет иметь ключ «значение» с каким-то числовым значением и ключ «дочерние элементы», который будет либо пустым массивом (листом), либо будет иметь один или несколько «дочерних» объектов.
Несмотря на то, что эта структура может не выглядеть как дерево, вы уже можете начать видеть неотъемлемую структуру объектов, имеющих дочерние значения.
Теперь давайте поговорим о том, как мы можем пройти по дереву, используя JavaScript и рекурсию. Цель состоит в том, чтобы вывести массив всех нечетных узлов дерева, а значит, у нас будет массив объектов.
Во-первых, давайте настроим нашу функцию. Мы знаем, что нам нужно будет вернуть массив, поэтому давайте объявим эту переменную, а также добавим возврат в конце функции:
Теперь давайте сначала сосредоточимся на решении проблемы для узла «верхнего уровня». Какой наименьший случай мы можем решить? Во-первых, мы можем проверить, является ли узел нечетным, и если да, то отправить его в наш массив результатов:
Теперь, когда у нас есть «базовый случай», давайте подумаем об одном узле «второго уровня». Мы знаем, что нам нужно будет перебрать все элементы в дочернем массиве, поэтому давайте настроим цикл for:
Здорово! Нам осталось добавить еще одну деталь. Если мы просто рекурсивно запустим нашу функцию над node.children[i] и не сохраним значение, мы будем терять его каждый раз, когда будем переходить к следующему дочернему элементу. Нам нужно будет взять наш массив результатов и объединить его с каждым результатом, чтобы мы зафиксировали все результаты. Теперь, когда мы решили для корневого узла и следующего дочернего узла, мы все настроены на обход всех узлов дерева. Наконец, мы вызовем функцию и передадим наш объект дерева:
Теперь у нас есть массив со всеми нечетными узлами! Рекурсия часто является хорошим способом обхода неупорядоченного дерева структуры данных. Удачного обхода дерева!
