PHP配列ツリーソート

Question

私は以下の配列を持っています。 IDに対応する親のIDを持っています。この配列をソートしてツリー配列に変換する関数を作成することができます。私の問題は、親が子供の後ろにいると、それが正しく動作しないことがあるということです。

どのように私は最初にソートする必要はありませんツリーに以下のような配列を有効にするでしょうか？

[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 
     ) 

私が正しく動作しません。この機能を持っている：

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; 
} 

ご注意：親がある場合（空）（= '';）それがルートであることを意味します。

Answer 1

このトリックは、ツリー内のすべてのノードへの参照を持つ一種のインデックス（以下、$allという名前）を保持することです。以下の例では、処理する必要があるノードを$danglingという配列に追加し、最後の出力を$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); 

は注意（例えば親のための無効な値を持つ項目が無限ループの原因になります）。