Algoritmo para crear una matriz multidimensional

Question

Estoy usando PHP y necesito ayuda con una tarea aparentemente simple con una matriz.

Este es mi ejemplo de matriz:

$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' 
); 

Las claves de la tabla representan los identificadores (único).
Los valores son parentIDs, es decir, el ID del "nodo" principal. NULL significa que no hay parentID (es decir, primera dimensión de la nueva matriz).

Ahora, necesito crear una matriz nueva y multidimensional que tenga todos los elementos secundarios debajo de sus ID principales. (Esto probablemente suene muy confuso, disculpe mi falta de habilidades descriptivas. Hay un ejemplo a continuación, que debería aclarar las cosas)

Así es como se vería la nueva matriz de mi ejemplo después de la función "ordenar", o lo que sea se llama a esto, se aplicó:

 
$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() 
) 
); 

Conozco todos los matriz vacía (s) probablemente no son una solución muy limpia y elegante, pero por desgracia, este es el camino que necesito que sea!

Answer 1

Esta función recursiva añadirá el dato dado a los padres correcta, y debe ser llamada una vez por cada elemento de la matriz de partida.

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; 

} 

Los comentarios son bastante detallados, con la esperanza de que pueda entender lo que está pasando. Te animo a que leas un poco sobre funciones recursivas para entenderlo.

Esta es la forma en que se utilizaría:

$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 ahora tiene la matriz de acabado correcto, tal como se indica en la pregunta.

Answer 2

Two pass foreach hace el truco. Esto vinculará a todos los niños con sus padres recursivamente.

//$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 ]); 
    } 
}