您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP 無限分類樹狀結構生成類完整實現

編輯：PHP 相關知識

數據庫設計 (鄰接表模型)


CREATE TABLE `categories` (
  `id` INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  `parent_id` INT UNSIGNED DEFAULT 0 COMMENT '父級 ID，0 為頂級',
  `name` VARCHAR(50) NOT NULL COMMENT '分類名稱',
  `sort` INT DEFAULT 0 COMMENT '同級排序',
  `status` TINYINT DEFAULT 1 COMMENT '1啟用 0禁用',
  INDEX `idx_parent` (`parent_id`),
  INDEX `idx_status_sort` (`status`, `sort`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

核心 Tree 類實現 (遞歸構建)

<?php
class CategoryTree {
    private array $data = [];      // 扁平數據 [id => row]
    private array $children = [];  // 子級索引 [parent_id => [child_ids]]
    private string $indentChar = '│';
    private string $branchChar = '├';
    private string $lastBranchChar = '└';
    private string $spaceChar = '   ';

    public function __construct(array $flatData = []) {
        $this->buildIndex($flatData);
    }

    // 構建索引，O(n) 時間複雜度
    private function buildIndex(array $flatData): void {
        $this->data = [];
        $this->children = [];
        
        foreach ($flatData as $row) {
            $id = (int)$row['id'];
            $this->data[$id] = $row;
            $pid = (int)($row['parent_id'] ?? 0);
            $this->children[$pid][] = $id;
        }
        // 確保每個父級下的子級按 sort 排序
        foreach ($this->children as &$ids) {
            usort($ids, fn($a, $b) => 
                ($this->data[$a]['sort'] ?? 0) <=> ($this->data[$b]['sort'] ?? 0)
            );
        }
    }

    // 公開方法：生成 HTML 下拉選單
    public function getSelectOptions(int $parentId = 0, int $selectedId = 0, string $disabledIds = ''): string {
        $html = '';
        $this->buildOptionsRecursive($parentId, 0, $selectedId, $disabledIds, $html);
        return $html;
    }

    // 公開方法：生成樹狀列表 (UL/LI)
    public function getTreeList(int $parentId = 0, array $options = []): string {
        $defaultOptions = [
            'itemTpl' => '{spacer}{name}',
            'wrapTpl' => '{children}',
            'spacerChars' => ['│', '├', '└', '   '],
        ];
        $opts = array_merge($defaultOptions, $options);
        $this->indentChar = $opts['spacerChars'][0];
        $this->branchChar = $opts['spacerChars'][1];
        $this->lastBranchChar = $opts['spacerChars'][2];
        $this->spaceChar = $opts['spacerChars'][3];
        
        $html = '';
        $this->buildListRecursive($parentId, '', $opts['itemTpl'], $html, true);
        return str_replace('{children}', $html, $opts['wrapTpl']);
    }

    // 遞歸構建下拉選項
    private function buildOptionsRecursive(int $pid, int $level, int $selected, string $disabled, string &$html): void {
        if (empty($this->children[$pid])) return;
        
        $total = count($this->children[$pid]);
        foreach ($this->children[$pid] as $index => $id) {
            $row = $this->data[$id];
            $isLast = ($index === $total - 1);
            $spacer = str_repeat($this->spaceChar, $level);
            $prefix = $isLast ? $this->lastBranchChar : $this->branchChar;
            
            $attrs = 'value="' . $id . '"';
            if ($id == $selected) $attrs .= ' selected';
            if (strpos(",{$disabled},", ",{$id},") !== false) $attrs .= ' disabled';
            
            $html .= "\n";
            
            $this->buildOptionsRecursive($id, $level + 1, $selected, $disabled, $html);
        }
    }

    // 遞歸構建列表
    private function buildListRecursive(int $pid, string $prefix, string $tpl, string &$html, bool $isRoot = false): void {
        if (empty($this->children[$pid])) return;
        
        $total = count($this->children[$pid]);
        foreach ($this->children[$pid] as $index => $id) {
            $row = $this->data[$id];
            $isLast = ($index === $total - 1);
            
            $currentPrefix = $prefix . ($isLast ? $this->lastBranchChar : $this->branchChar);
            $nextPrefix = $prefix . ($isLast ? $this->spaceChar : $this->indentChar . $this->spaceChar);
            $spacer = $isRoot ? '' : $currentPrefix;
            
            $itemHtml = str_replace(
                ['{id}', '{name}', '{spacer}', '{prefix}'],
                [$id, htmlspecialchars($row['name']), $spacer, $currentPrefix],
                $tpl
            );
            $html .= $itemHtml;
            
            $this->buildListRecursive($id, $nextPrefix, $tpl, $html);
        }
    }

    // 實用工具方法
    public function getPath(int $id): array { // 獲取麵包屑路徑
        $path = [];
        while ($id && isset($this->data[$id])) {
            $path[] = $this->data[$id];
            $id = (int)($this->data[$id]['parent_id'] ?? 0);
        }
        return array_reverse($path);
    }

    public function getChildrenIds(int $pid, bool $recursive = true): array { // 獲取所有子孫 ID
        $ids = [];
        $this->collectChildren($pid, $ids, $recursive);
        return $ids;
    }
    
    private function collectChildren(int $pid, array &$ids, bool $recursive): void {
        if (empty($this->children[$pid])) return;
        foreach ($this->children[$pid] as $id) {
            $ids[] = $id;
            if ($recursive) $this->collectChildren($id, $ids, true);
        }
    }
}

使用示例

1. 從數據庫加載並生成下拉選單

<?php
// 1. 獲取扁平數據 (單次查詢，避免 N+1)
$pdo = new PDO("mysql:host=localhost;dbname=test;charset=utf8mb4", "root", "");
$stmt = $pdo->query("SELECT id, parent_id, name, sort FROM categories WHERE status=1 ORDER BY sort ASC");
$flatData = $stmt->fetchAll(PDO::FETCH_ASSOC);

// 2. 實例化樹
$tree = new CategoryTree($flatData);

// 3. 輸出下拉選單 (編輯頁面用)
$selectedId = $_GET['cat_id'] ?? 0;
$disabledIds = $selectedId ? implode(',', $tree->getChildrenIds($selectedId)) : ''; // 禁用自身及子孫
echo '';

2. 生成前端樹狀列表 (配合 CSS/JS 實現摺疊)


<style>
.tree-list { margin: 0; padding-left: 20px; list-style: none; }
.tree-list li { position: relative; padding: 3px 0; cursor: pointer; }
.tree-list li::before { content: "📁"; margin-right: 5px; }
.tree-list li.has-children::before { content: "📂"; }
.tree-list ul { display: none; } /* 默認摺疊 */
.tree-list ul.expanded { display: block; }
</style>

<div id="cat-tree">
<?php echo $tree->getTreeList(0, [
    'itemTpl' => '{spacer}{name}',
    'wrapTpl' => '{children}',
]); ?>
</div>

<script>
document.getElementById('cat-tree').addEventListener('click', e => {
    const li = e.target.closest('li');
    if (li && e.target === li) { // 僅點擊文字展開
        const ul = li.querySelector(':scope > ul');
        if (ul) ul.classList.toggle('expanded');
    }
});
</script>

大數據量優化方案

問題	解決方案
遞歸深度過大導致棧溢出	PHP 默認無限制，但建議改用迭代+棧非遞歸實現
單次查詢數萬行內存壓力	分頁加載 / 虛擬滾動：前端按需 AJAX 請求子級
頻繁讀寫導致數據不一致	改用嵌套集合模型或 Closure Table (閉包表)，查詢子樹 O(1)
移動節點 (修改 parent_id) 成本高	Closure Table 需更新所有後代路徑，考慮異步隊列處理

Closure Table 方案簡介 (百萬級分類推薦)


-- 閉包表：存儲所有祖先-後代關係
CREATE TABLE `category_paths` (
  `ancestor` INT UNSIGNED NOT NULL,
  `descendant` INT UNSIGNED NOT NULL,
  `depth` INT UNSIGNED NOT NULL, -- 0=自身, 1=直接子級, 2=孫級...
  PRIMARY KEY (`ancestor`, `descendant`),
  INDEX `idx_descendant` (`descendant`)
);

-- 查詢節點 5 的所有子孫 (含自身)
SELECT c.* FROM categories c
JOIN category_paths cp ON c.id = cp.descendant
WHERE cp.ancestor = 5 AND cp.depth > 0;

-- 查詢節點 5 的所有祖先 (含自身)
SELECT c.* FROM categories c
JOIN category_paths cp ON c.id = cp.ancestor
WHERE cp.descendant = 5;

-- 移動節點 5 到新父級 10 (需事務)
-- 1. 獲取 5 的所有後代 (含自身)
-- 2. 獲取 10 的所有祖先 (含自身)
-- 3. 刪除 5 及後代的舊路徑
-- 4. 插入新路徑: 10的祖先 × 5的後代，depth 相加

此模型將「查詢子樹」從遞歸 O(n) 降為單表 JOIN O(1)，是大規模分類系統的標準選擇。