Построение дерева из списка ID-Parent

August 19, 2014

Поскольку данная задача возникает у разработчиков довольно часто, хотел бы поделиться простым и эффективным решением. Всё, что нам потребуется — это исходный массив примерно такого вида:

$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(), который требует, чтобы элементы были отсортированы по уровню (глубине вложенности).

Дерево строится следующей функцией:

/**
* Построение дерева из списка 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]);
}



Для повышения удобочитаемости в коде функции опущены необходимые проверки входного массива на корректность.

Результат работы функции выглядит так:

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 можно выделить следующие основные моменты:

  1. отсутствие рекурсии;
  2. достаточно одной функции;
  3. всего один цикл по исходному массиву для полного построения дерева;
  4. все манипуляции с массивом заключаются в установке ссылок на дочерние элементы, что сильно экономит память и увеличивает быстродействие (по сравнению с методами, перемещающими сами элементы массива).


И хотя первые два пункта так же присущи алгоритму с array_pop(), третий пункт, а также меньшие ограничения на формат входного массива делают предложенное решение наиболее применимым в разработке.

Комментарии

comments powered by Disqus