萬盛學電腦網

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

PHP 扁平陣列轉巢狀分類樹:高效能遞歸與引用賦值實作

問題背景

資料庫查出的分類列表通常是扁平結構:

[
    ['id' => 1, 'pid' => 0, 'name' => '電子產品'],
    ['id' => 2, 'pid' => 1, 'name' => '手機'],
    ['id' => 3, 'pid' => 1, 'name' => '筆電'],
    ['id' => 4, 'pid' => 2, 'name' => 'iPhone'],
    ['id' => 5, 'pid' => 0, 'name' => '家電'],
]

前端樹狀選單、無限級選單、麵包屑導航都需要巢狀結構:

[
    ['id' => 1, 'pid' => 0, 'name' => '電子產品', 'children' => [
        ['id' => 2, 'pid' => 1, 'name' => '手機', 'children' => [
            ['id' => 4, 'pid' => 2, 'name' => 'iPhone', 'children' => []]
        ]],
        ['id' => 3, 'pid' => 1, 'name' => '筆電', 'children' => []]
    ]],
    ['id' => 5, 'pid' => 0, 'name' => '家電', 'children' => []]
]

核心演算法:O(N) 單次遍歷 + 引用賦值

關鍵技巧:先建立 id => 節點引用的哈希表,再單次遍歷掛載 children,完全避免遞歸查找,效能 O(N)。

標準實作(支援物件/陣列)

<?php
/**
 * 扁平分類列表轉巢狀樹
 * @param array $list  扁平列表,鍵為 id,值為節點(陣列或物件),需含 pid 欄位
 * @param string $pidKey  父 ID 欄位名,預設 'pid'
 * @param string $childKey 子節點鍵名,預設 'children'
 * @return array 根節點陣列
 */
function buildTree(array $list, string $pidKey = 'pid', string $childKey = 'children'): array
{
    // 1. 建立 id => 節點引用表(關鍵:用 & 取得引用)
    $map = [];
    foreach ($list as $id => &$node) {
        $map[$id] = &$node;
        // 初始化 children
        if (is_array($node)) {
            $node[$childKey] = [];
        } elseif (is_object($node)) {
            $node->$childKey = [];
        }
    }
    unset($node); // 解除引用,防止後續誤用

    // 2. 單次遍歷掛載
    $roots = [];
    foreach ($list as $id => &$node) {
        $pid = is_array($node) ? $node[$pidKey] : $node->$pidKey;
        if ($pid == 0 || !isset($map[$pid])) {
            // 根節點或找不到父節點(髒資料保護)
            $roots[] = &$node;
        } else {
            // 掛載到父節點的 children
            $parent = &$map[$pid];
            if (is_array($parent)) {
                $parent[$childKey][] = &$node;
            } else {
                $parent->$childKey[] = &$node;
            }
        }
    }
    return $roots;
}
?>

使用範例

<?php
// 模擬資料庫查詢結果
$flat = [
    1 => (object)['id' => 1, 'pid' => 0, 'name' => '電子產品'],
    2 => (object)['id' => 2, 'pid' => 1, 'name' => '手機'],
    3 => (object)['id' => 3, 'pid' => 1, 'name' => '筆電'],
    4 => (object)['id' => 4, 'pid' => 2, 'name' => 'iPhone'],
    5 => (object)['id' => 5, 'pid' => 0, 'name' => '家電'],
];

$tree = buildTree($flat);
echo json_encode($tree, JSON_UNESCAPED_UNICODE | JSON_PRETTY_PRINT);
?>

進階變體

1. 非連續 ID / 字串 ID

只要 $list 的鍵為唯一識別碼即可,不限數字、不限連續。

2. 多重根節點(森林)

函數回傳陣列,天然支援多根節點。

3. 只需特定節點的子樹

<?php
function getSubTree(array $list, $rootId, string $pidKey = 'pid', string $childKey = 'children'): ?array
{
    $tree = buildTree($list, $pidKey, $childKey);
    // 簡易搜尋(實務上可在 buildTree 時建立 id->node 索引直接取用)
    $finder = function ($nodes) use ($rootId, &$finder) {
        foreach ($nodes as $node) {
            $id = is_array($node) ? $node['id'] : $node->id;
            if ($id == $rootId) return $node;
            $child = $finder($node[$childKey] ?? []);
            if ($child) return $child;
        }
        return null;
    };
    return $finder($tree);
}
?>

4. Laravel Eloquent Collection 版

<?php
// 假設 $categories = Category::all()->keyBy('id');
$categories->each(function ($cat) use ($categories) {
    $cat->children = $categories->where('pid', $cat->id)->values();
});
$roots = $categories->where('pid', 0)->values();
?>

效能對比

方法時間複雜度記憶體適用資料量
遞歸查找(傳統寫法)O(N²) 最壞低< 100 筆
本文方法(哈希表+引用)O(N)O(N)10 萬+ 筆
資料庫遞歸 CTE (MySQL 8.0+)O(N)DB 端極大資料集

常見錯誤與除錯

  1. 忘記 & 引用:導致 children 掛載到複製品,原樹不變
  2. 未初始化 children:[] 追加時會產生「Indirect modification」警告
  3. pid 指向不存在的 id:本文程式碼會視為根節點,避免資料遺失
  4. 循環引用(pid 形成環):會導致無限遞歸,建議資料庫層面加檢查約束

掌握這個 O(N) 樹構建演算法,處理萬級分類也能毫秒級完成,是 PHP 後端開發的必備工具函數。

copyright © 萬盛學電腦網 all rights reserved