2. Определения

Файловая структура – пример дерева, с которым знакомы все, кто пользуется компьютером. Она состоит из директорий и разного вида файлов.

nodejs-package # корневая директория
├── Makefile # файл
├── README.md # файл
├── __tests__ # директория
│   └── half.test.js # файл
├── babel.config.js # файл
└── node_modules # директория
    └── @babel # директория
        └── cli # директория
            └── LICENSE # файл

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

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

Дерево состоит из узлов (вершин или нод, так как по-английски узел — это node) и рёбер между ними. Рёбра в реальности не существуют, они нужны лишь для того, чтобы визуализировать связь и, по необходимости, описать её. Узлы делятся на два типа: внутренние (те, у которых есть потомки) и листовые узлы (те, у которых нет потомков). В случае файловой системы листовые узлы представлены файлами, а внутренние — директориями.

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

Реализация

Количество способов, которыми можно описать деревья, бесконечно. Самый примитивный вариант — это вложенные массивы:

[['index.html', 'main.js'], 'index.js', ['favicon.ico', 'app.css']];
//                    * корень – сам массив
//         /          |         \
//       *         index.js       * 
//  /         |               |        \
// index.html main.js   favicon.ico app.css

// Ещё пара примеров деревьев с произвольными данными:
[]; // пустое дерево
[3, 2, [3, 8], [[8], 3]];
[1, null, [[3]], [5, 'string', [undefined, [3], { key: 'value' }]]];

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

Любое дерево состоит из двух больших частей:

Данных, которые хранятся внутри дерева
Структуры дерева, которая отвечает за связи между данными

[['index.html', 'main.js'], 'index.js', ['favicon.ico', 'app.css']];

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

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

['app', [ // Корень
  ['dist', [ // Внутренний узел
    ['index.html'], // Лист
    ['main.js'] // Лист
  ]],
  ['index.js'], // Лист
  ['assets', [ // Внутренний узел
    ['favicon.ico'], // Лист
    ['app.css'], // Лист
  ]],
]];

//                   app
//         /          |         \
//       dist      index.js   assets
//  /         |               |        \
// index.html main.js   favicon.ico app.css

Такой вариант многословнее, но позволяет хранить данные в любом узле, даже не листовом. Причём это не обязательно должна быть строка как в примере выше. Изменение данных на объекты позволит добавлять туда все что угодно.

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

// Обратите внимание на разделение структуры и данных
// Здесь оно значительно более очевидное
{
  value: 5,
  children: [
    { value: 10 },
    { value: 100 },
    { value: 'nested', children: [/* ... */] }
  ]
}

По большому счёту, что массив, что объект сами по себе всегда могут рассматриваться как деревья. Это справедливо для любой рекурсивной структуры данных, то есть для такой структуры, элементами которой может быть сама структура. В любом массиве может содержаться массив, как и в любом объекте может содержаться объект.

Дополнительные материалы

Тесты

Вопрос 1

Что из перечисленного является листовым узлом?

(нужно выбрать все корректные ответы)

Роутер

Ребёнок (с точки зрения генеалогии)

Каталог в файловой системе

Компьютер пользователя в сети интернет

Вопрос 2

Рассмотрите организацию как классическую иерархию должностей. Выберите листовой узел:

1. Кассир

2. Бухгалтер

3. Генеральный директор

4. Главный бухгалтер

Вопрос 3

Сколько родительских узлов может существовать у потомка?

Ни одного

Любое количество

Больше одного

Вопрос 4

Сколько родительских узлов может существовать у корневого узла?

Ни одного

Любое количество

Больше одного

Вопрос 5

Какова глубина указанного дерева?

  *
 / \
*   *

Вопрос 6

Проанализируйте дерево, построенное на основе массивов:

const tree = [[1, 4], 2, [3, 8]];

Выберите верные утверждения

(нужно выбрать все корректные ответы)

Корневым узлом является массив [[1, 4], 2, [3, 8]]

Глубина внутреннего узла (листа) 2 равна двум

Глубина узла 3 равна двум

Узлы 1 и 4 являются братскими

Узлы 4 и 8 являются братскими

Корневым узлом является массив [3, 8]

Вопрос 7

Проанализируйте дерево, построенное на основе массивов:

const tree = [[1, 4], 2, [3, 8]];

Выберите верные утверждения

(нужно выбрать все корректные ответы)

Узлы 2 (листовой узел) и [3, 8] находятся на одной глубине

Узел 8 является потомком узла [3, 8]

Узлы 3 и 8 не являются братскими

Узлы [1, 4] и [3, 8] не находятся на одной глубине

Узел 8 является потомком узла [1, 4]

Вопрос 8

Проанализируйте дерево, построенное на основе массивов:

const tree = [[1, 4], 2, [3, 8]];

Выберите верные утверждения

(нужно выбрать все корректные ответы)

Узлы 1 и 4 являются прямыми потомками узла [1, 4]

Узел [3, 8] является прямым потомком корневого узла

Узел [1, 4] не является прямым потомком корневого узла

Узел 4 является прямым потомком корневого узла

Лист 2 является прямым потомком корневого узла

Узлы 3 и 8 являются потомками узла [1, 4]

Упражнение

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

[
  3, // лист
  [5, 3], // узел
  [[2]] // узел
]

Больше примеров в тестах.

removeFirstLevel.js

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

Примеры

import removeFirstLevel from '../removeFirstLevel.js';

// Второй уровень тут: 5, 3, 4
const tree1 = [[5], 1, [3, 4]];
removeFirstLevel(tree1); // [5, 3, 4]

const tree2 = [1, 2, [3, 5], [[4, 3], 2]];
removeFirstLevel(tree2);
// [3, 5, [4, 3], 2]

Подсказки

Array.prototype.flat() - возвращает новый массив, в котором все элементы вложенных подмассивов были рекурсивно "подняты" на указанный уровень.
Array.isArray() - проверяет, является ли элемент массивом.

Хештеги

#courses #hexlet #hexlet_courses #hexlet_js_trees #js_trees #js_trees_lessons