Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 Теги: php, алгоритмы, программирование на php, древо, древовидная иерархия, рекурсивный метод, рекурсия в php

2 Однажды я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, какклассические алгоритмы.

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

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

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

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

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

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

9 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; }Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом:

10 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 уровня. Замечу, что приведённый метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.

11 $tree = new Tree(); $tree->buildTree(0, 0);А вот как будет<a>выглядеть наше дерево</a>в итоге:

12 <?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); ?>Данный метод применим при построении меню на сайте, каталогов продукции и т. п. У него, разумеется, есть недостатки. При построении достаточно большого каталога метод будет работать довольно долго. Но выигрыш тут в том, чтометод можно модифицироватьи ограничить не только уровнем входа, но и уровнем погружения. Таким образом, можно достраивать дерево постепенно при запросе пользователей, что решит данную проблему.

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

14 На этом всё! Безошибочного вам кода!