使用循环与引用（非递归）构建父子层级数组遇null值问题求助

我有一组对象列表，每个对象包含指定父节点的parent_id字段，可作为其他对象的子节点。预期构建的层级树结构示例如下：

Current Array
element 1
element 2
element 3
element 4
element 5

Organized into a hierarchy 
-----------------------

element 2
   -children:
         element 1
             -children
                  element 5
element 3
   -children:
         element 4

最终要生成仅包含顶层元素、子节点通过引用嵌入的树结构，但实现时遇到部分元素为null的问题。已尝试在循环后添加unset($var)语句处理PHP作用域问题，但仍存在null值。以下是完整示例代码：

$response = array(
    array( "kind"=> "t1", "data" => array( "id" => 25, "parent_id" => 30 )),
    array("kind"=> "t1", "data" => array( "id" => 30,"parent_id" => 0)),
    array("kind"=> "t1", "data" => array("id" => 32, "parent_id" => 0 )),
    array("kind"=> "t1", "data" => array("id" => 33,"parent_id" => 32)),
    array("kind"=> "t1", "data" => array("id" => 35,"parent_id" => 25))
);

$json_str = json_encode($response);

$tree = array();
foreach($response as &$firstObj)
{
    $parentFound = null;
    foreach($response as &$secondObject)
    {
        if($firstObj['data']['parent_id'] == $secondObject['data']['id'])
        {
            $parentFound = &$secondObject;
            break;
        }
        
    }
    unset($secondObject);

    if($parentFound)
    {
        $parentFound['data']['children'] = array(&$firstObj);
    }
    else{
        $tree[] = $firstObj;
    }

}
unset($firstObj);

print_r($tree);

期望得到正确的层级树结构，仅包含无父节点的顶层元素，子节点通过引用嵌入对应位置。

问题根源 #

1. 子节点覆盖问题：原代码中每次找到父节点后，直接将children赋值为array(&$firstObj)，这会覆盖父节点已有的子节点，导致一个父节点只能保留最后一个被处理的子节点。
2. 嵌套循环的引用混乱：嵌套的引用循环容易引发PHP的变量引用残留问题，即使unset也可能因为循环顺序导致意外的null值。
3. 效率低下：嵌套循环的时间复杂度为O(n²)，数据量大时性能很差。

修正后的代码 #

$response = array(
    array( "kind"=> "t1", "data" => array( "id" => 25, "parent_id" => 30 )),
    array("kind"=> "t1", "data" => array( "id" => 30,"parent_id" => 0)),
    array("kind"=> "t1", "data" => array("id" => 32, "parent_id" => 0 )),
    array("kind"=> "t1", "data" => array("id" => 33,"parent_id" => 32)),
    array("kind"=> "t1", "data" => array("id" => 35,"parent_id" => 25))
);

// 第一步：建立ID到元素的映射表，方便快速查找父节点
$idMap = [];
foreach ($response as &$item) {
    $idMap[$item['data']['id']] = &$item;
}
unset($item);

$tree = [];

// 第二步：遍历元素，构建层级结构
foreach ($response as &$item) {
    $parentId = $item['data']['parent_id'];
    if ($parentId === 0) {
        // 顶层节点直接加入树
        $tree[] = &$item;
    } else {
        // 找到父节点，追加到子节点列表
        if (isset($idMap[$parentId])) {
            // 初始化children数组（如果不存在）
            if (!isset($idMap[$parentId]['data']['children'])) {
                $idMap[$parentId]['data']['children'] = [];
            }
            $idMap[$parentId]['data']['children'][] = &$item;
        }
    }
}
unset($item);

print_r($tree);

代码说明 #

1. ID映射表：先遍历一次数组，将每个元素通过id作为键存入$idMap，后续查找父节点时可以直接通过ID定位，时间复杂度降为O(n)。
2. 引用处理：通过引用将子节点直接关联到父节点的children数组中，确保层级结构是引用嵌入的。
3. 子节点追加：判断父节点的children是否存在，不存在则初始化，再将当前元素追加进去，避免覆盖已有子节点。
4. 顶层节点收集：直接将parent_id=0的节点加入$tree数组，确保最终结果只包含顶层元素。

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