PHP 樹形結構資料存取類：高效構建、查詢與序列化

前言

分類目錄、組織架構、評論回覆、選單導航等場景均涉及樹形資料。本文實現一個通用 Tree 類，支援：

• 陣列資料快速構建樹 (遞歸/迭代雙模式)
• O(1) 節點查找 (雜湊索引)
• 子孫/祖先/兄弟節點遍歷
• 多種序列化輸出 (巢狀陣列、扁平陣列、JSON、HTML <ul>)
• 大數據量分頁載入策略

一、資料結構約定

輸入陣列每項必含：

• id (int/string) 唯一標識
• pid (int/string) 父節點 ID，根節點為 0 或 null
• 其他業務字段 (name, title, sort, url, icon...)

$rawData = [
    ['id'=>1, 'pid'=>0, 'name'=>'PHP', 'sort'=>1],
    ['id'=>2, 'pid'=>0, 'name'=>'Java', 'sort'=>2],
    ['id'=>3, 'pid'=>1, 'name'=>'Laravel', 'sort'=>1],
    ['id'=>4, 'pid'=>1, 'name'=>'Symfony', 'sort'=>2],
    ['id'=>5, 'pid'=>3, 'name'=>'Eloquent ORM', 'sort'=>1],
    ['id'=>6, 'pid'=>2, 'name'=>'Spring Boot', 'sort'=>1],
];

二、核心類實現

<?php
namespace App\Structures;

use ArrayAccess;
use Countable;
use IteratorAggregate;
use JsonSerializable;
use Traversable;

class Tree implements ArrayAccess, Countable, IteratorAggregate, JsonSerializable {
    /** @var array 所有節點索引 id => Node */
    private array $nodes = [];
    /** @var array> 父子關係索引 pid => [childNodes] */
    private array $childrenIndex = [];
    /** @var array 根節點列表 */
    private array $roots = [];
    /** @var callable|null 自定義節點排序器 */
    private ?callable $sorter = null;

    /** 節點內部類 */
    private class Node {
        public int|string $id;
        public int|string $pid;
        public array $data;      // 原始業務數據
        public ?Node $parent = null;
        public array $children = [];
        public int $depth = 0;
        public bool $isLeaf = true;

        public function __construct(array $data) {
            $this->id   = $data['id'];
            $this->pid  = $data['pid'] ?? 0;
            $this->data = $data;
        }
    }

    /**
     * 構造函數：從扁平陣列構建樹
     * @param array $items 扁平資料
     * @param callable|null $sorter 子節點排序器 fn(Node $a, Node $b): int
     */
    public function __construct(array $items = [], ?callable $sorter = null) {
        $this->sorter = $sorter;
        if ($items) $this->build($items);
    }

    /** 重新構建樹 (支援動態更新資料) */
    public function build(array $items): self {
        $this->clear();
        
        // 1. 建立所有節點
        foreach ($items as $item) {
            if (!isset($item['id'])) continue;
            $node = new Node($item);
            $this->nodes[$node->id] = $node;
            $this->childrenIndex[$node->pid][] = $node;
        }

        // 2. 建立父子關係與深度
        foreach ($this->nodes as $node) {
            if ($node->pid !== 0 && $node->pid !== null && isset($this->nodes[$node->pid])) {
                $parent = $this->nodes[$node->pid];
                $node->parent = $parent;
                $parent->children[] = $node;
                $parent->isLeaf = false;
                $node->depth = $parent->depth + 1;
            } else {
                $this->roots[] = $node;
            }
        }

        // 3. 排序子節點
        if ($this->sorter) {
            foreach ($this->childrenIndex as &$children) {
                usort($children, $this->sorter);
            }
            usort($this->roots, $this->sorter);
        } else {
            // 預設按 sort 升序，再按 id 升序
            $defaultSorter = fn(Node $a, Node $b) => 
                (($a->data['sort'] ?? 0) <=> ($b->data['sort'] ?? 0)) ?: ($a->id <=> $b->id);
            foreach ($this->childrenIndex as &$children) {
                usort($children, $defaultSorter);
            }
            usort($this->roots, $defaultSorter);
        }

        return $this;
    }

    /** 獲取節點 (O(1)) */
    public function getNode(int|string $id): ?Node {
        return $this->nodes[$id] ?? null;
    }

    /** 獲取子節點列表 */
    public function getChildren(int|string $id): array {
        $node = $this->getNode($id);
        return $node?->children ?? [];
    }

    /** 獲取所有後代節點 (遞歸) */
    public function getDescendants(int|string $id): array {
        $result = [];
        $node = $this->getNode($id);
        if (!$node) return $result;
        $this->collectDescendants($node, $result);
        return $result;
    }

    private function collectDescendants(Node $node, array &$result): void {
        foreach ($node->children as $child) {
            $result[] = $child;
            $this->collectDescendants($child, $result);
        }
    }

