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

请注意，如果您输入的数据是不正确（如与父母无效值的项目会导致无限循环），这将严重错误。