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

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

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

отсутствие рекурсии; достаточно одной функции;

всего один цикл по исходному массиву для полного построения дерева;

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

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