傳統遞歸構建樹形結構存在性能瓶頸(重複遍歷、深度限制、內存開銷)。本文介紹一種基於 PHP 引用賦值的單次遍歷 O(n) 算法,代碼極簡卻極其高效。
<?php
function generateTree($items) {
$tree = [];
foreach ($items as $item) {
// 關鍵:引用賦值 &$items[$item['id']]
if (isset($items[$item['pid']])) {
// 父節點存在:掛載到父節點的 son 屬性
$items[$item['pid']]['son'][] = &$items[$item['id']];
} else {
// 根節點:加入樹根
$tree[] = &$items[$item['id']];
}
}
return $tree;
}
// 測試數據:ID 為鍵名,便於 O(1) 查找父節點
$items = [
1 => ['id' => 1, 'pid' => 0, 'name' => '安徽省'],
2 => ['id' => 2, 'pid' => 0, 'name' => '浙江省'],
3 => ['id' => 3, 'pid' => 1, 'name' => '合肥市'],
4 => ['id' => 4, 'pid' => 3, 'name' => '長豐縣'],
5 => ['id' => 5, 'pid' => 1, 'name' => '安慶市'],
];
$tree = generateTree($items);
print_r($tree);
?>
Array
(
[0] => Array
(
[id] => 1
[pid] => 0
[name] => 安徽省
[son] => Array
(
[0] => Array
(
[id] => 3
[pid] => 1
[name] => 合肥市
[son] => Array
(
[0] => Array
(
[id] => 4
[pid] => 3
[name] => 長豐縣
)
)
)
[1] => Array
(
[id] => 5
[pid] => 1
[name] => 安慶市
)
)
)
[1] => Array
(
[id] => 2
[pid] => 0
[name] => 浙江省
)
)
<?php
function generateTree($items) {
foreach ($items as $item) {
// 引用賦值:將當前節點掛載到父節點的 son[$id] 下
$items[$item['pid']]['son'][$item['id']] = &$items[$item['id']];
}
// 返回虛擬根節點 0 的子節點
return isset($items[0]['son']) ? $items[0]['son'] : [];
}
?>
| 關鍵點 | 解釋 |
|---|---|
| 數組鍵名為 ID | 確保 $items[$pid] 為 O(1) 查找,無需遍歷 |
| 引用賦值 & | 父節點持有子節點的引用而非副本,修改同步生效 |
| 虛擬根節點 0 | 統一處理頂級節點,無需特殊判斷 |
| 單次遍歷 | 時間複雜度 O(n),遞歸法通常 O(n log n) 甚至 O(n²) |
生成樹結構後,前端渲染或導出仍需遞歸遍歷:
<?php
function renderTree($tree, $level = 0) {
foreach ($tree as $node) {
echo str_repeat(' ', $level) . $node['name'] . "\n";
if (!empty($node['son'])) {
renderTree($node['son'], $level + 1);
}
}
}
renderTree($tree);
/* 輸出:
安徽省
合肥市
長豐縣
安慶市
浙江省
*/
?>
<TreeNode :node="node" /><ul><li> 結構,配合 CSS 縮進expanded、selected 字段適用:行政區劃、商品分類、組織架構、菜單權限、評論回覆等層級不超過 10 層、節點數 < 10 萬的場景
不適用:極深層級(>100)、極大數據量(>100萬)、頻繁增刪改需實時維護樹結構的場景(建議 Closure Table 或物化路徑)