無限分類（無限級分類）是電商、CMS、權限系統的核心資料結構。本文系統講解遞迴與非遞迴兩大流派的樹構建演算法，並提供生產級優化方案。
$categories = [
['id' => 1, 'name' => '電子產品', 'pid' => 0, 'sort' => 1],
['id' => 2, 'name' => '手機通訊', 'pid' => 1, 'sort' => 1],
['id' => 3, 'name' => '電腦辦公', 'pid' => 1, 'sort' => 2],
['id' => 4, 'name' => '智能手機', 'pid' => 2, 'sort' => 1],
['id' => 5, 'name' => '筆記本電腦', 'pid' => 3, 'sort' => 1],
['id' => 6, 'name' => '台式機', 'pid' => 3, 'sort' => 2],
['id' => 7, 'name' => '配件外設', 'pid' => 1, 'sort' => 3],
['id' => 8, 'name' => '手機殼', 'pid' => 4, 'sort' => 1],
['id' => 9, 'name' => '滑鼠鍵盤', 'pid' => 7, 'sort' => 1],
];function buildTreeRecursive(array $items, int $pid = 0): array
{
$tree = [];
foreach ($items as $item) {
if ($item['pid'] === $pid) {
$children = buildTreeRecursive($items, $item['id']);
if ($children) {
$item['children'] = $children;
}
$tree[] = $item;
}
}
return $tree;
}
$tree = buildTreeRecursive($categories);
print_r($tree);輸出結構：
Array
(
[0] => Array
(
[id] => 1
[name] => 電子產品
[pid] => 0
[children] => Array
(
[0] => Array
(
[id] => 2
[name] => 手機通訊
[children] => Array
(
[0] => Array
(
[id] => 4
[name] => 智能手機
[children] => Array
(
[0] => Array
(
[id] => 8
[name] => 手機殼
)
)
)
)
)
...
)
)
)缺陷：每次遞迴遍歷整個陣列，時間複雜度 O(n²)，資料量大時效能急劇下降。
function buildTreeOptimized(array $items): array
{
// 1. 建立 ID 索引映射
$map = [];
foreach ($items as $item) {
$map[$item['id']] = $item;
}
// 2. 單次遍歷建立父子關係（利用引用）
$tree = [];
foreach ($items as $item) {
$id = $item['id'];
$pid = $item['pid'];
// 確保 map 中有該節點的引用
if (!isset($map[$id]['children'])) {
$map[$id]['children'] = [];
}
if ($pid === 0) {
// 根節點
$tree[] = &$map[$id];
} elseif (isset($map[$pid])) {
// 掛載到父節點
$map[$pid]['children'][] = &$map[$id];
}
// 孤兒節點（父節點不存在）可選擇忽略或掛載到特殊容器
}
return $tree;
}
$tree = buildTreeOptimized($categories);核心技巧：使用 &$map[$id] 引用，確保父節點的 children 陣列指向同一記憶體地址，單次遍歷即可完成樹構建。
function printTreeLevel(array $items, int $pid = 0, int $level = 0): void
{
foreach ($items as $item) {
if ($item['pid'] === $pid) {
echo str_repeat('│ ', $level) . '├─ ' . $item['name'] . "\n";
printTreeLevel($items, $item['id'], $level + 1);
}
}
}
printTreeLevel($categories);輸出：
├─ 電子產品
│ ├─ 手機通訊
│ │ ├─ 智能手機
│ │ │ └─ 手機殼
│ ├─ 電腦辦公
│ │ ├─ 筆記本電腦
│ │ └─ 台式機
│ └─ 配件外設
│ └─ 滑鼠鍵盤-- 閉包表結構
CREATE TABLE category_closure (
ancestor INT NOT NULL,
descendant INT NOT NULL,
depth INT NOT NULL,
PRIMARY KEY (ancestor, descendant)
);
-- 查詢某節點所有子孫（含自身）
SELECT c.* FROM categories c
JOIN category_closure cc ON c.id = cc.descendant
WHERE cc.ancestor = 1 AND cc.depth > 0;
-- 查詢某節點所有祖先
SELECT c.* FROM categories c
JOIN category_closure cc ON c.id = cc.ancestor
WHERE cc.descendant = 8 AND cc.depth > 0;-- 增加 path 欄位：/1/2/4/8/
ALTER TABLE categories ADD COLUMN path VARCHAR(500) DEFAULT '';
-- 查詢子樹
SELECT * FROM categories WHERE path LIKE '/1/2/4/%';
-- 查詢祖先鏈
SELECT * FROM categories WHERE '/1/2/4/8/' LIKE CONCAT(path, '%') AND id != 8;-- left/right 編號
-- 查詢子樹：left > parent.left AND right < parent.right
-- 移動子樹需重新編號，寫入成本高<?php
declare(strict_types=1);
namespace App\Utils;
class TreeBuilder
{
public static function build(array $items, string $idKey = 'id', string $pidKey = 'pid', string $childrenKey = 'children'): array
{
$map = [];
foreach ($items as $item) {
$id = $item[$idKey];
$map[$id] = $item;
$map[$id][$childrenKey] = [];
}
$tree = [];
foreach ($items as $item) {
$id = $item[$idKey];
$pid = $item[$pidKey];
if ($pid === 0 || $pid === '0' || $pid === null) {
$tree[] = &$map[$id];
} elseif (isset($map[$pid])) {
$map[$pid][$childrenKey][] = &$map[$id];
}
}
return $tree;
}
public static function getChildren(array $tree, int $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
{
foreach ($tree as $node) {
if ($node[$idKey] === $targetId) {
return $node[$childrenKey] ?? [];
}
if (!empty($node[$childrenKey])) {
$result = self::getChildren($node[$childrenKey], $targetId, $idKey, $childrenKey);
if ($result) return $result;
}
}
return [];
}
public static function getPath(array $tree, int $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
{
$path = [];
self::findPath($tree, $targetId, $path, $idKey, $childrenKey);
return $path;
}
private static function findPath(array $tree, int $targetId, array &$path, string $idKey, string $childrenKey): bool
{
foreach ($tree as $node) {
$path[] = $node;
if ($node[$idKey] === $targetId) {
return true;
}
if (!empty($node[$childrenKey]) && self::findPath($node[$childrenKey], $targetId, $path, $idKey, $childrenKey)) {
return true;
}
array_pop($path);
}
return false;
}
public static function toFlat(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::toFlat($children, $childrenKey));
}
}
return $flat;
}
}
// 使用
$tree = TreeBuilder::build($categories);
$path = TreeBuilder::getPath($tree, 8); // 獲取手機殼的完整路徑
| 方案 | 時間複雜度 | 空間複雜度 | 適用場景 | 資料量建議 |
|---|---|---|---|---|
| 遞迴遍歷 | O(n²) | O(h) | 教學、極小資料集 | < 100 條 |
| 引用法單次遍歷 | O(n) | O(n) | 通用 Web 應用、API 回傳 | < 10,000 條 |
| 閉包表 | O(log n) 查詢 | O(n log n) | 高頻讀取、複雜祖先/子孫查詢 | > 10,000 條 |
| 路徑枚舉 | O(log n) 查詢 | O(n) | 中等規模、簡單部署 | < 50,000 條 |
pid === id 或使用拓撲排序驗證xdebug.max_nesting_level掌握引用法單次遍歷構建樹是 PHP 開發者必備技能；大規模場景請務必在資料庫層面佈局閉包表或路徑枚舉，將複雜度前置到寫入端，換取讀取端的極致效能。
