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

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

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

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

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

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

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

?>

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

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

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