    /** 獲取祖先鏈 (含自身可選) */
    public function getAncestors(int|string $id, bool $includeSelf = false): array {
        $result = [];
        $node = $this->getNode($id);
        if (!$node) return $result;
        if ($includeSelf) $result[] = $node;
        while ($node->parent) {
            $result[] = $node->parent;
            $node = $node->parent;
        }
        return array_reverse($result); // 從根到父
    }

    /** 獲取兄弟節點 (含自身可選) */
    public function getSiblings(int|string $id, bool $includeSelf = false): array {
        $node = $this->getNode($id);
        if (!$node || !$node->parent) return $includeSelf ? [$node] : [];
        $siblings = $node->parent->children;
        if (!$includeSelf) {
            $siblings = array_filter($siblings, fn($n) => $n->id !== $id);
        }
        return array_values($siblings);
    }

    /** 獲取根節點列表 */
    public function getRoots(): array {
        return $this->roots;
    }

    /** 獲取節點路徑 (從根到該節點的 ID 陣列) */
    public function getPath(int|string $id): array {
        return array_map(fn($n) => $n->id, $this->getAncestors($id, true));
    }

    /** 判斷是否為祖先關係 */
    public function isAncestorOf(int|string $ancestorId, int|string $descendantId): bool {
        $descendant = $this->getNode($descendantId);
        while ($descendant) {
            if ($descendant->id === $ancestorId) return true;
            $descendant = $descendant->parent;
        }
        return false;
    }

    // ==================== 序列化輸出 ====================

    /** 轉為巢狀陣列 (適合 JSON API) */
    public function toNestedArray(bool $includeMeta = true): array {
        $result = [];
        foreach ($this->roots as $root) {
            $result[] = $this->nodeToArray($root, $includeMeta);
        }
        return $result;
    }

    private function nodeToArray(Node $node, bool $includeMeta): array {
        $arr = $node->data;
        if ($includeMeta) {
            $arr['_meta'] = [
                'id'       => $node->id,
                'pid'      => $node->pid,
                'depth'    => $node->depth,
                'is_leaf'  => $node->isLeaf,
                'children_count' => count($node->children),
            ];
        }
        if ($node->children) {
            $arr['children'] = array_map(fn($c) => $this->nodeToArray($c, $includeMeta), $node->children);
        }
        return $arr;
    }

    /** 轉為扁平陣列 (適合資料表同步、CSV 匯出) */
    public function toFlatArray(bool $includeMeta = true): array {
        $result = [];
        foreach ($this->roots as $root) {
            $this->collectFlat($root, $result, $includeMeta);
        }
        return $result;
    }

    private function collectFlat(Node $node, array &$result, bool $includeMeta): void {
        $arr = $node->data;
        if ($includeMeta) {
            $arr['_meta'] = [
                'id'       => $node->id,
                'pid'      => $node->pid,
                'depth'    => $node->depth,
                'is_leaf'  => $node->isLeaf,
            ];
        }
        $result[] = $arr;
        foreach ($node->children as $child) {
            $this->collectFlat($child, $result, $includeMeta);
        }
    }

    /** 渲染為 HTML <ul> 樹狀選單 */
    public function renderHtml(array $options = []): string {
        $opts = array_merge([
            'id_prefix'     => 'tree_',
            'include_class' => true,
            'item_template' => '
{label}{children}
',
            'label_field'   => 'name',
            'url_field'     => 'url',
        ], $options);

        $html = '
';
        foreach ($this->roots as $root) {
            $html .= $this->renderNodeHtml($root, $opts);
        }
        $html .= '
';
        return $html;
    }

    private function renderNodeHtml(Node $node, array $opts): string {
        $label = $node->data[$opts['label_field']] ?? $node->id;
        $url   = $node->data[$opts['url_field']] ?? '#';
        $classes = [];
        if ($opts['include_class']) {
            $classes[] = 'tree-node';
            $classes[] = 'depth-' . $node->depth;
            if ($node->isLeaf) $classes[] = 'leaf';
            else $classes[] = 'parent';
        }
        $itemHtml = str_replace(
            ['{id}', '{pid}', '{label}', '{url}', '{classes}'],
            [$node->id, $node->pid, htmlspecialchars($label), htmlspecialchars($url), implode(' ', $classes)],
            $opts['item_template']
        );
        $childrenHtml = '';
        if ($node->children) {
            $childrenHtml = '
';
            foreach ($node->children as $child) {
                $childrenHtml .= $this->renderNodeHtml($child, $opts);
            }
            $childrenHtml .= '
';
        }
        return str_replace('{children}', $childrenHtml, $itemHtml);
    }

    // ==================== 介面實現 ====================

    public function offsetExists(mixed $offset): bool { return isset($this->nodes[$offset]); }
    public function offsetGet(mixed $offset): mixed { return $this->nodes[$offset]?->data ?? null; }
    public function offsetSet(mixed $offset, mixed $value): void { throw new \BadMethodCallException('Tree 是不可變結構，請使用 build() 重建'); }
    public function offsetUnset(mixed $offset): void { throw new \BadMethodCallException('Tree 是不可變結構'); }
    public function count(): int { return count($this->nodes); }
    public function getIterator(): Traversable { return new \ArrayIterator($this->nodes); }
    public function jsonSerialize(): mixed { return $this->toNestedArray(); }

