如何从扁平数组中高效提取具有上下级关系的树形子集-php教程-PHP中文网

如何从扁平数组中高效提取具有上下级关系的树形子集

本文介绍一种无副作用、可重入的 php 方法，用于根据指定父节点 id 从扁平结构数组中递归提取所有直接与间接子项（含自身），解决静态变量污染和多调用栈叠加问题。

本文介绍一种无副作用、可重入的 php 方法，用于根据指定父节点 id 从扁平结构数组中递归提取所有直接与间接子项（含自身），解决静态变量污染和多调用栈叠加问题。

在构建分类系统、菜单导航或组织架构等场景中，常需将扁平化的层级数据（如数据库查询结果）按需转换为子树结构。典型输入是一个包含 id 和 parent 字段的关联数组集合，其中 parent 表示其直接上级 ID（根节点通常为 0 或 null）。若采用带静态变量的递归方法，多次调用会导致结果累积、状态污染，破坏函数的纯性与线程/请求安全性。

正确的实现应满足：✅ 无全局或静态状态依赖；✅ 每次调用独立隔离；✅ 支持任意深度嵌套；✅ 时间复杂度可控（推荐预建索引优化）。

以下为推荐的非递归 + 索引加速实现（兼容 PHP 7.0+）：

public static function getAllChildren(array $categories, int $parent_id): array
{
    // Step 1: 构建 id → category 的哈希映射，O(n) 预处理
    $index = [];
    foreach ($categories as $item) {
        $index[$item['id']] = $item;
    }

    // Step 2: 使用栈模拟深度优先遍历（避免递归调用栈溢出）
    $result = [];
    $stack = [$parent_id];

    while (!empty($stack)) {
        $currentId = array_pop($stack);

        // 若当前 ID 存在于原始数据中，则加入结果并扩展子节点
        if (isset($index[$currentId])) {
            $result[] = $index[$currentId];
            // 扫描全量数组找子节点（适合小规模）或改用 parent-index（见下方优化）
            foreach ($categories as $item) {
                if ($item['parent'] === $currentId) {
                    $stack[] = $item['id'];
                }
            }
        }
    }

    return $result;
}

⚠️ 注意：上述基础版时间复杂度为 O(n × d)，d 为平均深度。对大数据集建议进一步优化——构建 parent → [children] 双向索引：

// 预先构建一次（例如在类初始化或服务容器中）
$parentIndex = [];
foreach ($categories as $item) {
    $parentIndex[$item['parent']][] = $item['id'];
}

// 调用时传入该索引，将内层循环降至 O(1) 均摊：
public static function getAllChildrenWithIndex(
    array $categories,
    array $parentIndex,
    int $parent_id
): array {
    $index = array_column($categories, null, 'id'); // id => item
    $result = [];
    $stack = [$parent_id];

    while (!empty($stack)) {
        $id = array_pop($stack);
        if (isset($index[$id])) {
            $result[] = $index[$id];
            // 快速获取所有子 ID
            if (isset($parentIndex[$id])) {
                foreach ($parentIndex[$id] as $childId) {
                    $stack[] = $childId;
                }
            }
        }
    }

    return $result;
}

? 关键总结：