Все статьи | Блог студента

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

Эта статья написана нашим студентом. Мнение пользователей иногда может не совпадать с точкой зрения Хекслета
JS. Путешествие по деревьям главное изображение

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

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

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

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

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

const tree = {
  roots: {
    trunk: {
      branch: 'a leaf',
      hollow: 'a squirrel',
    },
  },
  country: {
    city: 'a citizen',
  },
  'Internet': {
    'Hexlet.io': {
      'Frontend JS': {
        'Trees': 'this lesson'
      },
      'Blog': 'this post',
    },
    },
};

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

// Вот так выглядит наша функция:

const findPath = (tree) => {
  const iter = (obj, path) => {
    const keys = _.keys(obj);
    return keys.flatMap((key) => {
      if (_.isObject(obj[key])) {
        const updatedPath = `${path} —> ${key}`;
        return iter(obj[key], updatedPath);
      }
      const finalPath = `${path.slice(4)} —> ${key}`
      return `Follow the path [ ${finalPath} ] to find ${obj[key]}`;
    });
  };
  return iter(tree, '').join('\n');
};

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

const findPath = (tree) => {
  const iter = (obj, path) => {
    // здесь будет внутренняя логика
  };
  return iter(tree, '');
};

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

const keys = _.keys(obj);
return keys.flatMap((key) => {
  // Здесь будет внутренняя логика
});

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

return keys.flatMap((key) => {
  if (_.isObject(obj[key])) {
    const updatedPath = `${path} —> ${key}`;
    return iter(obj[key], updatedPath);
  }
  const finalPath = `${path.slice(4)} —> ${key}`

  // поскольку мы начинали с пустой строки,
  // в начале образовалась лишняя стрелка,
  // которую мы обрежем методом .slice

  return `Follow the path [ ${finalPath} ] to find ${obj[key]}`;

  // последнее значение и есть цель маршрута

});

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

Follow the path [ roots —> 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 oakForest = ['grove', [
  ['trunk', [
    ['branch',
      ['squirrel']
    ],
    ['branch'],
  ]],
  ['trunk', [
    ['branch'],
    ['branch', [
      ['hollow', [
        ['squirrel'],
      ]]
    ]],
  ]],
  ['trunk', [
    ['squirrel'],
    ['branch', [
      ['hollow'],
    ]],
  ]],
]];

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

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

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

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

const findSquirrels = (tree) => {
  const [root, branches] = tree;
  if (!branches) {
    return [];
  }
  // дальше — больше
};

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

const flatBranches = _.flatten(branches);

// Снова воспользуемся
// библиотекой Lodash
// и выпрямим массив

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

if (flatBranches.includes('squirrel')) {
  console.log(`Look at the ${root}! There's a squirrel!`);
  return root;
}
return branches.flatMap((branch) => findSquirrels(branch));

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

// Вывод в консоли:

Look at the branch! There's a squirrel!
Look at the hollow! There's a squirrel!
Look at the trunk! There's a squirrel!

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

const squirrelHabitats = findSquirrels(oakForest);

console.log(`I found ${squirrelHabitats.length} squirrels in these locations: ${squirrelHabitats.join(', ')}!`);

// Вот так выглядит финальный вывод:

I found 3 squirrels in these locations: branch, hollow, trunk!

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

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

Заключение

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

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

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

Аватар пользователя Андрей Агафонов
Андрей Агафонов 01 октября 2020
Рекомендуемые программы

С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.

Иконка программы Фронтенд-разработчик
Профессия
Разработка фронтенд-компонентов веб-приложений
1 декабря 8 месяцев
Иконка программы Python-разработчик
Профессия
Разработка веб-приложений на Django
1 декабря 8 месяцев
Иконка программы PHP-разработчик
Профессия
Разработка веб-приложений на Laravel
1 декабря 8 месяцев
Иконка программы Node.js-разработчик
Профессия
Разработка бэкенд-компонентов веб-приложений
1 декабря 8 месяцев
Иконка программы Верстальщик
Профессия
Вёрстка с использованием последних стандартов CSS
в любое время 5 месяцев
Иконка программы Java-разработчик
Профессия
Разработка приложений на языке Java
1 декабря 10 месяцев
Иконка программы Разработчик на Ruby on Rails
Профессия
Новый
Создает веб-приложения со скоростью света
1 декабря 5 месяцев