Algorithme de création de tableau multidimensionnel

Question

J'utilise PHP et j'ai besoin d'aide pour une tâche apparemment simple avec un tableau.

Ceci est mon tableau par exemple:

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

Les clés du tableau représentent les ID (unique).
Les valeurs sont parentID, c'est-à-dire l'ID du "nœud" parent. NULL signifie qu'il n'y a aucun parentID (c'est-à-dire 1ère dimension du nouveau tableau).

Maintenant, j'ai besoin de créer un nouveau tableau multi-dimensionnel qui a tous les éléments enfants sous leurs ID parents. (Cela semble probablement très déroutant, désolé pour mon manque de capacités descriptives.Il y a un exemple ci-dessous, qui devrait rendre les choses plus claires)

Voici à quoi ressemblerait le nouveau tableau de mon exemple après la fonction de "tri", ou peu importe vous appelez cela, a été appliqué:

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

Je connais tous les s de tableau vide() ne sont probablement pas une solution très propre et élégante, mais malheureusement, c'est la façon dont je besoin d'être!

Answer 1

Cette fonction récursive ajoutera la donnée donnée au parent correcte et doit être appelé une fois pour chaque élément dans votre tableau de départ.

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; 

} 

Les commentaires sont assez verbeux, dans l'espoir que vous puissiez comprendre ce qui se passe. Je vous encourage à faire un peu de lecture sur les fonctions récursives pour comprendre.

Voici comment cela serait utilisé:

$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 a maintenant le tableau de finition correcte, comme il est indiqué dans la question.

Answer 2

Deux passes foreach font l'affaire. Ceci reliera tous les enfants à leurs parents de manière récursive.

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