Алгоритм построения древа каталога
вам нужна функция, которая будет проходить по массиву и находить для каждого элемента родителя (если parentID != 0) и записывать этот элемент в дети родителя (по ссылке), после чего будет удалять все элементы массива, у которых parentID != 0. В результате у вас останутся только те деревья, чьи корни действительно являются корневыми элементами искомого дерева. Если будет время, позже напишу пример.
основную суть алгоритма я представляю так: берем строку если родитель == 0 $array[id]=$name; иначе $array[parentID][]=$name; берем следующую строку и все заново. Логично?
2 ответа 2
Таблица в базе данных:
+--+-------------+--------+ |id|name |parentid| +--+-------------+--------+ |1 |Имя раздела 1|0 | |2 |Имя раздела 2|0 | |3 |Имя раздела 3|1 | |4 |Имя раздела 4|2 | |5 |Имя раздела 5|4 | |6 |Имя раздела 6|2 | +--+-------------+--------+ Массив, полученный после выборки из базы данных:
$arr = array( array( 'id' => '1', 'name' => 'Имя раздела 1', 'parentid' => '0' ), array( 'id' => '2', 'name' => 'Имя раздела 2', 'parentid' => '0' ), array( 'id' => '3', 'name' => 'Имя раздела 3', 'parentid' => '1' ), array( 'id' => '4', 'name' => 'Имя раздела 4', 'parentid' => '2' ), array( 'id' => '5', 'name' => 'Имя раздела 5', 'parentid' => '4' ), array( 'id' => '6', 'name' => 'Имя раздела 6', 'parentid' => '2' ), ); Функции, для рекурсивного построения дерева:
Примеры использования
Вариант А:
$tree = form_tree($arr); echo build_tree($tree, 0); $tree = form_tree($arr); echo build_tree($tree, 2); Как работает алгоритм
Исходный массив обрабатывается функцией form_tree(); . Она формирует массив следующего вида:
$arr = array( 0 => array( array( 'id' => '1', 'name' => 'Имя раздела 1', 'parentid' => '0' ), array( 'id' => '2', 'name' => 'Имя раздела 2', 'parentid' => '0' ), ), 1 => array( array( 'id' => '3', 'name' => 'Имя раздела 3', 'parentid' => '1' ), ), 2 => array( array( 'id' => '4', 'name' => 'Имя раздела 4', 'parentid' => '2' ), array( 'id' => '6', 'name' => 'Имя раздела 6', 'parentid' => '2' ), ), 4 => array( array( 'id' => '5', 'name' => 'Имя раздела 5', 'parentid' => '4' ), ), ); Как можно видеть, элементы исходного массива были разбиты на группы, согласно их родителю. В итоге получилась схема вида: родитель => массив потомков .
Далее, функция build_tree() рекурсивно обрабатывает этот массив.
Она начинает свою работу с ID раздела, указанного в качестве корневого.
В первую очередь, она стремится перебрать потомков данного раздела. В процессе перебора функция проверяет, а не является ли текущий потомок в свою очередь чьим-то родителем? Для этого функция вызывает саму себя, с указанием в качестве ID корневого раздела ID текущего элемента.
Рассмотрим работу алгоритма на примере «Вариант А»:
- Мы начинаем перебор с ID = 0 , в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это Имя раздела 1 .
- Выводим этот раздел.
- Начинаем перебор с ID = 1 , в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это Имя раздела 3 .
- Выводим этот раздел.
- Мы начинаем перебор с ID = 3 , в качестве корневого.
- Подразделов нет, функция завершает свою работу.
- Начинаем перебор с ID = 2 , в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это Имя раздела 4 .
- Выводим этот раздел.
- Мы начинаем перебор с ID = 4 , в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это Имя раздела 5 .
- Выводим этот раздел.
• Мы начинаем перебор с ID = 5 , в качестве корневого.
• Подразделов нет, функция завершает свою работу. - Разделов больше нет, функция завершает свою работу.
- Мы начинаем перебор с ID = 6 , в качестве корневого.
- Подразделов нет, функция завершает свою работу.
В примере выше, уровень вложенности соответствует тому, в который раз по счету функция build_tree() вызвала сама себя.
Источник
Применение простых алгоритмов в 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--; > > >
Теперь можем вызвать построение дерева, начиная с 0 элемента и 0 уровня. Замечу, что приведённый метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.
$tree = new Tree(); $tree->buildTree(0, 0);
# $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 "" . $value["id_tree_test"] . " : " . $value["title"] . ""; $level++; $this->buildTree($value["id_tree_test"], $level); $level--; > > > > $tree = new Tree(); $tree->buildTree(0, 0); ?>Данный метод применим при построении меню на сайте, каталогов продукции и т. п. У него, разумеется, есть недостатки. При построении достаточно большого каталога метод будет работать довольно долго. Но выигрыш тут в том, что метод можно модифицировать и ограничить не только уровнем входа, но и уровнем погружения. Таким образом, можно достраивать дерево постепенно при запросе пользователей, что решит данную проблему.
Я не рассматриваю здесь проблемы хранения такой структуры, т. к. нас сейчас интересует только обход массива.
На этом всё! Безошибочного вам кода!
Источник
Построение дерева иерархии с помощью PHP / MySQL
Рассмотрим пример построения дерева иерархии (в развернутом виде) на основе информации из базы данных с помощью PHP и MySQL. Ключ к решению данной задачи - использование рекурсивной функции. Иерархия разделов будет храниться в таблице базы данных MySQL.
Ниже на скриншоте показана данная таблица (catalogue):
Далее напишем следующий PHP-скрипт:
1. Файл dbopen.php (открывает соединение с MySQL)
if (!mysql_select_db($databaseName, $link)) < printf("Ошибка базы данных !"); exit(); >?>2. Файл index.php (основной скрипт)
Всю работу выполняет рекурсивная функция ShowTree(). Ниже на скриншоте показан пример работы index.php:
Подборка курсов по PHP
4.4 Skillbox еще 3 курса
4.4 GeekBrains еще 1 курс
4.2 Оtus
4.4 HTML Academy
4.4 Hexlet
4.7 HEDU (irs.academy)
Комментарии
P.s я писал на js. не сильно отличается. Спасибо за идею!
var str='';
function ShowTree(ParentID) var result=SCatList.GetChild(ParentID, false);Я просто в бешенстве от простоты автора!
Зачем ему $link если он нигде не используется!И при всем уважении такого результата при этом коде получиться не может, там в исходнике html не пойми что будет!!
Лучше использовать references . Можно все сделать 1 запросом и без рекурсии
вот пример - http://phpblog.com.ua/2010/06/tree-with-references/Есть ещё один способ, но требующий умного подхода. Выбрать всё из базы одним запросом и запихать в многоуровневый массив, и уже потом работать с массивом. Загвоздка состоит в том, что бы отсортировать массив так, что бы сабы были именно под своими парентами.
К примеру есть такой массив:Array (
[0] => Array (
[s_id] => 5
[s_title] => Контент сайта
[c_id] => 34
[c_parent] => 0
[c_title] => Контент сайта
)
[1] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 35
[c_parent] => 0
[c_title] => Web дизайн
)
[2] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 36
[c_parent] => 40
[c_title] => Web программирование
)
[3] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 37
[c_parent] => 36
[c_title] => PHP
)
[4] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 38
[c_parent] => 0
[c_title] => JavaScript
)
[5] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 39
[c_parent] => 0
[c_title] => MySQL
)
[6] => Array (
[s_id] => 6
[s_title] => Статьи
[c_id] => 40
[c_parent] => 0
[c_title] => Joomla
)
)Описание:
[s_id] - ид секции
[s_title] => заголовок секции
[c_id] => ид категории
[c_parent] => родитель категории
[c_title] => заголовок категории
Это полная выборка из бд. Сделать что бы было такКонтент сайта
--Контент сайтаСтатьи
--Web дизайн
--JavaScript
--MySQL
--Joomla
----Web программирование
------PHP
пока никто не смог, а было бы хорошо@bibendi:
Этот метод стоит использовать, если у вас максимальный размер вложенности состовляет не более 3-4 уровней.Если же больше, то тут тоже надо смотреть, а как сильно будет нагружатся БД??
Т.е. на сколько часто будет извлекатсья информация, допусти для популярного интернет-магазина с подкатегориями более чем в 2-3 уровня это будет непозволительная роскошь использовать столько ресурсов.Короче, к чему я всё клоню, есть такой алгоритм Nested Sets (вложенные множества).
Вот его и нужно использовать, если предпологается большая многоуровневая вложенность и/или большая нагрузка на сервер - читай много посетителей.Конечно, кто-то скажет, что эта бодяга решается с помошью кэширования, безусловно его можно использовать и даже нужно, но в совокупности с этим алгоритмом вы добъётесь впечатляющих результатов скорости, т.к. для извлечения пркатически любой информации из дерева необходимо всего ОДИН запрос в БД.
здесь есть инфа, если кого заинтересовало http://www.getinfo.ru/article610.html
не сочтите за рекламу другого сайта.Я просто столкнулся с такой проблемой, когда закачик дал задание разработать каталог с 6-8 уровнями вложенности и в каталоге было более 1500 категорий о_О
Уважаемый, для этого и существует кеширование файлов.
Один раз подключились, загнали все у виде массива в файл, а потом просто вытаскиваеш. Когда нужно будет, так и обновиш файл.
Если что, смотри в сторону serialize()Источник
