Php рекурсивное построение деревьев

Содержание

Creating a recursive category tree function
Примеры использования рекурсивной функции в PHP
Простой пример рекурсии в PHP
Факториал
Пример функции для защиты от XSS
Класс дерева категорий
Рекурсия на PHP — алгоритм, применение
Задача №1
Задача №2
Задача №3

Creating a recursive category tree function

I’m trying to build a recursive tree script in PHP, but I’m stuck. Here’s what I have so far. I’m stuck on what to do between the else: and endif; in the foreach. (And I’m using that syntax just for easier reading here.) Any suggestions?

‘; if ($value[‘parent’] == NULL): $output .= $value[‘name’]; else: endif; endif; $output .= »; endforeach; $output .= ‘

EDIT 1 I was able to get this working, although I have a database call in a foreach loop, which probably isn’t the best idea:

‘; if ($value[‘parent’] == NULL): $output .= $value[‘name’]; $subcategories = ci()->db->get_where(‘categories’, array(‘parent’ => $value[‘id’])); if ($subcategories->num_rows() > 0): $output .= $this->makeTree($value[‘id’], $subcategories->result_array()); endif; else: $output .= $value[‘name’]; $output .= »; endif; endif; endforeach; $output .= ‘

‘; if ($value[‘parent’] == NULL): $output .= $value[‘name’]; $matches = array(); foreach($array as $subkey => $subvalue): if ($subvalue[‘parent’] == $value[‘id’]): $matches[$subkey] = $subvalue; endif; endforeach; $output .= $this->makeTree($value[‘id’], $matches); else: $output .= $value[‘name’]; $output .= »; endif; endif; endforeach; $output .= ‘

Источник

Примеры использования рекурсивной функции в PHP

Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Другими словами, рекурсия — это вызов функции внутри самой себя.

Простой пример рекурсии в PHP

Ниже показан примитивный пример использования рекурсии. По сути, ничего полезного данный код не делает. Более того, такой скрипт (бесконечный) переполнит стэк и аварийно завершит свою работу. Мы получим ошибку: Fatal error: Uncaught Error: Maximum function nesting level of ‘256’ reached, aborting! .

function recursion() < recursion(); >recursion();

Факториал

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

