Применение простых алгоритмов в PHP: рекурсивный метод | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «ELK»
-16%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Применение простых алгоритмов в PHP: рекурсивный метод

PHP_Deep_8.11-5020-f24b5f.png

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

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

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

1-20219-8ce915.jpg

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

Алгоритм (паттерн, если так хотите) будет примерно следующим: 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--;
            }
        }
    }

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

    $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!

Автор
1 комментарий
1

Доходчиво. Автор крут 👍 С нетерпением ждём nested sets

Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!