    private function clear(): void {
        $this->nodes = [];
        $this->childrenIndex = [];
        $this->roots = [];
    }
}

三、使用範例

1. 基礎構建與查詢

<?php
use App\Structures\Tree;

$raw = [
    ['id'=>1, 'pid'=>0, 'name'=>'電子產品', 'sort'=>1, 'url'=>'/cat/1'],
    ['id'=>2, 'pid'=>0, 'name'=>'圖書', 'sort'=>2, 'url'=>'/cat/2'],
    ['id'=>3, 'pid'=>1, 'name'=>'手機', 'sort'=>1, 'url'=>'/cat/3'],
    ['id'=>4, 'pid'=>1, 'name'=>'筆電', 'sort'=>2, 'url'=>'/cat/4'],
    ['id'=>5, 'pid'=>3, 'name'=>'iPhone', 'sort'=>1, 'url'=>'/cat/5'],
    ['id'=>6, 'pid'=>3, 'name'=>'Android', 'sort'=>2, 'url'=>'/cat/6'],
];

$tree = new Tree($raw);

// 獲取手機分類下所有子分類 (含孫)
$mobileChildren = $tree->getDescendants(3);
print_r(array_column($mobileChildren, 'id')); // [5, 6]

// 獲取 iPhone 的麵包屑導航路徑
$path = $tree->getPath(5); // [1, 3, 5]
$breadcrumb = array_map(fn($id) => $tree->getNode($id)->data['name'], $path);
// ['電子產品', '手機', 'iPhone']

// 判斷電子產品是否為手機的祖先
$tree->isAncestorOf(1, 3); // true
$tree->isAncestorOf(2, 3); // false
?>

2. API 回傳 JSON

<?php
// 控制器
public function categoryTree() {
    $categories = Category::all(['id', 'pid', 'name', 'sort', 'icon'])->toArray();
    $tree = new Tree($categories);
    return response()->json([
        'data' => $tree->toNestedArray(),
        'meta' => ['total' => count($tree)]
    ]);
}
// 輸出結構:
// {
//   "data": [
//     {"id":1, "name":"電子產品", "children":[
//       {"id":3, "name":"手機", "children":[
//         {"id":5, "name":"iPhone", "children":[]},
//         {"id":6, "name":"Android", "children":[]}
//       ]}
//     ]}
//   ]
// }
?>

3. HTML 選單渲染

<?php
echo $tree->renderHtml([
    'label_field' => 'name',
    'url_field'   => 'url',
    'item_template' => '
{label}{children}
'
]);
?>

4. 大數據量分頁載入 (前端懶加載)

<?php
// 後端介面：獲取指定節點的直接子節點 (非遞歸)
public function categoryChildren(int $pid = 0, int $page = 1, int $limit = 50) {
    $query = Category::where('pid', $pid)->orderBy('sort')->orderBy('id');
    $total = $query->count();
    $items = $query->forPage($page, $limit)->get(['id','pid','name','sort','url'])->toArray();
    return response()->json([
        'data'  => $items,
        'meta'  => ['total' => $total, 'page' => $page, 'limit' => $limit, 'has_more' => $page * $limit < $total]
    ]);
}

// 前端 Vue/React 組件邏輯:
// 1. 載入根節點 (pid=0)
// 2. 用戶點擊展開節點 -> 請求 /api/category/children?pid=3
// 3. 將返回數據插入到對應節點下
// 4. 標記 leaf 節點不再顯示展開圖標
?>

四、效能基準 (10 萬節點)

環境：PHP 8.2, 10 萬節點, 平均每節點 3 子節點, 深度 6

五、擴展建議

1. 可視化編輯器整合：配合 jstree、vue-draggable-nested-tree 實現拖拽排序，後端接收新順序批量更新 pid、sort。
2. 資料庫層面優化：
3. Closure Table 模式：額外表存儲所有祖先後代關係 (ancestor, descendant, depth)，查詢子樹/路徑極快。
4. Nested Set (左/右值編碼)：適合讀多寫少，單查詢獲取完整子樹。
5. Path Enumeration (物化路徑)：path = '1/3/5/'，LIKE '1/3/%' 查子樹，ORDER BY path 排序。
6. 權限控制：在 getChildren/getDescendants 中注入權限過濾器，不同角色看到不同樹形結構。
7. 異步構建：百萬級節點時，使用 Generator 分批構建，避免佔用過多記憶體阻塞進程。

結語

通用 Tree 類將樹形資料的構建、索引、遍歷、序列化封裝為可復用組件，配合資料庫層面的優化模式 (Closure Table / Nested Set / Path Enumeration)，可覆蓋從簡單選單到複雜組織架構的各類場景。關鍵在於：扁平存儲、記憶體索引、按需序列化、前端懶加載 四大原則的工程化落地。