Преобразование sql выборки в древовидную структуру, печать древовидных структур.
Сам я сталкивался с этой проблемой не один раз и каждый раз решал ее по-разному, с точки зрения высокого искусства, писанина мне моя абсолютно не нравилась, код работал правильно, но некрасиво.
Если хранить в БД иерархическую структуру, то есть дерево, то после запроса к таблице мы получим выборку данных в виде двумерного массива и наша задача сводится к тому, чтобы распечатать этот массив в виде дерева. Есть несколько моделей для хранения вложенных множеств Adjacency List самая простая, Nested Set и другие гибридные варианты. Все эти модели без исключения содержат 2 основных поля ID уникальный идентификатор элемента и parentID идентификатор элемента родительского узла. Впрочем нам больше ничего не понадобится.
Разабьем задачу на 2 этапа :
Первый - преобразование двумерного массива исходных данных в многомерный иерархический массив, второй этап - распечатывание многомерного массива ну здесь ничего сложного нет используя рекурсию делается это элементарно, а вот с первой частью возникает проблема. Итак имеем такую структуру данных на входе
$data = array( array('id' => 1, 'parentId' => 3, 'name' => 'первый'), array('id' => 3, 'parentId' => 0, 'name' => 'третий'), array('id' => 7, 'parentId' => 3, 'name' => 'седьмой'), array('id' => 9, 'parentId' => 3, 'name' => 'девятый'), array('id' => 12, 'parentId' => 0, 'name' => '№ 12'), array('id' => 24, 'parentId' => 7, 'name' => '№ 24'), array('id' => 25, 'parentId' => 1, 'name' => '№ 25'), array('id' => 46, 'parentId' => 7, 'name' => '№ 46'), array('id' => 5, 'parentId' => 7, 'name' => '№ 5'), array('id' => 4, 'parentId' => 5, 'name' => '№ 4'), array('id' => 13, 'parentId' => 0, 'name' => '№ 13'), array('id' => 14, 'parentId' => 0, 'name' => '№ 14'), );
Пишем функцию structuring которая собственно и будет делать основную работу, разворачивать двумерную структуру в древоподобный массив. И первое что нам надо сделать это отсортировать исходные данные по полю parentId в порядке убывания если этого не сделать алгоритм будет работать неправильно. Обычно способ сортировки задается в SQL запросе но мы предполагаем, что такой возможности нет. C помощью пользавательской функции sortParent2 и usort() сортируем массив по родителям, и по id если родители одинаковые.
function sortParent2($a,$b){ if($a['parentId'] == $b['parentId']) { return ($a['id'] < $b['id'])? -1:1; } else return ($a['parentId'] < $b['parentId'])? 1:-1; } function structuring($data){ usort($data, 'sortParent2'); //сортировка по parentID // корреляция ключей масиива while (list ($key, $val) = each ($data)) { $artmp[$val['id']] = $val; } unset($data); reset($artmp); $i = 0; while (list ($key, $val) = each ($artmp)) { $value = $artmp[$key]; $id = $value['id']; $parentID = $value['parentId']; if ( $parentID != 0 ) { $artmp[$parentID]['subCat'][] = &$artmp[$key]; $i++; } else { break ; } } return array_splice ($artmp, $i); }
Проходим по новому массиву $artmp и если елемент имеет родителя то есть выполняется условие (parentId != 0), то мы создаем у родительского элемента массив-подкатегорию subCat и добавляем в него ссылку на текущий элемент, обратите внимание что добавляется не сам элемент а именно ссылка на него - это и есть ключевой момент алгоритма. Мы как бы рисуем новое дерево прямо по старой двумерной структуре не разрушая ее. По ходу фиксируем счетчик $i++; И только когда дерево полностью прорисовнно вглубину с помощью сылочных связей, удаляем лишние элементы, если parentId = 0 цикл завершается т.к. дальше идут элементы 0 уровня без родителей
И последнее действие вырезаем все ненужное с помощью array_splice оставляем только элементы первого уровеня.
Теперь мы имеем структуру в виде дерева.
Ну и привожу весь код целиком, включая 2 варианта распечатки с помощью вычисляемого отступа, и как стрктуру UL-LI тегов.
$data = array( array('id' => 5, 'parentId' => 7, 'name' => '№ 5'), array('id' => 4, 'parentId' => 5, 'name' => '№ 4'), array('id' => 13, 'parentId' => 0, 'name' => '№ 13'), array('id' => 14, 'parentId' => 0, 'name' => '№ 14'), array('id' => 1, 'parentId' => 3, 'name' => 'первый'), array('id' => 3, 'parentId' => 0, 'name' => 'третий'), array('id' => 7, 'parentId' => 3, 'name' => 'седьмой'), array('id' => 9, 'parentId' => 3, 'name' => 'девятый'), array('id' => 12, 'parentId' => 0, 'name' => '№ 12'), array('id' => 24, 'parentId' => 7, 'name' => '№ 24'), array('id' => 25, 'parentId' => 1, 'name' => '№ 25'), array('id' => 46, 'parentId' => 7, 'name' => '№ 46'), ); echo ''; print_r( $data ); echo '‘;
function sortParent2($a,$b){
if($a['parentId'] == $b['parentId']) {
return ($a['id'] < $b['id'])? -1:1;
} else return ($a['parentId'] < $b['parentId'])? 1:-1;
}function structuring($data){
usort($data, 'sortParent2');while (list ($key, $val) = each ($data)) {
$artmp[$val['id']] = $val;
}
echo ''; print_r( $artmp ); echo '‘;
unset($data);
reset($artmp);
$i = 0;
while (list ($key, $val) = each ($artmp)) {
$value = $artmp[$key];
$id = $value['id'];
$parentID = $value['parentId'];
if ( $parentID != 0 ) {
$artmp[$parentID]['subCat'][] = &$artmp[$key];
$i++;
} else {
break ;
}
}return array_splice ($artmp, $i);
}
$tree = structuring($data);
function printData($data, $_level = 0){
$tab = str_repeat(’ | ’,$_level);
foreach ($data as $value) {
$st .= $tab.$value['id'].’:’.$value['name'].’
‘;
if( isset( $value['subCat'] ) ) {
$st .= printData($value['subCat'], $_level+1);
}
}
return $st;
}function printDataUl($data, $_level = 0){
foreach ($data as $value) {
$st .= ‘
if( isset( $value['subCat'] ) ) {
$st .= printDataUl($value['subCat'], $_level+1);
}
$st .= ‘
‘;
}
$st = ‘
- ‘.$st.’
‘;
return $st;
}
//echo printData($tree);
echo printDataUl($tree);
echo ‘
'; print_r( $tree ); echo '
‘;
полезный код
— мая 19, 2008 | 1:06 пп
Автору мега респект
Женя — августа 27, 2008 | 8:22 пп