PHP递归构建树形结构：扁平数据转层级展示

理解扁平数据与树形结构转换

在许多应用场景中，数据通常以扁平化的形式存储，例如数据库中的分类、菜单或组织结构，它们通过一个 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。函数内部会遍历数组，找出所有直接子节点，然后对每个子节点递归调用自身，以查找它们的子节点。

初始代码分析与问题诊断

最初的尝试可能如下所示：

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）后，我们可以得到一个功能完善的递归函数：

 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 "
";
print_r($tree);
echo "
";

?>

运行结果示例

执行上述代码，将得到以下结构化的输出：

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 的子元素，完美地构建了所需的嵌套树形结构。

注意事项与优化建议

1. 起始 parentId： 通常，根节点的 parentid 会被设置为 0、null 或一个特殊值。在调用 buildTree 函数时，应传入这个根节点的 parentid 来获取完整的树结构。
2. 性能考虑： 对于非常庞大的数据集（例如数万条记录），这种纯递归方法可能会导致性能问题，因为每次递归调用都会遍历整个原始数组。在这种情况下，可以考虑以下优化：
   • 预处理数据： 将数据转换为以 id 为键的关联数组，或者创建一个以 parentid 为键，值为子节点数组的映射表。这样在查找子节点时，可以直接通过键访问，避免重复遍历。
   • 迭代方法： 对于极端情况，可以采用迭代而非递归的方式构建树，通常结合队列或栈来实现。
3. 循环引用检测： 在某些复杂场景中，数据可能存在循环引用（A是B的父，B又是A的父）。纯递归方法可能会导致无限循环。在实际应用中，如果存在这种可能性，需要增加额外的逻辑来检测和处理循环。
4. 内存消耗： 深度递归可能会消耗较多的内存，尤其是在PHP的默认配置下。如果树的深度非常大，可能需要调整PHP的 memory_limit 或 xdebug.max_nesting_level 配置。
5. 数据完整性： 确保 id 和 parentid 字段的类型和值在整个数据集中保持一致。

总结

通过递归函数将扁平的父子关系数据转换为嵌套的树形结构是PHP开发中常见的需求。理解递归的工作原理，特别是正确处理当前元素属性的赋值，是实现这一功能的关键。虽然递归方法简洁优雅，但在处理大规模数据时，也需要考虑性能和内存消耗，并根据具体情况选择或优化实现方式。掌握这种技巧，将有助于你更灵活地处理和展示具有层级关系的数据。