Алгоритм для создания многомерного массива

Question

Я использую PHP, и мне нужна помощь с простой задачей с массивом.

Это мой пример массива:

$arr = array(
    0 => NULL, 
    1 => NULL, 
    2 => NULL, 
    3 => NULL, 
    8 => '2', 
    9 => '2', 
    10 => '2', 
    11 => '2', 
    12 => '3', 
    13 => '3', 
    14 => '8', 
    15 => '8', 
    16 => '14', 
    17 => '14', 
    18 => '14' 
); 

Ключи массива представляют собой идентификаторы (уникальный).
Значения: parentIDs, то есть идентификатор родительского «узла». NULL означает, что нет родительского идентификатора (то есть первого измерения нового массива).

Теперь мне нужно создать новый многомерный массив, который имеет все дочерние элементы под их родительскими идентификаторами. (Возможно, это звучит очень запутанно, извините за отсутствие описательных способностей. Ниже приведен пример, который должен сделать все более ясным)

Вот как выглядит новый массив моего примера после функции «сортировки» или что-то еще вы называете это, был применен:

 
$arr = array(
0 => array(), 
1 => array(), 
2 => array(
    8 => array(
     14 => array(
      16 => array(), 
      17 => array(), 
      18 => array() 
), 
     15 => array() 
), 
    9 => array(), 
    10 => array(), 
    11 => array() 
), 
3 => array(
    12 => array(), 
    13 => array() 
) 
); 

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

Answer 1

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

function add_branch(&$tree, $datum, $parent) { 

    // First we have the base cases: 
    // If the parent is NULL then we don't need to look for the parent 
    if ($parent == NULL) { 
     $tree[$datum] = array(); 
     return true; 
    } 

    // If the array we've been given is empty, we return false, no parent found in this branch 
    if (! count($tree)) { 
     return false; 
    } 


    // We loop through each element at this level of the tree... 
    foreach($tree as $key => $val) { 

     // If we find the parent datum... 
     if ($key == $parent) { 

      // We add the new array in and we're done. 
      $tree[$key][$datum] = array(); 
      return true; 
     } 

     // Otherwise, check all the child arrays 
     else { 

      // Now we check to see if the parent can be found in the curent branch 
      // If a recursive call found a parent, we're done 
      if (add_branch($tree[$key], $datum, $parent)) { 
       return true; 
      } 
     } 
    } 

    // If none of the recursive calls found the parent, there's no match in this branch 
    return false; 

} 

Замечания достаточно подробные, в надежде, что вы поймете, что происходит. Я бы посоветовал вам немного почитать о рекурсивных функциях, чтобы обдумать это.

Это, как он будет использоваться:

$arr = array(
0 => NULL, 
1 => NULL, 
2 => NULL, 
3 => NULL, 
8 => '2', 
9 => '2', 
10 => '2', 
11 => '2', 
12 => '3', 
13 => '3', 
14 => '8', 
15 => '8', 
16 => '14', 
17 => '14', 
18 => '14' 
); 


$final = array(); 

foreach ($arr as $datum => $parent) { 
    add_branch($final, $datum, $parent); 
} 

$final теперь имеет правильный массив отделки, как указано в этом вопросе.

Answer 2

Two pass foreach делает трюк. Это будет рекурсивно связывать всех детей с родителями.

//$array is the input 

//The tree starts out as a flat array of the nodes 
$tree = array_combine(
    array_keys($array), 
    array_fill(0, count($array), array()) 
); 

//link children to parents (by reference) 
foreach($tree as $key => &$row) { 
    if(! is_null($array[$key])) { 
     $tree[ $array[$key] ][ $key ] =& $row; 
    } 
} 

//remove non-root nodes 
foreach(array_keys($tree) as $key) { 
    if(! is_null($array[$key])) { 
     unset($tree[ $key ]); 
    } 
}