Преобразование массива из одного в многомерный на основе значений родительского идентификатора

Question

У меня есть одномерный массив объектов, которые представляют многомерные данные:

array(
    array(
        "id" => 45,
        "parent_id" => null
    ),
    array(
        "id" => 200,
        "parent_id" => 45
    ),
    array(
        "id" => 345,
        "parent_id" => 45
    ),
    array(
        "id" => "355",
        "parent_id" => 200
    )
);

Как мне преобразовать его в многомерный массив:

array(
    array(
        "id" => 45,
        "parent_id" => null,
        "children" => array(
            array(
                "id" => 200,
                "parent_id" => 45,
                "children" => array(
                    "id" => "355",
                    "parent_id" => 200
                )

            ),
            array(
                "id" => 345,
                "parent_id" => 45
            ),
        )
    ),
);

Answer 1

Следующий пример кода преобразует массив $array в древовидную структуру, которую вы ищете:

// key the array by id
$keyed = array();
foreach($array as &$value)
{
    $keyed[$value['id']] = &$value;
}
unset($value);
$array = $keyed;
unset($keyed);

// tree it
$tree = array();
foreach($array as &$value)
{
    if ($parent = $value['parent_id'])
        $array[$parent]['children'][] = &$value;
    else
        $tree[] = &$value;
}
unset($value);
$array = $tree;
unset($tree);

var_dump($array); # your result

Это не работает, если существует существующий родительский идентификатор, который 0, Но может быть легко изменено, чтобы отразить это.

Это связанный вопрос, в котором исходный массив уже введен в ключ, поэтому первая половина решения может быть сэкономлена: вложенный массив. Третий уровень исчезает.

Редактировать:

Так как же это работает? При этом используются псевдонимы переменных PHP (также называемые ссылками) и (временные) массивы, которые используются для хранения а) псевдонимов узлов ($keyed) и б) построить новый порядок деревьев ($tree).

Не могли бы вы [...] объяснить цель $array = $keyed, $array = $tree а то unsets?

Как оба, $keyed а также $tree содержат ссылки на значения в $array Я сначала скопирую эту информацию в $array Например:

$array = $keyed;

Как сейчас $keyed все еще установлен (и содержит ссылки на те же значения, что и в $array), $keyed не установлен:

unset($keyed);

Это отменяет все ссылки в $keyed и гарантирует, что все значения в $array больше не ссылаются (значение пересчета уменьшается на единицу).

Если временные массивы не будут сброшены после итерации, их ссылки все равно будут существовать. Если вы используете var_dump на $array, вы увидите, что все значения будут иметь & впереди, потому что они все еще упоминаются. unset($keyed) удаляет эти ссылки, var_dump($array) снова, и вы увидите & s ушли.

Я надеюсь, что это было понятно, ссылки могут быть трудно следовать иногда, если вы не владеете ими. Это часто помогает мне думать о них как о переменных псевдонимах.

Если вы хотите какое-то упражнение, подумайте о следующем:

Как конвертировать ваши $array от плоского к дереву с одной итерацией foreach?

Решите самостоятельно, когда вы хотите перейти по ссылке, содержащей решение.

Answer 2

function convertArray ($array) {
  // First, convert the array so that the keys match the ids
  $reKeyed = array();
  foreach ($array as $item) {
    $reKeyed[(int) $item['id']] = $item;
  }
  // Next, use references to associate children with parents
  foreach ($reKeyed as $id => $item) {
    if (isset($item['parent_id'], $reKeyed[(int) $item['parent_id']])) {
      $reKeyed[(int) $item['parent_id']]['children'][] =& $reKeyed[$id];
    }
  }
  // Finally, go through and remove children from the outer level
  foreach ($reKeyed as $id => $item) {
    if (isset($item['parent_id'])) {
      unset($reKeyed[$id]);
    }
  }
  return $reKeyed;
}

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

ПРИМЕЧАНИЕ. Эта функция основана на parent_id для предметов без родителя либо NULL или не установлен вообще, так что isset() возвращается FALSE в последнем цикле.