Рекурсивная функция для генерации многомерного массива из результата базы данных
Я ищу написать функцию, которая берет массив страниц / категорий (из простого результата базы данных) и генерирует массив вложенных элементов страницы / категории на основе родительских идентификаторов. Я хотел бы сделать это рекурсивно, чтобы можно было выполнить любой уровень вложенности.
Например: я выбираю все страницы в одном запросе, и вот так выглядит таблица базы данных.
+-------+---------------+---------------------------+
| id | parent_id | title |
+-------+---------------+---------------------------+
| 1 | 0 | Parent Page |
| 2 | 1 | Sub Page |
| 3 | 2 | Sub Sub Page |
| 4 | 0 | Another Parent Page |
+-------+---------------+---------------------------+
И этот массив я хотел бы обработать в моих файлах вида:
Array
(
[0] => Array
(
[id] => 1
[parent_id] => 0
[title] => Parent Page
[children] => Array
(
[0] => Array
(
[id] => 2
[parent_id] => 1
[title] => Sub Page
[children] => Array
(
[0] => Array
(
[id] => 3
[parent_id] => 1
[title] => Sub Sub Page
)
)
)
)
)
[1] => Array
(
[id] => 4
[parent_id] => 0
[title] => Another Parent Page
)
)
Я посмотрел и попробовал почти все решения, с которыми мне приходилось сталкиваться (их много здесь, в Stack Overflow, но не повезло, получив что-то достаточно общее, которое будет работать как для страниц, так и для категорий.
Вот самое близкое, что я получил, но это не работает, потому что я назначаю детей родителю первого уровня.
function page_walk($array, $parent_id = FALSE)
{
$organized_pages = array();
$children = array();
foreach($array as $index => $page)
{
if ( $page['parent_id'] == 0) // No, just spit it out and you're done
{
$organized_pages[$index] = $page;
}
else // If it does,
{
$organized_pages[$parent_id]['children'][$page['id']] = $this->page_walk($page, $parent_id);
}
}
return $organized_pages;
}
function page_list($array)
{
$fakepages = array();
$fakepages[0] = array('id' => 1, 'parent_id' => 0, 'title' => 'Parent Page');
$fakepages[1] = array('id' => 2, 'parent_id' => 1, 'title' => 'Sub Page');
$fakepages[2] = array('id' => 3, 'parent_id' => 2, 'title' => 'Sub Sub Page');
$fakepages[3] = array('id' => 4, 'parent_id' => 3, 'title' => 'Another Parent Page');
$pages = $this->page_walk($fakepages, 0);
print_r($pages);
}
5 ответов
Некоторое очень простое, общее построение дерева:
function buildTree(array $elements, $parentId = 0) {
$branch = array();
foreach ($elements as $element) {
if ($element['parent_id'] == $parentId) {
$children = buildTree($elements, $element['id']);
if ($children) {
$element['children'] = $children;
}
$branch[] = $element;
}
}
return $branch;
}
$tree = buildTree($rows);
Алгоритм довольно прост:
- Возьмите массив всех элементов и идентификатор текущего родителя (изначально
0/ничего такого/null/без разницы). - Перебрать все элементы.
- Если
parent_idэлемента соответствует текущему родительскому идентификатору, который вы получили в 1., элемент является дочерним по отношению к родительскому элементу. Поместите это в свой список текущих детей (здесь:$branch). - Вызовите функцию рекурсивно с идентификатором элемента, который вы только что определили в 3., т.е. найдите всех потомков этого элемента и добавьте их как
childrenэлемент. - Верните список найденных детей.
Другими словами, одно выполнение этой функции возвращает список элементов, которые являются потомками данного родительского идентификатора. Позвони с buildTree($myArray, 1), он вернет список элементов, имеющих родительский идентификатор 1. Первоначально эта функция вызывается с родительским идентификатором, равным 0, поэтому возвращаются элементы без родительского идентификатора, которые являются корневыми узлами. Функция вызывает себя рекурсивно, чтобы найти детей детей.
Я знаю, что этот вопрос старый, но я столкнулся с очень похожей проблемой - за исключением очень большого количества данных. После некоторой борьбы мне удалось построить дерево за один проход набора результатов - используя ссылки. Этот код не очень красивый, но он работает и работает довольно быстро. Это нерекурсивно - то есть только один проход через набор результатов и затем один array_filter в конце:
$dbh = new PDO(CONNECT_STRING, USERNAME, PASSWORD);
$dbs = $dbh->query("SELECT n_id, n_parent_id from test_table order by n_parent_id, n_id");
$elems = array();
while(($row = $dbs->fetch(PDO::FETCH_ASSOC)) !== FALSE) {
$row['children'] = array();
$vn = "row" . $row['n_id'];
${$vn} = $row;
if(!is_null($row['n_parent_id'])) {
$vp = "parent" . $row['n_parent_id'];
if(isset($data[$row['n_parent_id']])) {
${$vp} = $data[$row['n_parent_id']];
}
else {
${$vp} = array('n_id' => $row['n_parent_id'], 'n_parent_id' => null, 'children' => array());
$data[$row['n_parent_id']] = &${$vp};
}
${$vp}['children'][] = &${$vn};
$data[$row['n_parent_id']] = ${$vp};
}
$data[$row['n_id']] = &${$vn};
}
$dbs->closeCursor();
$result = array_filter($data, function($elem) { return is_null($elem['n_parent_id']); });
print_r($result);
Когда выполняется по этим данным:
mysql> select * from test_table;
+------+-------------+
| n_id | n_parent_id |
+------+-------------+
| 1 | NULL |
| 2 | NULL |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
| 7 | 5 |
| 8 | 5 |
+------+-------------+
Последний print_r производит этот вывод:
Array
(
[1] => Array
(
[n_id] => 1
[n_parent_id] =>
[children] => Array
(
[3] => Array
(
[n_id] => 3
[n_parent_id] => 1
[children] => Array
(
)
)
[4] => Array
(
[n_id] => 4
[n_parent_id] => 1
[children] => Array
(
)
)
)
)
[2] => Array
(
[n_id] => 2
[n_parent_id] =>
[children] => Array
(
[5] => Array
(
[n_id] => 5
[n_parent_id] => 2
[children] => Array
(
[7] => Array
(
[n_id] => 7
[n_parent_id] => 5
[children] => Array
(
)
)
[8] => Array
(
[n_id] => 8
[n_parent_id] => 5
[children] => Array
(
)
)
)
)
[6] => Array
(
[n_id] => 6
[n_parent_id] => 2
[children] => Array
(
)
)
)
)
)
Что именно то, что я искал.
public function testTree(){
$array = [
['id'=>7,'parent_id'=>3],
['id'=>1,'parent_id'=>0],
['id'=>2,'parent_id'=>0],
['id'=>3,'parent_id'=>1],
['id'=>4,'parent_id'=>1],
['id'=>5,'parent_id'=>2],
['id'=>6,'parent_id'=>1],
['id'=>8,'parent_id'=>4],
['id'=>9,'parent_id'=>4],
['id'=>10,'parent_id'=>0]
];
$res = $this->buildTree($array);
print_r($res);
}
public function buildTree($array,$id_key = 'id',$parent_key = 'parent_id'){
$res = [];
foreach($array as $y){
$array_with_id[$y[$id_key]] = $y;
}
foreach($array_with_id as $key => $element){
if($element[$parent_key]){
$array_with_id[$element[$parent_key]]['childrens'][$key] = &$array_with_id[$key];
}else{
$res[$element[$id_key]] = &$array_with_id[$key];
}
}
return $res;
}
Слишком много операций выполняется с помощью рекурсии, я думаю, что это лучший способ.
Вдохновленный другими ответами здесь, я придумал свою собственную версию для рекурсивной группировки массива связанных массивов (на любую произвольную глубину) с использованием списка настраиваемых функций для получения ключей группировки на каждом уровне.
Вот упрощенная версия более сложного исходного варианта(с большим количеством параметров для настройки ручек). Обратите внимание, что он использует простую итеративную функцию
groupByFn как подпрограмму для выполнения группировки на отдельных уровнях.
/**
* - Groups a (non-associative) array items recursively, essentially converting it into a nested
* tree or JSON like structure. Inspiration taken from: https://stackru.com/a/8587437/3679900
* OR
* - Converts an (non-associative) array of items into a multi-dimensional array by using series
* of callables $key_retrievers and recursion
*
* - This function is an extension to above 'groupByFn', which also groups array but only till 1 (depth) level
* (whereas this one does it till any number of depth levels by using recursion)
* - Check unit-tests to understand further
* @param array $data Array[mixed] (non-associative) array of items that has to be grouped / converted to
* multi-dimensional array
* @param array $key_retrievers Array[Callable[[mixed], int|string]]
* - A list of functions applied to item one-by-one, to determine which
* (key) bucket an item goes into at different levels
* OR
* - A list of callables each of which takes an item or input array as input and returns an int
* or string which is to be used as a (grouping) key for generating multi-dimensional array.
* @return array A nested assoc-array / multi-dimensional array generated by 'grouping' items of
* input $data array at different levels by application of $key_retrievers on them (one-by-one)
*/
public static function groupByFnRecursive(
array $data,
array $key_retrievers
): array {
// in following expression we are checking for array-length = 0 (and not nullability)
// why empty is better than count($arr) == 0 https://stackru.com/a/2216159/3679900
if (empty($data)) {
// edge-case: if the input $data array is empty, return it unmodified (no need to check for other args)
return $data;
// in following expression we are checking for array-length = 0 (and not nullability)
// why empty is better than count($arr) == 0 https://stackru.com/a/2216159/3679900
} elseif (empty($key_retrievers)) {
// base-case of recursion: when all 'grouping' / 'nesting' into multi-dimensional array has been done,
return $data;
} else {
// group the array by 1st key_retriever
$grouped_data = self::groupByFn($data, $key_retrievers[0]);
// remove 1st key_retriever from list
array_shift($key_retrievers);
// and then recurse into further levels
// note that here we are able to use array_map (and need not use array_walk) because array_map can preserve
// keys as told here:
// https://www.php.net/manual/en/function.array-map.php#refsect1-function.array-map-returnvalues
return array_map(
static function (array $item) use ($key_retrievers): array {
return self::groupByFnRecursive($item, $key_retrievers);
},
$grouped_data
);
}
}
Проверьте суть для большей коллекции вспомогательных функций массива вместе с модульными тестами
Можно использовать php, чтобы получить результат mysql в массив, а затем использовать его.
$categoryArr = Array();
while($categoryRow = mysql_fetch_array($category_query_result)){
$categoryArr[] = array('parentid'=>$categoryRow['parent_id'],
'id'=>$categoryRow['id']);
}