Построение дерева из списка ID-Parent |
217
|
|
 nectarin
Сергей NectarIn Новиков
Специализации: 1
|
|
|
Поскольку данная задача возникает у разработчиков довольно часто, хотел бы поделиться простым и эффективным решением. Всё, что нам потребуется — это исходный массив примерно такого вида:
| 1 | $listIdParent = array(
|
| 2 | 1 => array('parent' => 0),
|
| 3 | 2 => array('parent' => 1),
|
| 4 | 3 => array('parent' => 1),
|
| 5 | 4 => array('parent' => 2),
|
| 6 | 5 => array('parent' => 4)
|
| 7 | ); |
$listIdParent = array(
1 => array('parent' => 0),
2 => array('parent' => 1),
3 => array('parent' => 1),
4 => array('parent' => 2),
5 => array('parent' => 4)
);
Как нетрудно догадаться, ключи исходного списка являются ID, а поля
parent содержат ссылки на родительский элемент в дереве. Элемент с
parent, равным 0, является корневым. Такой элемент должен быть единственным в списке, и в целом дерево должно быть консистентным (не должно быть "битых" ссылок и рекурсивной вложенности) — и, пожалуй, это единственные ограничения. Таким образом, важной особенностью используемого метода является то, что элементы исходного списка могут идти в любом порядке, в отличие от известного способа с
array_pop(), который требует, чтобы элементы были отсортированы по уровню (глубине вложенности).
Дерево строится следующей функцией:
| 1 | /**
|
| 2 | * Построение дерева из списка ID-Parent.
|
| 3 | *
|
| 4 | * @param array Исходный список.
|
| 5 | * @return array Дерево.
|
| 6 | */
|
| 7 | function buildTree(array $listIdParent) {
|
| 8 | // Подготовка ID корневого узла.
|
| 9 | $rootId = 0;
|
| 10 |
|
| 11 | // Обход списка и обработка узлов.
|
| 12 | foreach ($listIdParent as $id => $node) {
|
| 13 | if ($node['parent']) {
|
| 14 | // Сохранение в родительском узле ссылки на текущий.
|
| 15 | $listIdParent[$node['parent']]['sub'][$id] =& $listIdParent[$id];
|
| 16 | } else {
|
| 17 | // Сохранение ссылки на корневой элемент.
|
| 18 | $rootId = $id;
|
| 19 | }
|
| 20 | }
|
| 21 |
|
| 22 | // Возврат корневого узла, содержащего всё построенное дерево.
|
| 23 | return array($rootId => $listIdParent[$rootId]);
|
| 24 | } |
/**
* Построение дерева из списка ID-Parent.
*
* @param array Исходный список.
* @return array Дерево.
*/
function buildTree(array $listIdParent) {
// Подготовка ID корневого узла.
$rootId = 0;
// Обход списка и обработка узлов.
foreach ($listIdParent as $id => $node) {
if ($node['parent']) {
// Сохранение в родительском узле ссылки на текущий.
$listIdParent[$node['parent']]['sub'][$id] =& $listIdParent[$id];
} else {
// Сохранение ссылки на корневой элемент.
$rootId = $id;
}
}
// Возврат корневого узла, содержащего всё построенное дерево.
return array($rootId => $listIdParent[$rootId]);
}
Для повышения удобочитаемости в коде функции опущены необходимые проверки входного массива на корректность.
Результат работы функции выглядит так:
| 1 | array(
|
| 2 | 1 => array(
|
| 3 | 'parent' => 0,
|
| 4 | 'sub' => array(
|
| 5 | 2 => array(
|
| 6 | 'parent' => 1,
|
| 7 | 'sub' => array(
|
| 8 | 4 => array(
|
| 9 | 'parent' => 2,
|
| 10 | 'sub' => array(
|
| 11 | 5 => array('parent' => 4)
|
| 12 | )
|
| 13 | )
|
| 14 | )
|
| 15 | ),
|
| 16 | 3 => array(
|
| 17 | 'parent' => 1
|
| 18 | )
|
| 19 | )
|
| 20 | )
|
| 21 | ) |
array(
1 => array(
'parent' => 0,
'sub' => array(
2 => array(
'parent' => 1,
'sub' => array(
4 => array(
'parent' => 2,
'sub' => array(
5 => array('parent' => 4)
)
)
)
),
3 => array(
'parent' => 1
)
)
)
)
При сравнении с другими способами построения дерева из списка ID-Parent можно выделить следующие основные моменты:
- отсутствие рекурсии; достаточно одной функции;
- всего один цикл по исходному массиву для полного построения дерева;
- все манипуляции с массивом заключаются в установке ссылок на дочерние элементы, что сильно экономит память и увеличивает быстродействие (по сравнению с методами, перемещающими сами элементы массива).
И хотя первые два пункта так же присущи алгоритму с
array_pop(), третий пункт, а также меньшие ограничения на формат входного массива делают предложенное решение наиболее применимым в разработке.
Новости inPHP.org
Содействуют развитию
Участники проекта
Статистика проекта