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

228

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

Просмотров: 3616

Разделы публикаций

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