php array tree sorting

Question

I have the following array. It has a parent id that correspond with the id. I manage to create a function to sort and turn this array into a tree array. My problem stands that sometimes it does not work properly if the parent is after the child.

So how would I turn an array like the one below to a tree that doesn't need to be sorted first?

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

I have this function which does not work properly:

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

Please note: where parent is (empty) (='';) it means it's the root.

Quick question: why in your example is $rows[0][parent] == 0? — Zecc
– Zecc, Commented Nov 26, 2010 at 11:09
And a quick suggestion: ignoring the fact you may want your code to be more robust, you can assume your flat hierarchy will come in order if in your database you use a powerful technique called the Nested Set Model. See dev.mysql.com/tech-resources/articles/hierarchical-data.html (scroll down until you see Nested Set Model) — Zecc
– Zecc, Commented Nov 26, 2010 at 11:32
Never mind. I was assuming the indexes on the array corresponded to the ids of the nodes. — Zecc
– Zecc, Commented Nov 26, 2010 at 11:33
@Zecc Nested Set Model adds complexity and may be overkill if you are always retrieving the full set. — John
– John, Commented Nov 26, 2010 at 11:52

John · Accepted Answer · 2010-11-26 12:13:36Z

9

The trick is to keep a kind of index (named $all below) with references to all nodes in the tree. The example below will add nodes that still need to be processed to an array named $dangling and add the final output to the $output array.

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

Note that this will go horribly wrong if your input data is incorrect (e.g. an item with an invalid value for parent will cause an infinite loop).

edited Nov 26, 2010 at 12:13

answered Nov 26, 2010 at 11:44

John

6913 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Val Over a year ago

thanks john.. . this sounds good however I have hit that infinite loop thing :(

Val Over a year ago

found the problem it seems that parent id 0 (zero) should should be (null) so it's top level(root) node.

Val Over a year ago

I have also tested it re sorting in different ways and it still works nicely so thnx again :)

Matt Fletcher · Accepted Answer · 2020-01-17 09:35:53Z

0

I have found the package https://github.com/BlueM/Tree to be perfect for handling this sort of tree structure.

answered Jan 17, 2020 at 9:35

Matt Fletcher

3553 silver badges15 bronze badges

1 Comment

user2420206 Over a year ago

I discovered this library because of your answer, and it solved my sorting blues like mellow jazz music. Its a shame it only has 200 stars on github

Collectives™ on Stack Overflow

php array tree sorting

2 Answers 2

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related