Рекурсивный алгоритм построения дерева

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

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

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

$tree = build_tree($tree, $row["], $level);

}

return $tree;

}

В результате мы получаем массив $tree - представляющий собой развернутое дерево связанных элементов, хранящихся в некоей таблице some_table, отсортированное по наименованию (полю name).

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