Недавно меня спросили, как в PHP быстро построить дерево на основе выборки из базы данных (MySQL). Пусть дерево в PHP должно храниться в виде вложенных массивов. Исходная таблица, содержит минимум три колонки — id (первичный ключ), parent_id (ключ родителя) и value (собственно данные). Буду считать, что id>0 и parent_id>0 (или parent_id=0 для корневых элементов). Может получиться даже не дерево, а целый лес, если есть несколько корневых элементов. Обычный подход к построению дерева — рекурсивная функция. Самое худшее, что делают программисты — для каждого уровня рекурсии функция делает запрос к БД, чтобы выбрать всех детей текущего элемента. Пожалуй, стоит написать небольшую «СУБД» для примеров:
class FakeDB
{
public static $querys=0;
public function fetchAll($q)
{
++FakeDB::$querys;
$rs=array (
array('id'=>1, 'parent_id'=>0, 'value'=>'aaaa'),
array('id'=>2, 'parent_id'=>0, 'value'=>'bbbb'),
array('id'=>3, 'parent_id'=>1, 'value'=>'cccc'),
array('id'=>4, 'parent_id'=>2, 'value'=>'dddd'),
array('id'=>5, 'parent_id'=>2, 'value'=>'eeee'),
array('id'=>6, 'parent_id'=>5, 'value'=>'ffff'),
array('id'=>7, 'parent_id'=>6, 'value'=>'gggg'),
array('id'=>8, 'parent_id'=>6, 'value'=>'hhhh')
);
if (preg_match('|WHERE\s+parent_id\s*=\s*(\d+)|i', $q, $m)) {
foreach ($rs as $key=>$val) {
if ($val['parent_id'] != $m[1]) {
unset($rs[$key]);
}
}
}
return $rs;
}
}
|
«СУБД» не отличается умом и сообразительностью, но умеет делать вид, что немного понимает SQL (а мы делаем вид, что ей верим, ага). Она умеет «извлекать» данные из захардкоженной «таблицы», либо всё и сразу, либо по условию «where parent_id=nnn», данные отсортированы по parent_id, а затем по id. И еще она умеет считать количество запросов за сеанс. Этого достаточно, чтобы успешно делать вид, что используются SQL запросы и, что характерно, в рамках примеров получать правильные «выборки».
Все последующие примеры используют этот класс, поэтому он должен быть подключен или добавлен к их коду, чтобы они работали (я опустил этот момент для краткости).
Итак, рекурсивное построение дерева — это что-то вроде:
function RecursiveTree1($parent)
{
$out = array();
$db = new FakeDB();
$rs = $db->fetchAll("SELECT * FROM my_table WHERE parent_id=$parent");
foreach ($rs as $row) {
$chidls = RecursiveTree1($row['id']);
if ($chidls) {
$row['childs'] = $chidls;
}
$out[]=$row;
}
return $out;
}
print_r(RecursiveTree1(0));
echo "querys=", FakeDB::$querys;
|
Девять запросов на таблицу из 8 строк, и все такое.
Можно извлечь все данные сразу, одним запросом и попробовать обработать его уже на PHP. Вот немного модифицированная версия:
$db=new FakeDB();
$rs = $db->fetchAll("SELECT * FROM my_table");
$rs2 = array();
foreach ($rs as $row) {
$rs2[$row['parent_id']][] = $row;
}
function RecursiveTree2(&$rs,$parent)
{
$out = array();
if (!isset($rs[$parent])) {
return $out;
}
foreach ($rs[$parent] as $row) {
$chidls = RecursiveTree2($rs, $row['id']);
if ($chidls) $row['childs'] = $chidls;
$out[] = $row;
}
return $out;
}
print_r(RecursiveTree2($rs2 ,0));
echo "querys=", FakeDB::$querys;
|
Запрос один, массивов несколько, для простоты и удобства я произвел преобразование исходной выборки в двумерный массив, сгруппировав по родителю.
А можно ли обойтись без рекурсии? Разумеется можно, потому что любую рекурсию можно развернуть в цикл, только радости от этого мало. Вопрос надо поставить по-другому. А можно ли построить дерево произвольной вложенности за один проход по исходным данным? Чтобы просто и быстро, без рекурсий и вложенных циклов? Это потребует некоторой организации исходных данных. Исходные данные должны быть отсортированы по уровню вложенности. Это очевидное требование для гарантии того, что, спускаясь линейно сверху вниз по выборке, нам никогда не попадется ребенок раньше своего родителя (в этом случае его просто еще некуда будет прицепить в массиве). Если предположить, что дети создаются всегда позже своих родителей и имеют id всегда больше parent_id (это бывает справедливо, когда деревья создаются человеком, ручками в визуальном интерфейсе, и потом элементы не перемещаются в другие ветки), то достаточно упорядочить элементы по parent_id.
Единственная проблема заключается в том, что в дереве (многомерном массиве с произвольными вложенностями) найти элемент с заданным id, чтобы прицепить к нему очередного ребенка, не так легко как бы хотелось. Например, попался элемент с parent_id=6, как теперь понять, что его папочка (в случае таблицы из примеров) имеет путь в дереве: $x[1]['childs'][1]['childs'][0]? Логично было бы иметь вспомогательный массив, где ключом будет id каждого элемента, а значением нечто, что укажет его положение конечном в дереве. Но как хранить пути?
На самом деле все немного проще. Достаточно вспомнить, что на любую переменную всегда можно сделать ссылку. Именно она (ссылка) и должна храниться во вспомогательном массиве. С этого момента о дереве и путях можно не думать. Все становится действительно линейно. Для большей выразительности я даже не буду использовать функцию:
$db = new FakeDB();
$rs = $db->fetchAll("SELECT * FROM my_table");
$tree = array(0=>array('id'=>0, 'parent_id'=>0, 'value'=>'root'));
$temp = array(0=>&$tree[0]);
foreach ($rs as $val) {
$parent = &$temp[ $val['parent_id'] ];
if (!isset($parent['childs'])) {
$parent['childs'] = array();
}
$parent['childs'][$val['id']] = $val;
$temp[$val['id']] = &$parent['childs'][$val['id']];
}
unset($rs, $temp, $val, $parent);
print_r($tree[0]['childs']);
echo "querys=", FakeDB::$querys;
|
Последний вопрос, который лично у меня остался — а зачем вообще строить такое дерево, если потом нет никакой удобной возможности, его обойти? Если для его обхода потребуется очередная рекурсивная процедура? Вопрос для меня открыт.
вот как я рисую дерево
SELECT ID, ParentID, Title FROM Tree;
while($row= mysql_fetch_assoc($res)){$tree[$row[ParentID]][$row[ID]] =$row[Title];}functionShowTree($tree,$pid=0){echo;foreach($treeas$id=>$root){if($pid!=$id)continue;if(count($root)){foreach($rootas$key=>$title){echo{$title};if(count($tree[$key]))ShowTree($tree,$key);}}}echo;}—
Моё решение:
function array_tree ($array, $id = 'id', $parent_id = 'parent_id', $children = 'children') {
$tree = [[$children => []]];
$references = [&$tree[0]];
foreach ($array as $item) {
if (isset ($references[$item[$id]])) {
$item[$children] = $references[$item[$id]][$children];
}
$references[$item[$parent_id]][$children][] = $item;
$references[$item[$id]] =& $references[$item[$parent_id]][$children][count($references[$item[$parent_id]][$children]) — 1];
}
return $tree[0][$children];
}