Restructure array by parent/child IDs. Recursion?

I have an array of locations. Each of these locations can have child locations. Each of the child locations can also have children, and so on:

$locations = array(
    array("id" => 1,  "parent_id" => 0, "name" => "England"),
    array("id" => 2,  "parent_id" => 0, "name" => "Scotland"),
    array("id" => 3,  "parent_id" => 0, "name" => "Ireland"),
    array("id" => 4,  "parent_id" => 0, "name" => "Wales"),
    array("id" => 5,  "parent_id" => 1, "name" => "East England"),
    array("id" => 6,  "parent_id" => 1, "name" => "London"),
    array("id" => 7,  "parent_id" => 6, "name" => "West London"),
    array("id" => 8,  "parent_id" => 6, "name" => "East London"),
    array("id" => 9,  "parent_id" => 1, "name" => "East Midlands"),
    array("id" => 10, "parent_id" => 9, "name" => "Derbyshire")
);

I want to re-structure this array so that the children are arrays of the parent. Something like this (untested):

$locations =    array("id" => 1, "parent_id" => 0, "name" => "England", "children" => array(
                    array("id" => 5,  "parent_id" => 1, "name" => "East England"),
                    array("id" => 6,  "parent_id" => 1, "name" => "London", "children" => array(
                            array("id" => 7,  "parent_id" => 6, "name" => "West London"),
                            array("id" => 8,  "parent_id" => 6, "name" => "East London")))));

This is so I can then print them out using indents like so:

LOCATIONS

England
- East England
- London
-- West London开发者_开发技巧
-- East London
- East Midlands
-- Derbyshire
Scotland
Ireland
Wales

I have tried several ways, like grouping them by parent ID, but I just can't work out the logic for this, and there may be a better way of doing it (recursion, perhaps?).

Many thanks.

Hi perhaps this will help you, i just wrote it to quickly convert a mysql result containing a parent_id into a usable data hierarchy. Your input array should also work. It's just a couple of lines with two basic loops. No recursion required. Some comments included:

<?php

$max = count($inputArray);
$tree = array();
$flat = array();
// Create a flat hierarchy array of all entries by their id
for ($i = 0; $i < $max; $i++) {
        $n = $inputArray[$i];
        $id = $n['page_id'];
        $flat[$id] = $n;
}
// Then check all those entries by reference
foreach ($flat as $key => &$child) {
        // Add a children array if not already existing
        if (!isset($child['children']))
                $child['children'] = array();

        $id = $child['page_id'];
        $pid = $child['parent_id'];

        // If childs parent id is larger then zero
        if ($pid > 0) {
                // Append it by reference, which means it will reference
                // the same object across different carriers
                $flat[$pid]['children'][] = &$child;
        } else {
                // Otherwise it is zero level, which initiates the tree
                $tree[$id] = &$child;
        }
}

$tree = array_values($tree); // Indices fixed, there we go, use $tree further
?>

So notice the by '& reference' characters. They do all the work allowing the tree to be built from the flat array by pointing to the same objects.

See this excellent anwser from Bill Kalwin.

As well as his presentation on "Models for hierarchical data (PHP and SQL)"

Also, you may be interested in storing directly data as a "nested set" structure in your DB.