本文介绍一种高效构建无限层级树形数组的方法：通过建立页面映射表与引用关系表，将扁平化父子数组递归组装为嵌套结构，支持任意深度的子节点挂载。
本文介绍一种高效构建无限层级树形数组的方法：通过建立页面映射表与引用关系表，将扁平化父子数组递归组装为嵌套结构，支持任意深度的子节点挂载。
在实际开发中（如菜单系统、站点导航、分类目录等），我们常需将多个扁平数组按父子关系（referer 字段）组装成一棵逻辑清晰的树。由于嵌套深度不可预知，简单的一层循环无法满足需求；而递归虽直观，但易引发性能与栈溢出问题。本文提供一种非递归、时间复杂度近似 O(n) 的映射组装法，兼顾可读性与扩展性。
核心思路：两步映射 + 一次挂载
-
构建
page → node映射表：为所有子节点（$array2）建立以page为键的快速查找表，并统一初始化'childs' => []； -
逐层向上归并：遍历该映射表，若某节点的
referer在表中存在，则将其作为子节点挂入对应父节点的childs数组，并从顶层候选集中移除——这一步自动完成多级嵌套（如666.ru→66.ru→6.ru）； -
按根节点聚合子树：将剩余未被挂载的节点（即最终的叶子或中间节点）按
referer分组，形成referer → [node, ...]映射； -
注入一级父数组：遍历原始
$array1，对每个根节点，查找其page对应的子树列表并合并至childs。
完整实现代码
<?php $array1 = [
['page' => '1.ru', 'title' => '—', 'childs' => []],
['page' => '3.ru', 'title' => '—', 'childs' => []],
['page' => '6.ru', 'title' => '—', 'childs' => []]
];
$array2 = [
['page' => '666.ru', 'title' => '+', 'referer' => '66.ru'],
['page' => '33.ru', 'title' => '+', 'referer' => '3.ru'],
['page' => '66.ru', 'title' => '+', 'referer' => '6.ru']
];
// Step 1: 构建 page → node 映射，统一初始化 childs
$childPageMap = [];
foreach ($array2 as $row) {
$row['childs'] = [];
$childPageMap[$row['page']] = $row;
}
// Step 2: 自底向上归并：将子节点挂入其 referer 指向的父节点（支持多层嵌套）
foreach ($childPageMap as $page => $row) {
$parentPage = $row['referer'];
if (isset($childPageMap[$parentPage])) {
// 注意：此处使用 []= 追加，而非 = 覆盖，避免同父多子时丢失
$childPageMap[$parentPage]['childs'][] = $row;
unset($childPageMap[$page]); // 移除已挂载节点，保留根级子树
}
}
// Step 3: 按 referer 分组剩余节点（即所有未被上挂的“子树根”）
$childRefererMap = [];
foreach ($childPageMap as $row) {
$referer = $row['referer'] ?? '';
if (!isset($childRefererMap[$referer])) {
$childRefererMap[$referer] = [];
}
$childRefererMap[$referer][] = $row;
}
// Step 4: 将子树注入一级父数组
foreach ($array1 as &$root) {
$page = $root['page'];
if (isset($childRefererMap[$page])) {
$root['childs'] = array_merge($root['childs'], $childRefererMap[$page]);
}
}
unset($root); // 解除引用
// 输出结果（即 $array1 已变为期望的 $array3）
print_r($array1);
关键注意事项
- ✅ 支持无限嵌套：算法不依赖递归深度，仅通过多次哈希查找与数组追加完成层级拼装；
- ⚠️ 同名
page冲突：确保所有page值全局唯一，否则映射会覆盖； - ⚠️
referer必须存在且有效：若子节点referer指向不存在的父节点（如'referer'=>'999.ru'），该子节点将被丢弃（可扩展为日志告警）； - ✅ 同父多子安全：使用
[]=追加而非赋值，避免多个子节点相互覆盖； - ? 可扩展建议：如需支持排序、过滤或动态加载，可在
Step 4后添加usort()或封装为独立函数（如buildTree($roots, $nodes, $idKey='page', $parentKey='referer')）。
该方案已在 CMS 导航生成、后台权限菜单构建等场景稳定运行，兼具性能、健壮性与可维护性。
