如何构建无限嵌套树形数组？两级关联数组合并实现方案

我们有两个数组，第一个是一级父节点数组，第二个是子节点数组（子节点通过referer字段指定所属父节点的page值）。需要将二者合并为支持无限嵌套的数组结构，示例如下：

一级父节点数组 #

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

期望的嵌套结果数组 #

$array3 = [
    ['page'=>'1.ru', 'title'=>'—', 'childs'=>[]],
    ['page'=>'3.ru', 'title'=>'—', 'childs'=>[
        ['page'=>'33.ru' , 'title'=>'+', 'childs'=>[]],
    ]],
    ['page'=>'6.ru', 'title'=>'—', 'childs'=>[
        ['page'=>'66.ru' , 'title'=>'+', 'childs'=>[
            ['page'=>'666.ru', 'title'=>'—', 'childs'=>[]]
        ]]
    ]]
];

解决方案 #

核心思路是通过构建节点映射表实现快速查找，再将子节点关联到对应父节点的childs数组中，具体步骤如下：

1. 把所有一级父节点存入以page为键的映射表，方便后续快速定位节点；
2. 遍历子节点数组，给每个子节点添加childs字段（默认空数组），并将其存入映射表；
3. 根据子节点的referer字段找到对应的父节点，将子节点添加到父节点的childs数组中；
4. 最终的嵌套数组就是原一级父节点数组，因为它们已经包含了所有嵌套的子节点。

实现代码 #

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

// 构建节点映射表，key为page值，value为节点引用
$nodeMap = [];

// 先将一级父节点加入映射表
foreach ($array1 as &$parentNode) {
    $nodeMap[$parentNode['page']] = &$parentNode;
}
unset($parentNode); // 释放引用，避免后续操作出现意外

// 处理子节点，关联到父节点
foreach ($array2 as $childData) {
    // 给子节点添加childs字段
    $childNode = $childData;
    $childNode['childs'] = [];
    
    // 将子节点存入映射表
    $nodeMap[$childNode['page']] = $childNode;
    
    // 找到父节点并添加子节点
    if (isset($nodeMap[$childNode['referer']])) {
        $nodeMap[$childNode['referer']]['childs'][] = &$nodeMap[$childNode['page']];
    }
}

// 最终的嵌套数组
$array3 = $array1;

// 输出验证
print_r($array3);
?>

方案优势 #

• 支持无限层级嵌套，无论子节点的嵌套深度有多深都能正确处理；
• 不依赖子节点的顺序，即使子节点在父节点之前出现也能正确关联；
• 时间复杂度为O(n)，处理效率高，适合大规模数组。

内容的提问来源于stack exchange，提问作者Aleksandr Pomozov