Tri de l'arbre du tableau php

Question

J'ai le tableau suivant. Il a un identifiant parent qui correspond à l'identifiant. Je parviens à créer une fonction pour trier et transformer ce tableau en un arbre. Mon problème est que parfois cela ne fonctionne pas correctement si le parent est après l'enfant.

Alors comment transformer un tableau comme celui ci-dessous en un arbre qui n'a pas besoin d'être trié en premier?

[0] => Array 
     (
      [menu] => 
      [parent] => 0 
      [id] => 1 
     ) 
    , 
    [1] => Array 
     (
      [menu] => 
      [parent] => 
      [id] => 2 
     ) 
    , 
    [2] => Array 
     (
      [menu] => 
      [parent] => 1 
      [id] => 3 
     ) 
    , 
    [3] => Array 
     (
      [menu] => 
      [parent] => 1 
      [id] => 4 
     ) 
    , 
    [4] => Array 
     (
      [menu] => 
      [parent] => 4 
      [id] => 5 
     ) 

J'ai cette fonction qui ne fonctionne pas correctement:

function page_tree($rows) { 
    if(!is_array($rows) || empty($rows)){ 
     return false; 
    } 
    // $rows = array(); //stores all the database rows that are to be converted into a tree 
    $tree = array(); //stores the tree 
    $tree_index = array(); //an array used to quickly find nodes in the tree 
    $id_column = "id"; //The column that contains the id of each node 
    $parent_column = "parent"; //The column that contains the id of each node's parent 
    $text_column = "title"; //The column to display when printing the tree to html 
    //build the tree - this will complete in a single pass if no parents are defined after children 
    // vp(count($rows));die(); 
    // while(count($rows) > 0){ 
    foreach($rows as $row_id => $row){ 
     $row_id = $row['id']; 
     if($row[$parent_column]){ 
      if((!array_key_exists($row[$parent_column], $rows)) and (!array_key_exists($row[$parent_column], $tree_index))){ 
       unset($rows[$row_id]); 
      } 
      else{ 
       if(array_key_exists($row[$parent_column], $tree_index)){ 
       $parent = & $tree_index[$row[$parent_column]]; 
       $parent['children'][$row_id] =$row; 
       $parent['children'][$row_id]["children"] = array(); 
       $tree_index[$row_id] = & $parent['children'][$row_id]; 
       unset($rows[$row_id]); 
       } 
      } 
     } 
     else{ 
      $tree[$row_id] = $row; 
      $tree[$row_id]["children"] = array(); 
      $tree_index[$row_id] = & $tree[$row_id]; 
      unset($rows[$row_id]); 
     } 
    } 
    // } 
    return $tree; 
} 

S'il vous plaît noter: lorsque le parent (vide) (= '';) cela signifie qu'il est la racine.

Answer 1

L'astuce consiste à conserver une sorte d'index (nommé $all ci-dessous) avec des références à tous les nœuds de l'arborescence. L'exemple ci-dessous va ajouter des nœuds qui doivent encore être traités dans un tableau nommé $dangling et ajouter la sortie finale au tableau $output.

<? 
// Test input 
$input = array(
array('menu' => 'A', 'parent' => 2, 'id' => 4), 
    array('menu' => 'B', 'parent' => 1, 'id' => 3), 
    array('menu' => 'C', 'parent' => 2, 'id' => 1), 
    array('menu' => 'D', 'parent' => '', 'id' => 2) 
); 

$output = array(); 
$all = array(); 
$dangling = array(); 

// Initialize arrays 
foreach ($input as $entry) { 
    $entry['children'] = array(); 
    $id = $entry['id']; 

    // If this is a top-level node, add it to the output immediately 
    if ($entry['parent'] == '') { 
     $all[$id] = $entry; 
     $output[] =& $all[$id]; 

    // If this isn't a top-level node, we have to process it later 
    } else { 
     $dangling[$id] = $entry; 
    } 
} 

// Process all 'dangling' nodes 
while (count($dangling) > 0) { 
    foreach($dangling as $entry) { 
     $id = $entry['id']; 
     $pid = $entry['parent']; 

     // If the parent has already been added to the output, it's 
     // safe to add this node too 
     if (isset($all[$pid])) { 
      $all[$id] = $entry; 
      $all[$pid]['children'][] =& $all[$id]; 
      unset($dangling[$entry['id']]); 
     } 
    } 
} 

print_r($output); 

Notez que cela détraquer si vos données d'entrée est incorrecte (par exemple un élément avec une valeur non valide pour le parent provoque une boucle infinie).