利用PHP递归构建树形数据结构教程-php教程-PHP中文网

利用PHP递归构建树形数据结构教程

霞舞

发布： 2025-07-22 14:26:23

原创

650人浏览过

利用PHP递归构建树形数据结构教程

本文详细介绍了如何使用PHP递归函数将扁平化的父子关系数组转换为嵌套的树形结构。通过分析常见错误并提供修正后的代码示例，本教程旨在帮助开发者高效地处理层级数据，实现如菜单、分类或评论回复等场景的动态生成和展示。

1. 理解树形数据结构及其应用场景

在web开发中，我们经常需要处理具有层级关系的数据，例如网站导航菜单、商品分类、组织架构图或评论回复列表。这类数据通常存储在数据库中，以扁平化的形式呈现，即每条记录包含一个 id 和一个 parentid 来标识其父子关系。然而，为了更好地展示或操作这些数据，我们往往需要将其转换为嵌套的、树形的结构。

例如，我们有以下扁平化的数据数组，它描述了一个简单的层级关系：

$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']
];

登录后复制

我们的目标是将其转换为如下所示的嵌套结构，其中子元素被封装在父元素的 pages 数组中：

$index=[
  [
    'id'=>1,
    'pages' => [
       [
         'id'=>2,
         'pages' => [
          [
            'id'=>3
          ]
     ]
];

登录后复制

2. 递归构建树形结构的核心思想

递归是一种强大的编程技术，它允许函数调用自身来解决问题。在构建树形结构时，递归的核心思想是：

查找直接子元素： 对于给定父ID，遍历所有元素，找出直接以该父ID为 parentid 的子元素。
递归处理子元素： 对于每个找到的子元素，以其自身的 id 作为新的父ID，再次调用函数，查找其下属的子元素。
构建层级： 将递归调用返回的子元素集合添加到当前元素的特定键（例如 pages）下。

3. 常见错误分析与修正

在尝试实现上述逻辑时，开发者可能会遇到一些常见的错误。以下是原始代码片段及其存在的问题：

立即学习“PHP免费学习笔记（深入）”；

function buildSubs(array $elms, int $parentId = 0)
{
    $branch = [];
    foreach ($elms as $elm) {
        if ($elm['parentid'] == $parentId) {
            $children = buildSubs($elms, $elm['id']);
            if ($children) {
                // 错误点1：这里应该是 $elm['pages'] = $children; 而不是 $elms['pages']
                $elms['pages'] = $children; 
            }
            $branch[] = $elm;
        }
    }
    return $branch;
}

// 错误点2：如果想构建完整的树，初始 $parentId 应该从根节点（通常是0）开始
$parentid = 1; 
$indexes = buildSubs($indexes, $parentid);
var_dump($indexes);

登录后复制

错误分析：

PHP与MySQL程序设计3

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。本书内容全面深入，适合各层次PHP和MySQL开发人员阅读，既是优秀的学习教程，也可用作参考手册。

253

查看详情

变量引用错误： 在 if ($children) 块中， $elms['pages'] = $children; 试图修改传入函数的整个 $elms 数组，而不是当前正在处理的单个元素 $elm。这导致子节点未能正确附加到其父节点上。
初始父ID选择： 如果目标是构建整个树形结构（从根节点开始），那么首次调用 buildSubs 时，$parentId 应该设置为根节点的 parentid，通常是 0。如果设置为 1，则只会构建以 id=1 为根的子树。

4. 正确的递归实现

根据上述分析，我们对 buildSubs 函数进行修正，并展示如何正确调用以构建完整的树形结构：

<?php

function buildSubs(array $elms, int $parentId = 0): array
{
    $branch = []; // 用于存储当前层级的子元素
    foreach ($elms as $key => $elm) {
        // 检查当前元素的 parentid 是否与传入的 parentId 匹配
        if ($elm['parentid'] == $parentId) {
            // 找到直接子元素后，递归调用 buildSubs 查找其子级
            // 注意：这里传入的是完整的 $elms 数组，以便在所有元素中查找
            $children = buildSubs($elms, $elm['id']);

            // 如果当前元素有子级，将其添加到当前元素的 'pages' 键下
            if ($children) {
                $elm['pages'] = $children;
            }
            // 将处理后的当前元素添加到当前层级的 $branch 数组中
            $branch[] = $elm;
            // 可选：如果元素处理后不再需要，可以从 $elms 中移除以优化性能（对于非常大的数据集）
            // unset($elms[$key]); 
        }
    }
    return $branch; // 返回当前层级的元素集合
}

// 原始扁平化数据
$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']
];

// 调用函数构建完整的树形结构，从 parentid 为 0 的根节点开始
$fullTree = buildSubs($indexes, 0);

// 输出结果
echo '<pre>';
var_dump($fullTree);
echo '</pre>';

?>

登录后复制

代码解析：

buildSubs(array $elms, int $parentId = 0): array：函数接受完整的扁平化数组 $elms 和当前要查找的父ID $parentId。默认 $parentId 为 0，方便从根节点开始构建。
$branch = [];：初始化一个空数组，用于收集当前 $parentId 下的所有直接子元素。
foreach ($elms as $key => $elm)：遍历所有元素。
if ($elm['parentid'] == $parentId)：判断当前元素是否是 $parentId 的直接子元素。
$children = buildSubs($elms, $elm['id']);：递归调用。如果当前元素是直接子元素，就以它的 id 作为新的 $parentId，再次调用 buildSubs 来查找它的所有子孙。
if ($children) { $elm['pages'] = $children; }：如果递归调用返回了子元素（即 $children 不为空），则将这些子元素赋值给当前元素的 pages 键。这是关键修正点，确保子元素被正确地附加到其父元素内部。
$branch[] = $elm;：将处理完毕（可能已包含 pages 键）的当前元素添加到 $branch 数组中。
return $branch;：返回当前层级的所有已处理元素。

预期输出：

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
                                        )

                                )

                        )

                )

        )

)

