PHP 無限分類遞迴實作：父子節點追溯與樹狀結構操作

無限分類是電商、CMS、權限系統的核心資料結構。本文提供基於陣列的遞迴實作，包含向下追溯所有子孫節點、向上追溯所有祖先節點、樹狀陣列構建等核心操作。

資料結構定義

<?php
// 資料庫查詢結果範例
$categories = [
    ['id' => 1, 'parent_id' => 0, 'name' => '電子產品'],
    ['id' => 2, 'parent_id' => 1, 'name' => '手機'],
    ['id' => 3, 'parent_id' => 1, 'name' => '筆電'],
    ['id' => 4, 'parent_id' => 2, 'name' => 'iPhone'],
    ['id' => 5, 'parent_id' => 2, 'name' => 'Android'],
    ['id' => 6, 'parent_id' => 0, 'name' => '家電'],
    ['id' => 7, 'parent_id' => 6, 'name' => '冰箱'],
];
?>

核心工具類別

<?php
class CategoryTree {
    private array $nodes = [];
    private array $childrenMap = [];
    private array $parentMap = [];

    public function __construct(array $flatData) {
        foreach ($flatData as $node) {
            $this->nodes[$node['id']] = $node;
            $this->childrenMap[$node['parent_id']][] = $node['id'];
            $this->parentMap[$node['id']] = $node['parent_id'];
        }
    }

    // 向下遞迴：取得所有子孫節點 ID（含自己）
    public function getDescendants(int $id, bool $includeSelf = true): array {
        $result = $includeSelf ? [$id] : [];
        foreach ($this->childrenMap[$id] ?? [] as $childId) {
            $result = array_merge($result, $this->getDescendants($childId, true));
        }
        return $result;
    }

    // 向上遞迴：取得所有祖先節點（含自己）
    public function getAncestors(int $id, bool $includeSelf = true): array {
        $result = $includeSelf ? [$id] : [];
        $parentId = $this->parentMap[$id] ?? 0;
        while ($parentId > 0) {
            $result[] = $parentId;
            $parentId = $this->parentMap[$parentId] ?? 0;
        }
        return array_reverse($result); // 從根到葉
    }

    // 取得完整路徑名稱（如：電子產品 > 手機 > iPhone）
    public function getPath(int $id, string $separator = ' > '): string {
        $ancestors = $this->getAncestors($id, true);
        return implode($separator, array_map(fn($id) => $this->nodes[$id]['name'], $ancestors));
    }

    // 構建樹狀陣列（適合前端樹狀元件）
    public function buildTree(int $rootId = 0): array {
        $tree = [];
        foreach ($this->childrenMap[$rootId] ?? [] as $childId) {
            $tree[] = $this->buildNode($childId);
        }
        return $tree;
    }

    private function buildNode(int $id): array {
        $node = $this->nodes[$id];
        $children = $this->buildTree($id);
        if ($children) $node['children'] = $children;
        return $node;
    }

    // 扁平化樹狀陣列（含層級資訊）
    public function flatten(int $rootId = 0): array {
        $result = [];
        $this->flattenRecursive($rootId, 0, $result);
        return $result;
    }

    private function flattenRecursive(int $id, int $level, array &$result): void {
        foreach ($this->childrenMap[$id] ?? [] as $childId) {
            $node = $this->nodes[$childId];
            $node['level'] = $level;
            $result[] = $node;
            $this->flattenRecursive($childId, $level + 1, $result);
        }
    }
}
?>

使用範例

<?php
$tree = new CategoryTree($categories);

// 1. 取得手機(2)的所有子孫
$descendants = $tree->getDescendants(2);
// [2, 4, 5] (含自己)

// 2. 取得iPhone(4)的所有祖先
$ancestors = $tree->getAncestors(4);
// [1, 2, 4] (根到葉)

// 3. 取得完整路徑
echo $tree->getPath(4); // "電子產品 > 手機 > iPhone"

// 4. 構建完整樹狀結構
$fullTree = $tree->buildTree();
/*
[
    [
        'id' => 1, 'name' => '電子產品', 'children' => [
            ['id' => 2, 'name' => '手機', 'children' => [
                ['id' => 4, 'name' => 'iPhone'],
                ['id' => 5, 'name' => 'Android'],
            ]],
            ['id' => 3, 'name' => '筆電'],
        ]
    ],
    ['id' => 6, 'name' => '家電', 'children' => [
        ['id' => 7, 'name' => '冰箱'],
    ]],
]
*/

// 5. 扁平化輸出（含層級，適合表格顯示）
$flat = $tree->flatten();
/*
[
    ['id'=>1, 'name'=>'電子產品', 'level'=>0],
    ['id'=>2, 'name'=>'手機', 'level'=>1],
    ['id'=>4, 'name'=>'iPhone', 'level'=>2],
    ['id'=>5, 'name'=>'Android', 'level'=>2],
    ['id'=>3, 'name'=>'筆電', 'level'=>1],
    ['id'=>6, 'name'=>'家電', 'level'=>0],
    ['id'=>7, 'name'=>'冰箱', 'level'=>1],
]
*/
?>

資料庫查詢優化：遞迴 CTE (MySQL 8.0+ / PostgreSQL)

-- 向下查詢：取得分類 2 及所有子孫
WITH RECURSIVE category_tree AS (
    SELECT id, parent_id, name, 0 AS level
    FROM categories WHERE id = 2
    UNION ALL
    SELECT c.id, c.parent_id, c.name, ct.level + 1
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT * FROM category_tree;

-- 向上查詢：取得分類 4 所有祖先
WITH RECURSIVE category_path AS (
    SELECT id, parent_id, name, 0 AS level
    FROM categories WHERE id = 4
    UNION ALL
    SELECT c.id, c.parent_id, c.name, cp.level + 1
    FROM categories c
    JOIN category_path cp ON c.id = cp.parent_id
)
SELECT * FROM category_path ORDER BY level DESC;

效能比較與選型建議

現代專案優先考慮 遞迴 CTE 或 Closure Table，PHP 遞迴適合中小型專案或快速原型開發。