function factorial($n) < if ($n echo factorial(5); // 120

Факториал числа так же можно вычислить, применив цикл, полностью заменяющий рекурсию:

function factorial($n) < $result = 1; for ($i = 1; $i return $result; > echo factorial(5); // 120

Пример функции для защиты от XSS

Практически все данные (за редким исключением) из форм необходимо, во избежания XSS, пропускать через функцию htmlspecialchars() . Наша задача написать такую функцию, которая будет принимать массив (включая вложенные массивы) всех входящих данных и "прогонять" эти данные через встроенную функцию php htmlspecialchars() . И как раз здесь мы будем использовать рекурсию.

 $value) < // Перебираем исходный массив $result[$key] = xss($value); // Рекурсивно вызываем функцию xss >return $result; // Возвращаемый "защищённый" массив > return htmlspecialchars($data, ENT_QUOTES); // Если это не массив, то вызываем htmlspecialchars() > // Предположим, что в строке запроса у нас такая строка: // /?name=John&age=<>45 $data = xss($_REQUEST); // Вызываем функцию, передав туда в качестве аргумента весь REQUEST // Распечатаем результат var_dump($data);

Класс дерева категорий

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

CREATE TABLE IF NOT EXISTS category ( `id` INT NOT NULL AUTO_INCREMENT, `name` VARCHAR(100) NOT NULL, `parent_id` VARCHAR(40) NOT NULL, PRIMARY KEY ( id ) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci; INSERT INTO category (`id`, `name`, `parent_id`) VALUES (1, 'Компьютеры и периферия', 0), (2, 'Комплектующие для ПК', 0), (3, 'Смартфоны и смарт-часы', 0), (4, 'Телевизоры и медиа', 0), (5, 'Игры и приставки', 0), (6, 'Аудиотехника', 0), (7, 'Фото-видеоаппаратура', 0), (8, 'Офисная техника и мебель', 0), (9, 'Компьютерные системы', 1), (10, 'Периферия', 1), (11, 'Программное обеспечение и аксессуары', 1), (12, 'Системные блоки', 9), (13, 'Моноблоки', 9), (14, 'Неттопы и компьютеры-флешки', 9), (15, 'Платформы', 9), (16, 'Игровые компьютеры', 12), (17, 'Компьютеры для офиса', 12), (18, 'Компьютеры для бизнеса', 12), (19, 'Сенсорные моноблоки', 13), (20, 'Моноблоки с IPS экраном', 13), (21, 'Моноблоки с VA экраном', 13), (22, 'Моноблоки с TN экраном', 13), (23, 'Основные комплектующие', 2), (24, 'Хранение данных и охлаждение', 2);

require 'Category.php'; $category = new Category(); $data = $category->getData(); $tree = $category->createTree($data); $category->renderTemplate($tree);

Основы хранения в БД древовидных структур можно почитать здесь.

Источник

Рекурсия на PHP — алгоритм, применение

К написанию статьи сподвигли часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах, но в последствии решил реализовать на PHP, дабы снять зависимость от СУБД. На простом примере я покажу как можно пройти от корня иерархии до каждого конечного элемента и обратно, информация скорее для новичков.

Итак, тестовая иерархия, с которой нам предстоит работать:

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

CREATE TABLE [dbo].[Test]( [uid] [int] IDENTITY(1,1) NOT NULL, -- уникальное поле, автоинкрементное [pid] [int] NULL, -- это поле указывает на элемент уровнем выше, содержит uid родителя [name] [varchar](255) NULL, [access] [varchar](50) NULL, -- права доступа ) ON [PRIMARY]

Описание полей есть в комментариях, чуть подробнее о поле access:

По умолчанию в моей системе для каждого нового документа проставляется inherit, то есть наследование от родителя. Для нашего эксперимента для некоторых эелементов пропишем доменные группы. В группе Domain Users моя учётная запись имеется, а вот в AD Group Secret меня нет.

Что ещё мы имеем. Массив, содержащий список моих доменных групп. Достаётся он достаточно просто, на IIS включена аутентификация Windows, всё работает прозрачно, в PHP логин зашедшего находится в переменной $_SERVER[«AUTH_USER»], далее LDAP запросом получаем список групп.

Теперь предлагаю получить необходимые данные и перейти непосредственно к делу:

$stmt = $PDO->query("SELECT * FROM Test"); $table = $stmt->fetchAll(); //Получим таблицу из БД $groups = LDAP::getGroups('$login'); //Получим группы ActiveDirectory

Задача №1

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

Задача №2

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

Задача №3

Необходимо скрыть от пользователей ресурсы, к которым у них нет доступа, но самое главное, при наличии прав хотя бы на один документ где то в глубине закрытой для него ветки, делать видимыми элементы ведущие к этому документу (иначе как пользователь до него доберётся?)

Вот собственно базовая функция:

$array = array(); //выходной массив function recursive($data, $pid = 0, $level = 0) < global $array; foreach ($data as $row) < //перебираем строки if ($row['pid'] == $pid) < //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта //Собираем строку в ассоциативный массив $_row['uid'] = $row['uid']; $_row['pid'] = $row['pid']; $_row['name'] = $_row['name'] = str_pad('', $level*3, '.').$row['name']; //Функцией str_pad добавляем точки $_row['level'] = $level; //Добавляем уровень $array[] = $_row; //Прибавляем каждую строку к выходному массиву //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом) recursive($data, $row['uid'], $level + 1); >> > recursive($table); //Запускаем

Описание по большей части привёл в комментариях, но если говорить просто — после того как цикл foreach проходит строку и делает что то с данными(в нашем случае просто копирует данные в другой массив, добавляя поле level и точки к имени), он запускает эту же функцию, передав ей uid строки, и поскольку в условии if мы сравниваем его с pid, то следующий запуск однозначно захватит дочерние элементы. Цикл foreach перебирает все строки у которых uid родителя совпадает с переданным значением, поэтому перезапуская саму себя, функция отработает на каждом элементе каждого уровня. Для наглядности, мы так же передаём level увеличивая его на единицу. В итоге мы увидим какой документ какой уровень вложенности имеет.

Выводим массив $array в браузер:

А теперь немного усложним нашу функцию:

$array = array(); //выходной массив $array_idx_lvl = array(); //индекс по полю level function recursive($data, $pid = 0, $level = 0, $path = "", $access_parent = "inherit") < global $array; global $array_idx_lvl; //Индекс по level global $groups; //доменные группы //перебираем строки foreach ($data as $row) < //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта if ($row['pid'] == $pid) < //Собираем строку в ассоциативный массив $_row['uid'] = $row['uid']; $_row['pid'] = $row['pid']; $_row['name'] = str_pad('', $level*3, '.').$row['name']; $_row['level'] = $level; //Добавляем уровень $_row['path'] = $path."/".$row['name']; //Добавляем имя к пути $_row['view'] = ""; //Разруливаем доступы if($row['access'] == 'inherit') < $_row['access'] = $access_parent; //Если стоит наследование, делаем как у родителя >else < $_row['access'] = (in_array($row['access'], $groups)) ? 'allow' : 'deny'; >$array[$row['uid']] = $_row; //Результирующий массив индексируемый по uid //Для быстрой выборки по level, формируем индекс $array_idx_lvl[$level][$row['uid']] = $row['uid']; //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом) recursive($data, $row['uid'], $level + 1, $_row['path'], $_row['access']); > > > recursive($table); //Запускаем

1. Добавлено поле path — для формирования пути, добавляем к значению "/" и имя строки, затем полученное значение передаём в функцию, где история повторяется и на выходе получается путь от корня до элемента.

2. Результирующий массив теперь формируется не по порядку, начиная с нуля а с привязкой к uid — $array[$row['uid']] = $_row;. В данном случае это ни как не влияет на работу скрипта, но возможность обращаться к строке по индексу, а не перебором в цикле потребуется нам в дальнейшем, когда будем разбирать проход по дереву в обратную сторону.

3. Добавлен индекс $array_idx_lvl = array();. Этот индекс нам так же потребуется позже, смысл таков — результирующий набор складывается не в одну кучу, а с разбивкой на массивы индексируемые по level.

4. Поле Access. Когда функция запускает саму себя, вместе с остальными параметрами она передаёт свою настройку прав $_row['access'] дочерям, а далее происходит следующее, проверяются права — если выставлено наследование (inherit), то применяются права родителя, если нет — через in_array проверяем, есть ли указанная в access доменная группа среди групп зашедшего пользователя. Если есть — добавляем в строку allow (разрешить), иначе deny (запрет).

Итоговый результат:

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

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

//Функция прохода вверх по дереву на один уроверь от заданного uid, устанавливает //свойство видимости себе и родителю в зависимости от доступа или заданной ранее видимости. function backRecursive($uid, $view = null, $ident = 0) < global $array; //Если поднялись не больше чем на один уровень if($ident backRecursive($array[$uid]['pid'], $array[$uid]['view'], $ident+1); > >

Что делает эта функция — принимает в качестве параметра uid строки, с которой нужно начать действовать, обращается к этой строке и проверяет видимость. Если в поле view не show(т.е. показывать), а что то другое, проверяет что находится в безопасности, и если там стоит allow(доступ открыт), делает элемент видимым, в противном случае скрытым(hide), затем запускает себя же, передавая свой pid и настройку видимости, а так же переменную $ident увеличенную на 1, тем самым блокируя последующие самозапуски. При втором проходе, по переданному pid находится родительский элемент, выполняется та же проверка, за исключением одного, если от дочернего в переменной $view передано 'show', то не смотря ни на что, текущему элементу так же присвоится show, то есть видимый.

На мой взгляд, работа с ограничителем — самый оптимальный вариант, ибо представьте ситуацию, на 10 уровне у нас 100 документов, для полного обхода всего дерева, нам нужно запускать эту функцию на каждом элементе, т.к. если на последнем уровне мы запустим функцию 100 раз, то выполняя самозапуски, перебор 100 раз дойдёт до корня. Если умножить на 10 уровней — уже получится 1000 циклов, что не есть хорошо, поэтому подъём нужно осуществлять равномерно, уровень за уровнем.

Запускает эту функцию следующий код:

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

Перед запуском, я намеренно прописал разрешающую группу для пункта «Отчет для налоговой», чтобы наглядно показать что код отрабатывает корректно. Несмотря на то, что доступ к разделу «Бухгалтерская отчетность» закрыт, он видимый.

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

Источник