Таблица в базе данных:
+--+-------------+--------+
|id|name |parentid|
+--+-------------+--------+
|1 |Имя раздела 1|0 |
|2 |Имя раздела 2|0 |
|3 |Имя раздела 3|1 |
|4 |Имя раздела 4|2 |
|5 |Имя раздела 5|4 |
|6 |Имя раздела 6|2 |
+--+-------------+--------+
Массив, полученный после выборки из базы данных:
$arr = array(
array(
'id' => '1',
'name' => 'Имя раздела 1',
'parentid' => '0'
),
array(
'id' => '2',
'name' => 'Имя раздела 2',
'parentid' => '0'
),
array(
'id' => '3',
'name' => 'Имя раздела 3',
'parentid' => '1'
),
array(
'id' => '4',
'name' => 'Имя раздела 4',
'parentid' => '2'
),
array(
'id' => '5',
'name' => 'Имя раздела 5',
'parentid' => '4'
),
array(
'id' => '6',
'name' => 'Имя раздела 6',
'parentid' => '2'
),
);
Функции, для рекурсивного построения дерева:
function form_tree($mess)
{
if (!is_array($mess)) {
return false;
}
$tree = array();
foreach ($mess as $value) {
$tree[$value['parentid']][] = $value;
}
return $tree;
}
//$parent_id - какой parentid считать корневым
//по умолчанию 0 (корень)
function build_tree($cats, $parent_id)
{
if (is_array($cats) && isset($cats[$parent_id])) {
$tree = '<ul>';
foreach ($cats[$parent_id] as $cat) {
$tree .= '<li>' . $cat['name'];
$tree .= build_tree($cats, $cat['id']);
$tree .= '</li>';
}
$tree .= '</ul>';
} else {
return false;
}
return $tree;
}
Примеры использования
Вариант А:
$tree = form_tree($arr);
echo build_tree($tree, 0);
- Имя раздела 1
- Имя раздела 2
- Имя раздела 4
- Имя раздела 6
Вариант Б:
$tree = form_tree($arr);
echo build_tree($tree, 2);
- Имя раздела 4
- Имя раздела 6
Как работает алгоритм
Исходный массив обрабатывается функцией form_tree();
.
Она формирует массив следующего вида:
$arr = array(
0 => array(
array(
'id' => '1',
'name' => 'Имя раздела 1',
'parentid' => '0'
),
array(
'id' => '2',
'name' => 'Имя раздела 2',
'parentid' => '0'
),
),
1 => array(
array(
'id' => '3',
'name' => 'Имя раздела 3',
'parentid' => '1'
),
),
2 => array(
array(
'id' => '4',
'name' => 'Имя раздела 4',
'parentid' => '2'
),
array(
'id' => '6',
'name' => 'Имя раздела 6',
'parentid' => '2'
),
),
4 => array(
array(
'id' => '5',
'name' => 'Имя раздела 5',
'parentid' => '4'
),
),
);
Как можно видеть, элементы исходного массива были разбиты на группы, согласно их родителю. В итоге получилась схема вида: родитель => массив потомков
.
Далее, функция build_tree()
рекурсивно обрабатывает этот массив.
Она начинает свою работу с ID раздела, указанного в качестве корневого.
В первую очередь, она стремится перебрать потомков данного раздела. В процессе перебора функция проверяет, а не является ли текущий потомок в свою очередь чьим-то родителем? Для этого функция вызывает саму себя, с указанием в качестве ID корневого раздела ID текущего элемента.

Рассмотрим работу алгоритма на примере "Вариант А":
- Мы начинаем перебор с
ID = 0
, в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это
Имя раздела 1
.
- Выводим этот раздел.
- Начинаем перебор с
ID = 1
, в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это
Имя раздела 3
.
- Выводим этот раздел.
- Мы начинаем перебор с
ID = 3
, в качестве корневого.
- Подразделов нет, функция завершает свою работу.
- Разделов больше нет, функция завершает свою работу.
- Продолжаем перебор с
ID = 0
, в качестве корневого.
- Второй раздел, который мы встречаем во время перебора, это
Имя раздела 2
.
- Выводим этот раздел.
- Начинаем перебор с
ID = 2
, в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это
Имя раздела 4
.
- Выводим этот раздел.
- Мы начинаем перебор с
ID = 4
, в качестве корневого.
- Первый раздел, который мы встречаем во время перебора, это
Имя раздела 5
.
- Выводим этот раздел.
• Мы начинаем перебор с ID = 5
, в качестве корневого.
• Подразделов нет, функция завершает свою работу.
- Разделов больше нет, функция завершает свою работу.
- Второй раздел, который мы встречаем во время перебора, это
Имя раздела 6
.
- Выводим этот раздел.
- Мы начинаем перебор с
ID = 6
, в качестве корневого.
- Подразделов нет, функция завершает свою работу.
- Разделов больше нет, функция завершает свою работу.
- Разделов больше нет, функция завершает свою работу.
В примере выше, уровень вложенности соответствует тому, в который раз по счету функция build_tree()
вызвала сама себя.