Построение дерева из списка 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(), третий пункт, а также меньшие ограничения на формат входного массива делают предложенное решение наиболее применимым в разработке.

Записи