Всем привет! В этой статье я просто хочу показать вам, как вы можете перемещаться по древовидной структуре в TypeScript тремя различными способами.
Часто на собеседовании можно встретить вопросы о древовидной структуре, и, несмотря на свою простоту, они могут ввести в ступор, если вы никогда с ней не сталкивались.
Прежде всего, давайте посмотрим, с чем мы будем иметь дело.
interface Tree<T> {
value: T,
children?: Tree<T>[]
}
const tree: Tree<number> = {
value: 0,
children: [
{
value: 1,
children: [
{
value:2,
children: [
{
value: 3
}
]
}
]
},
{
value: 4,
children: [
{
value: 5
},
{
value: 6
},
{
value: 7,
children: [
{
value: 8
}
]
}
]
}
]
}
Итак, вот что мы имеем в начале. На собеседовании вам могут задавать разные вопросы, но сегодня мы узнаем, как собрать все значения в один массив.
Результат должен быть таким:
traverseTree(tree); // [0,1,2,3,4,5,6,7,8]
- Рекурсивный обход
Для меня рекурсивный подход является самым простым для понимания. Сейчас я вам докажу, что ничего сложного в этом нет.
Прежде всего, создайте функцию и введите ее входные и выходные параметры.
const traversalTree = <T>(tree: Tree<T>): T[] => {
...
///
}
Второй шаг, который вы должны сделать, это понять — каким должен быть ваш конечный результат.
В нашем случае мы должны вернуть массив — вот что нам нужно сделать! Нам нужно инициализировать пустой массив, ввести его и вернуться.
const traversalTree = <T>(tree: Tree<T>): T[] => {
let arr: T[] = [];
///
...
return arr;
}
Мы знаем, что наша структура данных, не имеет значения, на какой глубине вложенности мы находимся, мы имеем свою ценность. Итак, мы должны поместить значение нашего дерева в массив.
const traversalTree = <T>(tree: Tree<T>): T[] => {
let arr: T[] = [];
arr.push(value);
///
...
return arr;
}
Следующий шаг — условие. Нам нужно проверить наше дерево на наличие дочерних элементов. Он должен существовать и иметь длину (должны быть вложенные значения)
const traversalTree = <T>(tree: Tree<T>): T[] => {
let arr: T[] = [];
arr.push(value);
if (tree.children && tree.children.length) {
///
...
}
return arr;
}
И последний шаг заставляет нас использовать наш инициализированный массив. Мы должны пройтись по нашему дереву потомки и присвоить нашему массиву текущее значение массива + рекурсивное значение, используя присваивание destructuring.
const traversalTree = <T>(tree: Tree<T>): T[] => {
let arr: T[] = [];
arr.push(tree.value);
if(tree.children && tree.children.length) {
for(const child of tree.children) {
arr = [...arr, ...traverseTree(child)]
}
}
return arr;
}
const collectData = traverseTree(tree); // [0,1,2,3,4,5,6,7,8]
И это все. Наш код работает отлично! Но, если вам не нравятся чистые циклы или что-то еще, вы можете использовать метод reduce.
const traversalTree = <T>(tree: Tree<T>): T[] => {
let arr: T[] = [];
arr.push(tree.value);
if(tree.children && tree.children.length) {
arr = tree.children.reduce((acc, item) => [...acc, ...traverseTree(item)], arr);
}
return arr;
}
const collectData = traverseTree(tree); // [0,1,2,3,4,5,6,7,8]
2. Обход очереди
Этот метод довольно сложен для понимания, но если вы понимаете, как его использовать и какие мощные возможности может дать очередьструктура данных, вы точно удивите своего интервьюера😉
Поговорим немного об очереди.
Очередь — это примитивная структура данных, позволяющая нам делать только 2 вещи. Ставить данные в очередь и удалять данные из очереди. Не так, как мы привыкли например в массивах, а только одним визуальным образом. Вы можете видеть, как на этой картинке:
И это то, что нам нужно. Теперь наш первый шаг — добавить наше дерево в массив с именем queue.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const result:T[] = [];
const queue:Tree<T>[] = [tree];
///
...
return result
}
И теперь наше базовое условие зацикливания будет зависеть от массива очередей. Он не должен быть пустым.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const result:T[] = [];
const queue:Tree<T>[] = [tree];
while(queue.length > 0) {
///
...
}
return result
}
Следующая часть — просто переместить узел из нашей очереди и сохранить его в переменной. Напоминаю, что метод shiftудаляет из массива первый элемент и возвращает его. Если массив пуст, возвращается undefined и массив не изменяется.
И если наше значение узла существует, мы просто помещаем его в массив результатов.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const result:T[] = [];
const queue:Tree<T>[] = [tree];
while(queue.length > 0) {
const node = queue.shift();
if(node?.value) {
result.push(node.value)
}
///
...
}
return result
}
Наш последний шаг — проверить значения дочерних узлов. Если у него есть длина, мы продолжим. Ключевая логика здесь заключается в изменении нашей очереди путем вставки новых элементов в начало массива. Метод unshift позволяет нам делать это очень хорошо.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const queue:Tree<T>[] = [tree];
const result:T[] = [];
while(queue.length > 0) {
const node = queue.shift();
if(node?.value) {
result.push(node.value)
}
if(node?.children?.length) {
queue.unshift(...node.children)
}
}
return result
}
Когда мы используем unshift с назначением деструктурирования дочерних узлов, мы просто помещаем дочерние узлы в начало нашего массива. Это то, что позволит нашему циклу не заканчиваться на первой итерации.
Готово! Наш метод обхода очереди работает отлично!
const traversalTree = <T>(tree: Tree<T>): T[] => {
const queue:Tree<T>[] = [tree];
const result:T[] = [];
while(queue.length > 0) {
const node = queue.shift();
if(node?.value) {
result.push(node.value)
}
if(node?.children?.length) {
queue.unshift(...node.children)
}
}
return result
}
const collectData = traversalTree(tree); // [0,1,2,3,4,5,6,7,8]
3. Циклический обход
Этот подход не так уж сложно воспроизвести, но он требует от вас понимания того, как замыкание работает в JavaScript.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const result: T[] = [];
const treeArr:Tree<T>[] = [tree];
///
...
return result
}
Первый шаг здесь очень похож на то, что мы делали, когда мы зацикливались, используя очередь. Нам нужно определить массив, с которым мы будем работать.
Следующий шаг — это определение функции. Эта функция позволит нам использовать всю мощь замыканий в JS. В качестве параметра принимает наш массив деревьев.
const traversalTree= <T>(tree: Tree<T>): T[] => {
const result: T[] = [];
const treeArr:Tree<T>[] = [tree];
function treeForeach(tree: Tree<T>[]) {
///
...
}
return result
}
И вот идет цикл. Работа цикла заключается в том, чтобы поместить каждое значение, с которым он сталкивается, в массив результатов, и, если у наших данных есть дочерние элементы, он должен снова вызвать нашу функцию treeForeach. Аргументами больше не будет исходный массив, а будет наш дочерний массив.
const traversalTree= <T>(tree: Tree<T>): T[] => {
const result: T[] = [];
const treeArr:Tree<T>[] = [tree];
function treeForeach(tree: Tree<T>[]) {
tree.forEach(data => {
result.push(data.value)
data.children && treeForeach(data.children)
})
}
return result
}
Наша функция выполнена! Последнее, что нам нужно сделать, это просто вызвать его внутри нашего метода traverseTree.
const traversalTree = <T>(tree: Tree<T>): T[] => {
const result: T[] = [];
const treeArr:Tree<T>[] = [tree];
function treeForeach(tree: Tree<T>[]) {
tree.forEach(data => {
result.push(data.value)
data.children && treeForeach(data.children)
})
}
treeForeach(treeArr)
return result
}
const collectData = traversalTree(tree);// [0,1,2,3,4,5,6,7,8]
Готово! Наш метод циклического обхода работает отлично!
Вот и все. Спасибо за прочтение. Я надеюсь, вы понимаете, как это работает, когда вы столкнетесь с подобным вопросом в интервью, это не вызовет у вас никаких проблем!
