資料庫查出的分類列表通常是扁平結構:
[
['id' => 1, 'pid' => 0, 'name' => '電子產品'],
['id' => 2, 'pid' => 1, 'name' => '手機'],
['id' => 3, 'pid' => 1, 'name' => '筆電'],
['id' => 4, 'pid' => 2, 'name' => 'iPhone'],
['id' => 5, 'pid' => 0, 'name' => '家電'],
]
前端樹狀選單、無限級選單、麵包屑導航都需要巢狀結構:
[
['id' => 1, 'pid' => 0, 'name' => '電子產品', 'children' => [
['id' => 2, 'pid' => 1, 'name' => '手機', 'children' => [
['id' => 4, 'pid' => 2, 'name' => 'iPhone', 'children' => []]
]],
['id' => 3, 'pid' => 1, 'name' => '筆電', 'children' => []]
]],
['id' => 5, 'pid' => 0, 'name' => '家電', 'children' => []]
]
關鍵技巧:先建立 id => 節點引用的哈希表,再單次遍歷掛載 children,完全避免遞歸查找,效能 O(N)。
<?php
/**
* 扁平分類列表轉巢狀樹
* @param array $list 扁平列表,鍵為 id,值為節點(陣列或物件),需含 pid 欄位
* @param string $pidKey 父 ID 欄位名,預設 'pid'
* @param string $childKey 子節點鍵名,預設 'children'
* @return array 根節點陣列
*/
function buildTree(array $list, string $pidKey = 'pid', string $childKey = 'children'): array
{
// 1. 建立 id => 節點引用表(關鍵:用 & 取得引用)
$map = [];
foreach ($list as $id => &$node) {
$map[$id] = &$node;
// 初始化 children
if (is_array($node)) {
$node[$childKey] = [];
} elseif (is_object($node)) {
$node->$childKey = [];
}
}
unset($node); // 解除引用,防止後續誤用
// 2. 單次遍歷掛載
$roots = [];
foreach ($list as $id => &$node) {
$pid = is_array($node) ? $node[$pidKey] : $node->$pidKey;
if ($pid == 0 || !isset($map[$pid])) {
// 根節點或找不到父節點(髒資料保護)
$roots[] = &$node;
} else {
// 掛載到父節點的 children
$parent = &$map[$pid];
if (is_array($parent)) {
$parent[$childKey][] = &$node;
} else {
$parent->$childKey[] = &$node;
}
}
}
return $roots;
}
?>
<?php
// 模擬資料庫查詢結果
$flat = [
1 => (object)['id' => 1, 'pid' => 0, 'name' => '電子產品'],
2 => (object)['id' => 2, 'pid' => 1, 'name' => '手機'],
3 => (object)['id' => 3, 'pid' => 1, 'name' => '筆電'],
4 => (object)['id' => 4, 'pid' => 2, 'name' => 'iPhone'],
5 => (object)['id' => 5, 'pid' => 0, 'name' => '家電'],
];
$tree = buildTree($flat);
echo json_encode($tree, JSON_UNESCAPED_UNICODE | JSON_PRETTY_PRINT);
?>
只要 $list 的鍵為唯一識別碼即可,不限數字、不限連續。
函數回傳陣列,天然支援多根節點。
<?php
function getSubTree(array $list, $rootId, string $pidKey = 'pid', string $childKey = 'children'): ?array
{
$tree = buildTree($list, $pidKey, $childKey);
// 簡易搜尋(實務上可在 buildTree 時建立 id->node 索引直接取用)
$finder = function ($nodes) use ($rootId, &$finder) {
foreach ($nodes as $node) {
$id = is_array($node) ? $node['id'] : $node->id;
if ($id == $rootId) return $node;
$child = $finder($node[$childKey] ?? []);
if ($child) return $child;
}
return null;
};
return $finder($tree);
}
?>
<?php
// 假設 $categories = Category::all()->keyBy('id');
$categories->each(function ($cat) use ($categories) {
$cat->children = $categories->where('pid', $cat->id)->values();
});
$roots = $categories->where('pid', 0)->values();
?>
| 方法 | 時間複雜度 | 記憶體 | 適用資料量 |
|---|---|---|---|
| 遞歸查找(傳統寫法) | O(N²) 最壞 | 低 | < 100 筆 |
| 本文方法(哈希表+引用) | O(N) | O(N) | 10 萬+ 筆 |
| 資料庫遞歸 CTE (MySQL 8.0+) | O(N) | DB 端 | 極大資料集 |
& 引用:導致 children 掛載到複製品,原樹不變[] 追加時會產生「Indirect modification」警告掌握這個 O(N) 樹構建演算法,處理萬級分類也能毫秒級完成,是 PHP 後端開發的必備工具函數。