Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Определения PHP: Деревья

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

php-package # директория
├── Makefile # файл
├── README.md # файл
├── tests # директория
│   └── halfTest.php # файл
├── phpunit.xml # файл
└── vendor # директория
    └── squizlabs # директория
        └── php_codesniffer # директория

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

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

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

Tree Terminology

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

Реализация

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

<?php

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

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

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

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

  1. Данных, которые хранятся внутри дерева
  2. Структуры дерева, которая отвечает за связи между данными
<?php

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

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

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

<?php

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

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

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

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

<?php

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

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


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

  1. Фракталы

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Для полного доступа к курсу нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнения
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 120 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы

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

Иконка программы PHP-разработчик
Профессия
Разработка веб-приложений на Laravel
22 сентября 8 месяцев

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»