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

请注意,如果输入数据不正确(例如,父项值无效的项将导致无限循环),则会出现严重错误.