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

請注意，如果您輸入的數據是不正確（如與父母無效值的項目會導致無限循環），這將嚴重錯誤。