将扁平结构整理成树只知道父母

Question

Given the following structure of arrays:

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
   ),
   77 => array(
       'parent_id' => 55,
       'ident' => 'test 2',
       'depth' => 2,
   )
);

Is there a general algorithm that can be used to turn that into a nested tree?

i.e.

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
       'children' => array(
            77 => array(
                'parent_id' => 55,
                'ident' => 'test 2',
                'depth' => 2,
           )
       )
   )
);

The example i have provided is simplified, the real case includes hundreds of nodes + a depth of up to 15.

Answer 1

Working with references helps a lot. This way you can still append to the children even if they're already inserted.

foreach ($array as $key => &$sub) {
    if (isset($sub['parent_id'])) {
        $array[$sub['parent_id']]['children'][$key] = &$sub;
    }
}
unset($sub); // unset the reference to make sure to not overwrite it later...

// now remove the entries with parents
foreach ($array as $key => $sub) {
    if (isset($sub['parent_id'])) { 
        unset($array[$key]);
    }
}

Some demo for this: http://3v4l.org/D6l6U#v500