萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 無限分類遞迴:父級追溯與子節點掃描

PHP 無限分類遞迴:父級追溯與子節點掃描

處理無限層級分類 (樹狀結構) 時,常需兩種核心操作:向上追溯所有父級 (麵包屑導航) 與 向下掃描所有葉子節點 (權限繼承、選單展開)。本文提供兩個遞迴函數實作,資料結構採用扁平陣列 ['id', 'parent_id', 'name']。

資料結構假設

$categories = [
    ['id' => 1, 'parent_id' => 0, 'name' => '電子產品'],
    ['id' => 2, 'parent_id' => 1, 'name' => '手機'],
    ['id' => 3, 'parent_id' => 2, 'name' => '智能手機'],
    ['id' => 4, 'parent_id' => 1, 'name' => '筆電'],
    ['id' => 5, 'parent_id' => 0, 'name' => '家居'],
    // ...
];

1. 向上追溯:取得某節點的所有祖先 (含自己)

<?php
/**
 * 遞迴向上查找所有父級
 * @param array $data  扁平分類陣列
 * @param int   $id    目標節點 ID
 * @param array $path  遞迴累積路徑 (內部使用)
 * @return array 從頂層到目標節點的路徑 [['name'=>'電子產品','id'=>1], ['name'=>'手機','id'=>2], ...]
 */
function getAncestors(array $data, int $id, array &$path = []): array {
    if ($id === 0) return array_reverse($path); // 遞迴終點:根節點 parent_id=0

    foreach ($data as $node) {
        if ($node['id'] === $id) {
            $path[] = ['name' => $node['name'], 'id' => $node['id']];
            return getAncestors($data, $node['parent_id'], $path);
        }
    }
    return array_reverse($path); // 找不到時返回已累積路徑
}

// 使用
$breadcrumb = getAncestors($categories, 3);
// 輸出:[['電子產品',1], ['手機',2], ['智能手機',3]]
?>

2. 向下掃描:取得某節點的所有葉子節點 ID

<?php
/**
 * 遞迴掃描所有子孫葉子節點 ID
 * @param array $data 扁平分類陣列
 * @param int   $pid  父節點 ID
 * @return string 逗號分隔的葉子節點 ID 字串 (如 "3,6,7")
 */
function scanLeafNodes(array $data, int $pid): string {
    $hasChild = false;
    $leafIds  = '';

    foreach ($data as $node) {
        if ($node['parent_id'] === $pid) {
            $hasChild = true;
            $leafIds .= scanLeafNodes($data, $node['id']) . ',';
        }
    }

    if (!$hasChild) {
        return (string)$pid; // 無子節點 = 葉子節點
    }
    return $leafIds;
}

// 使用
$leafStr = scanLeafNodes($categories, 1); // "3,4,"
$leafIds = array_filter(explode(',', $leafStr)); // [3, 4]
?>

效能優化:建立 ID 索引 (O(1) 查找)

原版每次遞迴都 foreach 遍歷整個陣列,時間複雜度 O(N²)。預先建立 id => node 映射與 parent_id => [children_ids] 反向索引,可降為 O(N)。

<?php
function buildIndexes(array $data): array {
    $byId = [];
    $children = [];
    foreach ($data as $node) {
        $byId[$node['id']] = $node;
        $children[$node['parent_id']][] = $node['id'];
    }
    return ['byId' => $byId, 'children' => $children];
}

// 向上追溯 (O(深度))
function getAncestorsFast(array $byId, int $id): array {
    $path = [];
    while ($id !== 0 && isset($byId[$id])) {
        $path[] = ['name' => $byId[$id]['name'], 'id' => $id];
        $id = $byId[$id]['parent_id'];
    }
    return array_reverse($path);
}

// 向下掃描葉子 (O(節點數))
function scanLeafNodesFast(array $children, int $pid): array {
    if (!isset($children[$pid]) || empty($children[$pid])) {
        return [$pid];
    }
    $leaves = [];
    foreach ($children[$pid] as $childId) {
        $leaves = array_merge($leaves, scanLeafNodesFast($children, $childId));
    }
    return $leaves;
}

// 使用
$indexes = buildIndexes($categories);
$breadcrumb = getAncestorsFast($indexes['byId'], 3);
$leaves = scanLeafNodesFast($indexes['children'], 1);
?>

資料庫層面的替代方案

  • 遞迴 CTE (MySQL 8.0+, PostgreSQL, SQL Server):單條 SQL 完成向上/向下查詢,效能最佳。
  • Closure Table (閉包表):額外儲存所有祖先後代關係,查詢極快,寫入稍複雜。
  • Nested Set / MPTT:適合讀多寫少,修改結構昂貴。
  • Path Enumeration (物化路徑):path = '1/2/3/',LIKE '1/%' 查子孫,SUBSTRING_INDEX 查祖先。

總結

PHP 遞迴處理無限分類直觀易寫,但資料量超過千筆時效能明顯下降。建議:小規模 (<500 節點) 用遞迴函數即可;中大規模務必在資料庫層面解決 (CTE/Closure Table) 或預建索引陣列。圖片中的樹狀圖展示了典型的父子層級關係。

copyright © 萬盛學電腦網 all rights reserved