Рекурсивный алгоритм построения дерева
Написал: admin в категорию PHP, Алгоритмы, Программирование, tags: MySQL, PHP, Алгоритмы, Программирование, рекурсия, структуры данных
Этой заметкой, хочу начать серию посвященную алгоритмам и приемам программирования, и решению часто возникающих программистских задач.
И начну с задачи, построения древовидного списка.
Один из наиболее встречающихся методов решения - это построение рекурсии.
Итак, разберем этот метод на примере некоей структуры, хранящейся в таблице базы данных, и имеющей поле уникального идентификатора записи (Uid) и поле родительского идентификатора (ParentId)
Рабочая заготовка функции построения массива - списка (реализация на PHP, база MySQL):
function build_tree(&$tree, $parentID = 0, $level=-1){
$sql = "SELECT *
FROM some_table
WHERE parentID = ".$parentID."
ORDER BY name";
$q = mysql_query($sql);
$level += 1;
while ($row = mysql_fetch_assoc($q)){
$tmp_i = count($tree);
$tree[] = $row;
$tree[$tmp_i]["level"] = $level;
$tree = build_tree($tree, $row["Uid"], $level);
}
return $tree;
}
В результате мы получаем массив $tree - представляющий собой развернутое дерево связанных элементов, хранящихся в некоей таблице some_table, отсортированное по наименованию (полю name). При этом в массиве хранится также уровень вложенности каждого элемента (параметр level), который вычисляется в самой процедуре.
Допущения: элементы верхнего уровня в БД имеют parentID = 0, в итоговом массиве им соответствует level = 0
Естественно, подобным образом можно построить обработку некоторого массива данных (вместо обработки таблицы БД), но для наглядности и простоты я привел пример именно с БД, к тому же это наиболее часто встречающаяся задача.


Записи (RSS)
hi! Ну, уж если мы используем массив, то думаю было бы менее ресурсоемко сразу считать необходимые данные в массив и потом обрабатывать его. А так может получиться достаточно много запросов к БД, что при наших хостингах не самое лучшее решение
Хотя, это лишь моё имхо.
wmas
Да, всю обработку, безусловно, лучше вести в массиве, но в данном случае я преследовал цель максимально наглядно показать сам принцип, поэтому решил, что человеку маломальски знакомому с SQL будет легче воспринять такой вариант
А как сделать с ассоциативным массивом? на пример
Array
(
[1] => Array
(
[item] => 40
[2] => Array
(
[item] => 41
[5] => Array
(
[item] => 43
)
[6] => Array
(
[item] => 44
)
)
[3] => Array
(
[item] => 42
[7] => Array
(
[item] => 46
)
)
)
)