Recursively creating a multi-dimensional array in PHP

Question

I am trying to figure out the best way to write a PHP function that will recursively build a multi-dimensional array with an unknown number of sublevels from a mysql table. Its purpose is to create a data structure which can be looped through to create a navigation menu on a website, with each menu item possibly having a submenu with child menu items.

The fields of note in the table are:
int ItemID
int ParentID
varchar ItemText
text ItemLink
tinyint HasChildren

So an example of a returned array from the function would be:

$menuItems = 
    array(
        itemID# => 
            array(
                'ItemText' => 'Home',
                'ItemLink' => 'index.php',
                'Children' => array(
                        itemID# => array (
                            'ItemText' => 'Home Sub 1',
                            'ItemLink' => 'somepage.php',
                            'Children' => 0
                        ),
                        itemID# => array (
                            'ItemText' => 'Home Sub 2',
                            'ItemLink' => 'somepage2.php',
                            'Children' => 0
                        ),
                    )
            ),
        itemID# => 
            array(
                'ItemText' => 'Contact',
                'ItemLink' => 'contact.php',
                'Children' => 0
            )
        )
    );

Would greatly appreciate if someone could point me in the right direction to accomplish this. Thanks!

Answer 1

Not too hard. What you do is store the menu items in an array where you can look them up by ID. Then you iterate over the menu items and if they have a non-null ParentID you add them to their parent's list of children. Then you remove all the children from the master list so you have only top-level items left.

Code:

<?php
$menuItems = array
(
    1 => array
    (
        'ItemText' => 'Home',
        'ItemLink' => 'index.php',
        'ParentID' => null,
    ),

    2 => array
    (
        'ItemText' => 'Home Sub 1',
        'ItemLink' => 'somepage.php',
        'ParentID' => 1,
    ),

    3 => array
    (
        'ItemText' => 'Home Sub 2',
        'ItemLink' => 'somepage2.php',
        'ParentID' => 1,
    ),

    4 => array
    (
        'ItemText' => 'Contact',
        'ItemLink' => 'contact.php',
        'ParentID' => null,
    ),
);

// Each node starts with 0 children
foreach ($menuItems as &$menuItem)
    $menuItem['Children'] = array();

// If menu item has ParentID, add it to parent's Children array    
foreach ($menuItems as $ID => &$menuItem)
{
    if ($menuItem['ParentID'] != null)
        $menuItems[$menuItem['ParentID']]['Children'][$ID] = &$menuItem;
}

// Remove children from $menuItems so only top level items remain
foreach (array_keys($menuItems) as $ID)
{
    if ($menuItems[$ID]['ParentID'] != null)
        unset($menuItems[$ID]);
}

print_r($menuItems);
?>

Output:

Array
(
    [1] => Array
        (
            [ItemText] => Home
            [ItemLink] => index.php
            [ParentID] => 
            [Children] => Array
                (
                    [2] => Array
                        (
                            [ItemText] => Home Sub 1
                            [ItemLink] => somepage.php
                            [ParentID] => 1
                            [Children] => Array
                                (
                                )

                        )

                    [3] => Array
                        (
                            [ItemText] => Home Sub 2
                            [ItemLink] => somepage2.php
                            [ParentID] => 1
                            [Children] => Array
                                (
                                )

                        )

                )

        )

    [4] => Array
        (
            [ItemText] => Contact
            [ItemLink] => contact.php
            [ParentID] => 
            [Children] => Array
                (
                )

        )

)

Answer 2

Have a function that calls itself every time it gets an array element. As in:

Your function is called to display a node. Then it checks if the node its calling from has a sub menu, and if does, it calls itself again. And the process repeats until it dies out, and all the previous function calls return.

void printData($mysql_table_node){
    if($mysql_table_node.has_node()){
        for($i = 0; $i < $mysqql_table_node.num_nodes()){
            printData($mysql_table_node->own_node);
        }
    }
        return;
}