Как построить дерево на PHP? | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Backend-разработчик на PHP Алгоритмы и структуры данных Team Lead Архитектура и шаблоны проектирования Разработчик IoT C# Developer. Professional HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Symfony Framework Unity Game Developer. Basic JavaScript Developer. Professional Android Developer. Basic JavaScript Developer. Basic Java Developer. Professional Highload Architect Reverse-Engineering. Professional Java Developer. Basic Web-разработчик на Python Framework Laravel Cloud Solution Architecture Vue.js разработчик Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool" PHP Developer. Basic
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK Administrator Linux. Professional Дизайн сетей ЦОД Разработчик IoT PostgreSQL Экспресс-курс "Версионирование и командная работа с помощью Git"
-30%
Microservice Architecture Highload Architect MS SQL Server Developer Разработчик программных роботов (RPA) на базе UiPath и PIX Разработчик голосовых ассистентов и чат-ботов Administrator Linux. Advanced Infrastructure as a code Супер-практикум по использованию и настройке GIT Administrator Linux.Basic Экспресс-курс «IaC Ansible» Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Основы Windows Server
Корпоративные курсы
Безопасность веб-приложений IT-Recruiter Дизайн сетей ЦОД Компьютерное зрение Разработчик IoT Вебинар CERTIPORT Machine Learning. Professional
-6%
NoSQL Пентест. Практика тестирования на проникновение Java QA Engineer. Базовый курс Руководитель поддержки пользователей в IT
-8%
SRE практики и инструменты Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Infrastructure as a code Супер-практикум по использованию и настройке GIT Промышленный ML на больших данных Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» BPMN: Моделирование бизнес-процессов Основы Windows Server
Специализации Курсы в разработке Подготовительные курсы Подписка
+7 499 938-92-02

Как построить дерево на PHP?

Однажды я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как классические алгоритмы. Ведь если присмотреться к их реализации, то это тоже своего рода паттерны. С институтской скамьи можно вспомнить, к примеру, nested sets, b-tree, сортировку «пузырьком». Реализация многих алгоритмов давно устоялась. А потому, я хотел бы посвятить несколько статей алгоритмам и их применении в PHP.

Начну я с самого простого — построения древовидной иерархии.

Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:

1-20219-3ac018.png

Необходимо представить этот массив в виде древовидного меню. Я не буду говорить о том, какими неправильными способами можно решить эту задачу =)

Единственно верный подход в данном случае — рекурсивный метод.

Алгоритм (паттерн, если так хотите) будет примерно следующим: 0. Создаем объект дерева и выбираем все элементы в таблице. 1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию. 2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе. 3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе — выходим в шаг-инициализатор. 4. Уменьшаем уровень погружения. Выходим из итерации.

Итак, метод сборки массива категорий будет выглядеть примерно вот так

   private function getCategoryArray() {
        $query = $this->db_connect->prepare("SELECT * FROM tree_table");
        $query->execute();
        $result = $query->fetchAll(PDO::FETCH_OBJ);

        $category_array = array();
        foreach ($result as $value) {
            $category_array[$value->id_parent][] = $value;
        }

        return $category_array;
    }

Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом:

    public function buildTree($parent_id, $tree_level) {
        if (isset($this->category[$parent_id])) { 
            foreach ($this->category[$parent_id] as $value) { 
                echo "
" . $value->id_tree_test . " : " . $value->title . "
";
                $tree_level++;
                $this->buildTree($value->id_tree_test, $tree_level); 
                $tree_level--;
            }
        }
    }

Теперь можем вызвать построение дерева, начиная с нулевого элемента и нулевого уровня. Замечу, что приведенный метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.

    $tree = new Tree();
    $tree->buildTree(0, 0); 

А вот как будет выглядеть наше дерево в итоге:

<?php

class Tree {

    private $db_connect = null;
    public  $category = array();
    public  $tree = array();

    public function __construct() {
#        $this->db_connect = new PDO("mysql:dbname=devenergru_drup1;host=localhost", "devenergru_drup1", "weduucixwa");
        $this->category = $this->getCategoryArray();
     }

    private function getCategoryArray() {
        $category_array = [
        0 => [
            [
                'id_tree_test' => 2,
                'id_parent' => 0,
                'title' => "Два"
            ]
        ],
        1 => [
            [
                'id_tree_test' => 4,
                'id_parent' => 1,
                'title' => "Четыре"
            ]

        ],
        2 => [
            [
                'id_tree_test' => 1,
                'id_parent' => 2,
                'title' => "Один"
            ],
            [
                'id_tree_test' => 5,
                'id_parent' => 2,
                'title' => "Пять"
            ]
        ],
        4 => [
            [
                'id_tree_test' => 3,
                'id_parent' => 4,
                'title' => "Три"
            ]
        ]
    ];

        return $category_array;
    }

    public function buildTree($parent_id, $level) {
        if (isset($this->category[$parent_id])) { 
            foreach ($this->category[$parent_id] as $value) { 
                echo "<div style=\"margin-left:" . ($level * 25) . "px;\">" . $value["id_tree_test"] . " : " . $value["title"] . "</div>";
                $level++;
                $this->buildTree($value["id_tree_test"], $level); 
                $level--;
            }
        }
    }

}

$tree = new Tree();
$tree->buildTree(0, 0); 

?>

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

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

За сим все! Безошибочного вам кода!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться