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

Содержание

Построение дерева иерархии с помощью PHP и MySQL
Примеры использования рекурсивной функции в PHP
Простой пример рекурсии в PHP
Факториал
Пример функции для защиты от XSS
Класс дерева категорий
shurinskiy / category_tree.php
Creating a recursive category tree function

Построение дерева иерархии с помощью PHP и MySQL

Рассмотрим пример построения дерева иерархии (в развернутом виде) на основе информации из базы данных с помощью PHP и MySQL. Ключ к решению данной задачи — использование рекурсивной функции. Иерархия разделов будет храниться в таблице базы данных MySQL.

Ниже на скриншоте показана данная таблица (catalogue):

id — первичный ключ таблицы
pid — id родительского раздела

Далее напишем следующий PHP-скрипт:

1. Файл dbopen.php (открывает соединение с MySQL)

 $hostName = ""; $userName = "yura"; $password = "yura"; $databaseName = "tree"; if (!($link=mysql_connect($hostName,$userName,$password))) printf("Ошибка при соединении с MySQL !\n"); exit(); > if (!mysql_select_db($databaseName, $link)) printf("Ошибка базы данных !"); exit(); > ?>

 2. Файл index.php (основной скрипт)
 Всю работу выполняет рекурсивная функция ShowTree() . Ниже на скриншоте показан пример работы index.php :
 Пример проекта прилагается: phptree.zip 
Автор скрипта: Юрий Христофоров
 СодержаниеПроверка индексации страницыДругие инструменты Если нужно быстро проверить индексацию одной страницы, можно воспользоваться оператором
 СодержаниеСтатистика использования мобильных устройствИзменение поискового индекса GoogleИндексирование с ориентацией на мобильные устройстваПроверка оптимизации для
 В конце марта прошла конференция eTarget.Ecommerce, посвященная продвижению интернет-магазинов. Эксперты рассказали о том, как
 Если я правильно понял, то при каждой итерации идет обращение к базе данных. Как по мне, — не очень хорошая практика. Если вложеность дерева большая, то затратно… Как по мне, — лучне за раз выгребать все данные, а потом в пхп строить дерево по полученым данным или хранить деревя в файле. Если например надо построить меню сайта, можно закидывать все в іni or xml or json or yaml файл, а потом просто за раз выгребать и все.
 Мне больше нравится способ с конфигурационным файлом.. Я сейчас повсеместно использую Zend Framework. Там есть компонента Zend_Config_Writer . Тоесть когда приходится редактировать конфигурационный файл используем ее. А когда нужно использовать конфигурацию, берем просто Zend_Config, который выгребает готовое дерево с конфиг файла в виде массва. 
На сколько я знаю, доступ к файлу ПХП делает скорее чем к базе даных.. Хотя точно не буду утверждать..
 
 вот пример обработки результата виборки с базы данных: 
 $queryResult = array( 
array('id' => 1, 'parent_id' => 11, 'page' => 'News_1.1'), 
array('id' => 2, 'parent_id' => 0, 'page' => 'Index'), 
array('id' => 3, 'parent_id' => 17, 'page' => 'News_1.2.1'), 
array('id' => 5, 'parent_id' => 0, 'page' => 'News'), 
array('id' => 7, 'parent_id' => 17, 'page' => 'News_1.2.3'), 
array('id' => 8, 'parent_id' => 17, 'page' => 'News_1.2.2'), 
array('id' => 9, 'parent_id' => 0, 'page' => 'About'), 
array('id' => 11, 'parent_id' => 5, 'page' => 'News_1'), 
array('id' => 17, 'parent_id' => 11, 'page' => 'News_1.2'), 
); function tree($treeArray, $pid = 0) if (! $treeArray) return; 
> 
foreach($treeArray as $item) if ($item['parent_id'] == (int) $pid) echo($item['page'] . '') ; 
tree($treeArray, $item['id']); 
> 
> 
> tree($queryResult); 
 Не гарантирую, что самое оптимальное решение, но все же… 
 А я использую ajax поэтому у меня дерево не бывает затратным, разве что затраты идут только на прорисовку открытой ветки, которая изначально открывается, чтобы поисковику было понятно, где мы находимся в дереве, остальное грузится через json через ajax. Так что прорисовка дерева на клиенте идет :- ))
 
 а что там показывать… все элементарно просто.. 
1. Закидываете, напр. в базу запись с полями іd, navigation_title, parent_id. 
2. Далее при клике на пункте навигации отправляем аjax запрос, через тот же jquery, и параметром передаем id кликнутого пункта… 
3. на сервере вигребаем с базы все пункты меню, где parent_id = нашему id, который мы получили параметром, выгребенные даные отправляем обратно в json формате… 
4. На странице с которой был отправлен ajax-запрос получаем ответ, и если мы получили не пустой json-объект, строим DOM-дерево через javascript… p.s. можно вместо базы брать даные из того php-массива, или json файла, можно, если совсем по феншую реализовать систему кеширования.. корочче много чего можно… 
 Источник
 Примеры использования рекурсивной функции в 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);
 Основы хранения в БД древовидных структур можно почитать здесь.
 Источник
 shurinskiy / category_tree.php 
 This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters 
   /**  
  * Пример кода который будет упорядочивать рекурсивно массив и превращать его в дерево по  
  * идентификаторам родительских элементов - при этом он работает с произвольным уровнем вложенности.  
  * В этом примере, предпологается использование одной корневой категории, не имеющей потомков.  
  **/  
  $v_arr = array(  
  array(ID = > "0", name = > "корневая", parent= > "-1"),  
  array(ID = > "1", name = > "первая", parent= > "0"),  
  array(ID = > "2", name = > "вторая", parent= > "0"),  
  array(ID = > "3", name = > "третья", parent= > "1"),  
  array(ID = > "4", name = > "четвертая", parent= > "1"),  
  array(ID = > "5", name = > "пятая", parent= > "2"),  
  array(ID = > "6", name = > "шестая", parent= > "2"),  
  array(ID = > "7", name = > "седьмая", parent= > "5"),  
  array(ID = > "8", name = > "восьмая", parent= > "5")  
  );  
  $v_tree = array();  
  /**  
  * Построить дерево  
  **/  
  function make_tree($arr, &$tree, $par_id=-1) 
  foreach($arr as $item) 
  if($item['parent'] == $par_id) 
  if( ! is_array($tree)) 
  $tree = array();  
  >  
  $tree[$item['ID']] = array(  
  'name' = > $item['name'],  
  'ID' = > $item['ID'],  
  'parentID' = > $item['parent']  
  );  
  make_tree($arr, $tree[$item['ID']], $item['ID']);  
  >  
  >  
  >  
  /**  
  * Обойти дерево и преобразовать в список  
  **/  
  function menu_output($arr) 
  $html = '';  
  foreach($arr as $value) 
  if(! is_array($value)) continue;  
  $html .= ' < li >';  
  $html .= $value['name'];  
  $html .= menu_output($value);  
  $html .= ' ';  
  >  
  return $html ? ' < ul >'.$html.' ' : '';  
  >  
  make_tree($v_arr, $v_tree); // построить дерево из массива  
  echo menu_output(array_shift($v_tree)); // избавляюсь от корневого элемента дерева, а остальное вывожу как список  
 
 Источник
 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?
  '; foreach($array as $key => $value): if ($value['parent'] == $parent): $output .= ' '; 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:
  '; foreach($array as $key => $value): if ($value['parent'] == $parent): $output .= ' '; 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 .= '
 
  '; foreach($array as $key => $value): if ($value['parent'] == $parent): $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 .= '
 
 Источник
Читайте также:  Комбинированные фасады домов кирпич дерево