理解扁平数据与树形结构转换
在许多应用场景中，数据通常以扁平化的形式存储，例如数据库中的分类、菜单或组织结构，它们通过一个 id 字段和一个 parentid 字段来表示父子关系。然而，为了更好地展示或操作这些数据，我们常常需要将其转换为具有层级关系的树形结构，其中每个父节点包含一个子节点数组（例如 pages）。
例如，我们可能拥有以下结构的数据：
$indexes = [
['id' => 1, 'parentid' => 0, 'route' => 'root', 'title' => 'root'],
['id' => 2, 'parentid' => 1, 'route' => 'parent', 'title' => 'parent'],
['id' => 3, 'parentid' => 2, 'route' => 'child', 'title' => 'child']
];我们期望将其转换为如下的嵌套结构：
$index = [
[
'id' => 1,
'pages' => [
[
'id' => 2,
'pages' => [
[
'id' => 3
]
]
]
]
]
];递归实现原理
递归是解决这类问题的强大工具。其核心思想是：一个函数调用自身来解决问题的子集，直到达到基本情况（即没有更多子节点）。
为了构建树形结构，我们可以定义一个递归函数，该函数接收整个扁平数组和当前需要查找的父节点ID。函数内部会遍历数组，找出所有直接子节点，然后对每个子节点递归调用自身，以查找它们的子节点。
立即学习“PHP免费学习笔记（深入）”；
初始代码分析与问题诊断
最初的尝试可能如下所示：
function buildSubs(array $elms, int $parentId = 0)
{
$branch = [];
foreach ($elms as $elm) {
if ($elm['parentid'] == $parentId) {
$children = buildSubs($elms, $elm['id']);
if ($children) {
// 错误：这里将 'pages' 键添加到了整个 $elms 数组，而不是当前的 $elm 元素
$elms['pages'] = $children;
}
$branch[] = $elm;
}
}
return $branch;
}上述代码存在一个关键错误：在找到子节点后，试图通过 $elms['pages'] = $children; 将子节点数组赋给 $elms。然而，$elms 是传入函数的整个原始数组的副本，而不是当前正在处理的 $elm 元素。这导致了子节点数组没有被正确地附加到其父元素上。
正确的做法是将子节点数组附加到当前循环中的 $elm 元素上，即 $elm['pages'] = $children;。
优化后的递归实现
修正上述错误并考虑起始父节点ID（通常根节点的 parentid 为0或null）后，我们可以得到一个功能完善的递归函数：
<?php
/**
* 将扁平数组转换为嵌套树形结构
*
* @param array $elements 包含 id 和 parentid 的扁平数据数组
* @param int $parentId 当前需要查找的父节点ID
* @return array 构建好的树形分支
*/
function buildTree(array $elements, int $parentId = 0): array
{
$branch = []; // 用于存储当前层级的节点
foreach ($elements as $element) {
if ($element['parentid'] == $parentId) {
// 递归查找当前元素的子节点
$children = buildTree($elements, $element['id']);
// 如果存在子节点，则将其添加到当前元素的 'pages' 键下
if (!empty($children)) {
$element['pages'] = $children; // 关键修正：将 'pages' 赋给当前 $element
}
// 将处理好的元素添加到当前层级的 $branch 中
$branch[] = $element;
}
}
return $branch;
}
// 示例数据
$data = [
['id' => 1, 'parentid' => 0, 'route' => 'root', 'title' => 'root'],
['id' => 2, 'parentid' => 1, 'route' => 'parent', 'title' => 'parent'],
['id' => 3, 'parentid' => 2, 'route' => 'child', 'title' => 'child'],
['id' => 4, 'parentid' => 1, 'route' => 'sibling', 'title' => 'sibling'], // 添加一个同级节点
['id' => 5, 'parentid' => 0, 'route' => 'another_root', 'title' => 'another_root'] // 添加另一个根节点
];
// 从 parentid = 0 开始构建整个树
$tree = buildTree($data, 0);
// 打印结果
echo "<pre>";
print_r($tree);
echo "</pre>";
?>运行结果示例
执行上述代码，将得到以下结构化的输出：
Array
(
[0] => Array
(
[id] => 1
[parentid] => 0
[route] => root
[title] => root
[pages] => Array
(
[0] => Array
(
[id] => 2
[parentid] => 1
[route] => parent
[title] => parent
[pages] => Array
(
[0] => Array
(
[id] => 3
[parentid] => 2
[route] => child
[title] => child
)
)
)
[1] => Array
(
[id] => 4
[parentid] => 1
[route] => sibling
[title] => sibling
)
)
)
[1] => Array
(
[id] => 5
[parentid] => 0
[route] => another_root
[title] => another_root
)
)可以看到，id 为 1 的元素包含了 id 为 2 和 4 的子元素，而 id 为 2 的元素又包含了 id 为 3 的子元素，完美地构建了所需的嵌套树形结构。
注意事项与优化建议
- 起始 parentId： 通常，根节点的 parentid 会被设置为 0、null 或一个特殊值。在调用 buildTree 函数时，应传入这个根节点的 parentid 来获取完整的树结构。
-
性能考虑： 对于非常庞大的数据集（例如数万条记录），这种纯递归方法可能会导致性能问题，因为每次递归调用都会遍历整个原始数组。在这种情况下，可以考虑以下优化：
- 预处理数据： 将数据转换为以 id 为键的关联数组，或者创建一个以 parentid 为键，值为子节点数组的映射表。这样在查找子节点时，可以直接通过键访问，避免重复遍历。
- 迭代方法： 对于极端情况，可以采用迭代而非递归的方式构建树，通常结合队列或栈来实现。
- 循环引用检测： 在某些复杂场景中，数据可能存在循环引用（A是B的父，B又是A的父）。纯递归方法可能会导致无限循环。在实际应用中，如果存在这种可能性，需要增加额外的逻辑来检测和处理循环。
- 内存消耗： 深度递归可能会消耗较多的内存，尤其是在PHP的默认配置下。如果树的深度非常大，可能需要调整PHP的 memory_limit 或 xdebug.max_nesting_level 配置。
- 数据完整性： 确保 id 和 parentid 字段的类型和值在整个数据集中保持一致。
总结
通过递归函数将扁平的父子关系数据转换为嵌套的树形结构是PHP开发中常见的需求。理解递归的工作原理，特别是正确处理当前元素属性的赋值，是实现这一功能的关键。虽然递归方法简洁优雅，但在处理大规模数据时，也需要考虑性能和内存消耗，并根据具体情况选择或优化实现方式。掌握这种技巧，将有助于你更灵活地处理和展示具有层级关系的数据。