登录后复制

这个输出正是我们期望的完整树形结构。

5. 注意事项与优化

性能考量： 对于非常大的数据集（例如数万条记录），每次递归调用都遍历整个 $elms 数组可能会导致性能问题。在这种情况下，可以考虑以下优化：
- 预处理为哈希表： 在递归开始前，将 $elms 数组转换为以 id 为键的哈希表（或关联数组），这样可以通过 id 直接访问元素，避免重复遍历。
- 传递引用： 如果在递归过程中需要修改原始数组（例如，将已处理的元素从 $elms 中移除以减少后续遍历的范围），可以将 $elms 作为引用传递给函数。
- 迭代法： 对于极端大数据量，非递归的迭代方法（如广度优先搜索或深度优先搜索）可能更优，但实现复杂度通常更高。
内存消耗： 深度递归可能会消耗较多的栈内存。PHP的默认递归深度限制通常足以应对大多数情况，但如果层级非常深，可能需要调整 php.ini 中的 xdebug.max_nesting_level（开发环境）或考虑非递归方案。
灵活性：
- 根节点处理： 确保你的数据中有一个明确的根节点（例如 parentid = 0 或 null）以便于从顶部开始构建。
- 子节点键名： 可以根据需求修改存储子节点的键名，例如 children、sub_items 等，只需修改 if ($children) { $elm['pages'] = $children; } 中的 pages 即可。
- 返回数据： 如果你只需要树中特定字段（如 id 和 pages），可以在递归函数中过滤掉其他字段，或者在函数外部对结果进行后处理。

总结

通过本教程，我们学习了如何利用PHP的递归功能，将扁平化的父子关系数组转换为易于处理和展示的嵌套树形结构。理解递归的核心思想、识别并修正常见错误是掌握这一技术的关键。在实际应用中，根据数据规模和性能要求，可以进一步考虑优化策略，以构建高效、健壮的层级数据处理方案。

以上就是利用PHP递归构建树形数据结构教程的详细内容，更多请关注php中文网其它相关文章！