Реструктурировать массив по родительским / дочерним идентификаторам. Рекурсия?

Question

У меня есть массив локаций.У каждого из этих местоположений могут быть дочерние местоположения.Каждое из дочерних расположений также может иметь дочерние элементы и т. Д .:

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

Я хочу перестроить этот массив, чтобы дочерние элементы были массивами родительского.Примерно так (не проверено):

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

Это так, чтобы я мог затем распечатать их, используя такие отступы:

LOCATIONS

England
- East England
- London
-- West London
-- East London
- East Midlands
-- Derbyshire
Scotland
Ireland
Wales

Я пробовал несколько способов, например, группировать их по родителямID, но я просто не могу выработать логику для этого, и может быть лучший способ сделать это (рекурсия, возможно?).

Большое спасибо.

Answer 1

Привет, возможно, это поможет вам, я только что написал это, чтобы быстро преобразовать результат MySQL, содержащий parent_id, в пригодную для использования иерархию данных. Ваш входной массив также должен работать. Это просто пара строк с двумя основными циклами. Рекурсия не требуется. Некоторые комментарии включены:

<?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
?>

Обратите внимание на символы '& reference'. Они выполняют всю работу, позволяя строить дерево из плоского массива, указывая на одни и те же объекты.

Answer 2

См. отличный ответ от Билла Калвина .

А также его презентация «Модели для иерархических данных (PHP и SQL)»

Также вас может заинтересовать непосредственное хранение данных в виде структуры «вложенного набора» в вашей БД .