Преобразование 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 .= ‘

  • ‘.$tab.$value[‘id’].’:’.$value[‘name’];
    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 '

    ‘;


    Обсуждение на сайте: wp.od.ua

    Рубрика:  апреля 29, 2008.
    / » » »


    Похожие записи:

    7 комментариев на «Преобразование sql выборки в древовидную структуру, печать древовидных структур.»

    1. Там ошибки — у меня не сработало.

    2. спасибо — помогло.

    3. а как же комменты к коду?

    4. Здорово. Дерево есть, а как теперь его преобразовать из много мерного массива в обычный текст — не понятно. 🙁

      П.С. В коде кавычки неправильные и «пре» на выводе массивов съело, исправил — работает, теперь хорошо бы продолжение статьи 😉

    5. admin говорит:

      ну так там же 2 функции в комплекте есть

    6. Я чего сразу их удалил у себя, только потом внимание обратил на них 🙂

      Очень нужно продолжение, помогите, пожалуйста. Мне нужно вытащить название категорий, я уже весь мозг сломал как это сделать. Нужно, чтоб было так:

      href=»/maincat/subnamecat/sub-subnamecat/»

      Сейчас у меня просто «namecat» во всех категориях и подкатегориях выводится.

      П.С. Чего-то уведомления не получаю на мыло — выключено?

    7. Эх, автор совсем пропал… 🙁

      Почти доделал пути, но никак в толк не возьму пока, почему пути категорий в конце идут с предыдущими, хотя $pid = 0 в условии.

    Новости

  • Власть Киева экономит на школьниках
  • Украина и Польша начнут общий проект
  • Украинцы отдадут за газ всю зарплату
  • В Одессе откроется волонтерский центр
  • Россияне будут въезжать в Украину по загранпаспортам
  • В Харькове укрепляют границы с Россией
  • Планы прекратить транзит газа в Европу
  • Комментарии


    Расширеный поиск +

    Другие статьи

    Объявления

    Мои проекты на WordPress

    Одесса Процессор Недвижимости, - специализированная доска объявлений по недвижимости на стоимость сборки $300 с установкой.
    �льичевск - доска объявлений городская доска объявлений, основные разделы: недвижимость, транспорт, услуги, работа, куплю-продам. Стоимость сборки $300 с установкой.
    HiTech.Expert- все о высоких технологиях - разработка, поддержка.

    Счетчики

    our blog