WebAccent Development

Этой заметкой, хочу начать серию посвященную алгоритмам и приемам программирования, и решению часто возникающих программистских задач.
И начну с задачи, построения древовидного списка.
Один из наиболее встречающихся методов решения - это построение рекурсии.

Итак, разберем этот метод на примере некоей структуры, хранящейся в таблице базы данных, и имеющей поле уникального идентификатора записи (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

Естественно, подобным образом можно построить обработку некоторого массива данных (вместо обработки таблицы БД), но для наглядности и простоты я привел пример именно с БД, к тому же это наиболее часто встречающаяся задача.

Это сообщение было написано Воскресенье 10 Август 2008 в 15:46Вы можете следить за последующими комментариями посредством RSS 2.0. Вы можете оставить отзыв, или уведомить свой ресурс(trackback).