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

Tree
Terminology

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

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

Определение

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

[[1, 4], 2, [3, 8]];
//     *
//    /|\
//   * 2 *
//  /|   |\
// 1 4   3 8

[3, 2, [3, 8], [[8], 3]];
[1, null, [[3]], [5, 'string', [undefined, [3], { key: 'value' }]]];

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

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

[[3], [4], [[10], [[3], [2], [8], [[2], [[3], [4]]]]]];

Такой вариант многословнее, но позволяет хранить данные (произвольные) в любом узле, даже не листовом. Теперь, надеюсь, вам понятен принцип организации, и вы можете самостоятельно попрактиковаться в придумывании способов упаковки деревьев в массив. Кстати, интересная деталь. Исходный код высокоуровневых языков тоже имеет рекурсивную структуру. Посмотрите на код:

f1(3 * f2(f3() + 5));

Аргументы функции — выражения, а значит могут быть вызовами функций, что порождает рекурсию. Если код выше переписать в стиле lisp языков, то получится самое настоящее дерево, состоящее из списков:

(f1 (* 3 (f2 (+ 5 (f3))))

Соглашение здесь такое: первым элементом списка является функция (любые операции рассматриваются как функции), а всё остальное — её аргументы.

Ещё один способ определения основан на ассоциативных массивах, а конкретно в javascript — на объектах:

{
  value: 5,
  children: [
    { value: 10 },
    { value: 100 },
    { value: 'nested', children: [/* ... */] }
  ]
}

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

По ходу курса мы будем работать с одной и той же структурой, создавая поверх неё различные вспомогательные функции для поиска и модификации содержимого. Ниже показан код (dsl), который создаёт необходимый объект-дерево:

const tree = mkdir('etc', [
  mkdir('consul', [
    mkfile('config.json', { size: 1200 }),
  ]),
], { key: 'value' });

В результате выполнения кода получается следующий результат:

{
  name: 'etc',
  type: 'directory',
  meta: {
    key: 'value',
  },
  children: [
    {
      name: 'consul',
      type: 'directory',
      meta: {},
      children: [
        {
          name: 'config.json',
          type: 'file',
          meta: {
            size: 1200
          }
        }
      ],
    },
  ],
};

Представление директории:

{
  name: /* ... */,
  type: 'directory',
  meta: {},
  children: [/* ... */],
}

Представление файла:

{
  name: /* ... */,
  type: 'file',
  meta: {},
}

Некоторые утверждения относительно дерева выше:

  • Файлы — листовые узлы;
  • Директории — внутренние. Могут содержать как файлы, так и директории внутри свойства children;
  • meta — объект с произвольными данными, например, размером, датой создания и так далее;
  • Директорию от файла отличает, в первую очередь, тип, заданный соответствующим свойством.

Про последнее скажу пару слов. То самое понимание ООП, о котором так много говорят, как раз заключается в том, что код рассматривается с точки зрения типов, и вы их можете увидеть. Важно выделять их явно, а не анализировать по косвенным признакам — например, определение того, что за нода перед нами (какой у неё тип!), нужно делать через проверку type, а не через проверку наличия свойства children.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →