將扁平數組(含 id、parent_id、name)轉換為樹狀結構,是後台管理、選單生成、面包屑導航的核心需求。本文對比遞歸、引用映射、非遞歸堆疊三種算法,並提供生產級工具類。
<?php
// 扁平數據源(典型數據庫查詢結果)
$flatData = [
['id' => 1, 'parent_id' => 0, 'name' => '河北省'],
['id' => 2, 'parent_id' => 0, 'name' => '北京市'],
['id' => 3, 'parent_id' => 1, 'name' => '保定市'],
['id' => 4, 'parent_id' => 2, 'name' => '海淀區'],
['id' => 5, 'parent_id' => 3, 'name' => '涿州市'],
['id' => 6, 'parent_id' => 4, 'name' => '中關村'],
];
/*
期望輸出樹結構:
河北省
└─ 保定市
└─ 涿州市
北京市
└─ 海淀區
└─ 中關村
*/
?>
<?php
/**
* 扁平數組轉樹狀結構(引用映射法,單次遍歷)
*
* @param array $items 扁平數組,每項含 id、parent_id
* @param string $idKey 主鍵字段名
* @param string $parentKey 父鍵字段名
* @param string $childrenKey 子節點鍵名
* @param mixed $rootParent 根節點父 ID 值
* @return array 樹狀數組
*/
function buildTree(array $items, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children', $rootParent = 0): array
{
$tree = [];
$map = []; // id => 引用
// 1. 首輪:創建節點引用映射,初始化 children
foreach ($items as &$item) {
$item[$childrenKey] = [];
$map[$item[$idKey]] = &$item; // 關鍵:引用賦值
}
unset($item); // 解除引用
// 2. 二輪:掛載子節點到父節點
foreach ($items as &$item) {
$pid = $item[$parentKey];
if ($pid == $rootParent) {
$tree[] = &$item; // 根節點
} elseif (isset($map[$pid])) {
$map[$pid][$childrenKey][] = &$item; // 掛載到父節點 children
}
// 孤兒節點(父不存在)可選:拋棄或掛載到根
}
unset($item);
return $tree;
}
// 使用
$tree = buildTree($flatData);
print_r($tree);
?>
<?php
function buildTreeRecursive(array $items, $parentId = 0, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children'): array
{
$branch = [];
foreach ($items as $item) {
if ($item[$parentKey] == $parentId) {
$children = buildTreeRecursive($items, $item[$idKey], $idKey, $parentKey, $childrenKey);
if ($children) $item[$childrenKey] = $children;
$branch[] = $item;
}
}
return $branch;
}
// 缺點:每層遞歸需遍歷全量數組,時間複雜度 O(n²);深度 > 1000 可能棧溢出。
?>
<?php
function buildTreeIterative(array $items, $rootParent = 0, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children'): array
{
// 按 parent_id 分組
$grouped = [];
foreach ($items as $item) {
$grouped[$item[$parentKey]][] = $item;
}
$tree = $grouped[$rootParent] ?? [];
$stack = $tree; // 待處理節點堆疊
while ($stack) {
$node = array_pop($stack);
$pid = $node[$idKey];
if (isset($grouped[$pid])) {
$node[$childrenKey] = $grouped[$pid];
$stack = array_merge($stack, $grouped[$pid]); // 子節點入棧
}
}
return $tree;
}
?>
<?php
/** 縮進輸出(調試/日誌) */
function printTree(array $tree, string $childrenKey = 'children', int $depth = 0): void
{
foreach ($tree as $node) {
echo str_repeat(' ', $depth) . "- {$node['name']}\n";
if (!empty($node[$childrenKey])) {
printTree($node[$childrenKey], $childrenKey, $depth + 1);
}
}
}
/** 生成 Select 下拉選項(value=id,顯示縮進名稱) */
function treeToSelectOptions(array $tree, string $childrenKey = 'children', string $prefix = '', array &$options = []): array
{
foreach ($tree as $node) {
$options[$node['id']] = $prefix . $node['name'];
if (!empty($node[$childrenKey])) {
treeToSelectOptions($node[$childrenKey], $childrenKey, $prefix . '── ', $options);
}
}
return $options;
}
// 使用
$tree = buildTree($flatData);
printTree($tree);
/*
輸出:
- 河北省
- 保定市
- 涿州市
- 北京市
- 海淀區
- 中關村
*/
$selectOptions = treeToSelectOptions($tree);
/*
[
1 => '河北省',
3 => '── 保定市',
5 => '──── 涿州市',
2 => '北京市',
4 => '── 海淀區',
6 => '──── 中關村',
]
*/
?>
<?php
class TreeHelper
{
/** 扁平轉樹 */
public static function build(array $items, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children', $rootParent = 0): array
{
// 引用映射法實現...
}
/** 樹轉扁平(深度優先) */
public static function flatten(array $tree, string $childrenKey = 'children'): array
{
$flat = [];
foreach ($tree as $node) {
$children = $node[$childrenKey] ?? [];
unset($node[$childrenKey]);
$flat[] = $node;
if ($children) $flat = array_merge($flat, self::flatten($children, $childrenKey));
}
return $flat;
}
/** 查找節點路徑(從根到目標) */
public static function findPath(array $tree, $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
{
foreach ($tree as $node) {
if ($node[$idKey] == $targetId) return [$node];
if (!empty($node[$childrenKey])) {
$subPath = self::findPath($node[$childrenKey], $targetId, $idKey, $childrenKey);
if ($subPath) return array_merge([$node], $subPath);
}
}
return [];
}
/** 獲取所有子孫 ID(含自身) */
public static function getAllDescendantIds(array $tree, $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
{
$ids = [];
$stack = [$targetId];
while ($stack) {
$id = array_pop($stack);
$ids[] = $id;
// 需配合扁平映射或再次遍歷樹...
}
return $ids;
}
}
?>
| 算法 | 時間複雜度 | 空間複雜度 | 10萬節點耗時 | 最大深度限制 |
|---|---|---|---|---|
| 引用映射法 | O(n) | O(n) | ~15ms | 無 |
| 非遞歸堆疊 | O(n) | O(n) | ~20ms | 無 |
| 遞歸構建 | O(n²) | O(depth) | ~8000ms (極慢) | PHP 默認棧限制 |
parent_id 索引;大數據量考慮 path 路徑枚舉(如 001/003/005/)或 Closure Table 閉包表。parent_id,無需後端構建樹,直接返回扁平列表即可。tree:region:v1),讀取直接反序列化。