萬盛學電腦網

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

PHP 多級分類無限級樹狀結構生成:遞迴建樹與陣列扁平化輸出

前言

電商分類、CMS 欄目、組織架構等場景常需將扁平的「id + parent_id」資料轉為樹狀結構。本文提供兩種主流演算法:遞迴建樹(直觀易懂)與 陣列引用單次遍歷(O(n) 效能最佳),並示範樹狀輸出、選單產生、選取子樹等實務操作。

一、資料結構定義

<?php
// 資料庫查詢結果(扁平陣列)
$categories = [
    ['id' => 1, 'pid' => 0, 'name' => '電子產品'],
    ['id' => 2, 'pid' => 0, 'name' => '服飾鞋包'],
    ['id' => 3, 'pid' => 1, 'name' => '手機'],
    ['id' => 4, 'pid' => 1, 'name' => '筆電'],
    ['id' => 5, 'pid' => 3, 'name' => 'iPhone'],
    ['id' => 6, 'pid' => 3, 'name' => 'Android'],
    ['id' => 7, 'pid' => 2, 'name' => '男裝'],
    ['id' => 8, 'pid' => 7, 'name' => '襯衫'],
];

二、演算法 1:遞迴建樹(適合資料量 < 10000)

<?php
/**
 * 遞迴建立樹狀結構
 * @param array $items 扁平資料
 * @param int $parentId 父節點 ID
 * @return array 樹狀陣列
 */
function buildTreeRecursive(array $items, int $parentId = 0): array
{
    $tree = [];
    foreach ($items as $item) {
        if ($item['pid'] == $parentId) {
            $children = buildTreeRecursive($items, $item['id']);
            if ($children) {
                $item['children'] = $children;
            }
            $tree[] = $item;
        }
    }
    return $tree;
}

$tree = buildTreeRecursive($categories);
print_r($tree);
/*
Array
(
    [0] => Array
        (
            [id] => 1
            [pid] => 0
            [name] => 電子產品
            [children] => Array
                (
                    [0] => Array ( [id]=>3, [pid]=>1, [name]=>手機, [children]=>Array(...) )
                    [1] => Array ( [id]=>4, [pid]=>1, [name]=>筆電 )
                )
        )
    [1] => Array ( [id]=>2, [pid]=>0, [name]=>服飾鞋包, [children]=>Array(...) )
)
*/

三、演算法 2:單次遍歷 O(n)(大量資料首選)

<?php
/**
 * 陣列引用單次遍歷建樹(O(n))
 * @param array $items 扁平資料(需包含 id、pid)
 * @param string $idKey 主鍵欄位名
 * @param string $pidKey 父鍵欄位名
 * @param string $childKey 子節點鍵名
 * @return array 樹狀結構(根節點陣列)
 */
function buildTreeLinear(array $items, string $idKey = 'id', string $pidKey = 'pid', string $childKey = 'children'): array
{
    // 1. 建立 id => node 映射(引用)
    $map = [];
    foreach ($items as &$item) {
        $item[$childKey] = []; // 初始化子節點容器
        $map[$item[$idKey]] = &$item; // 存入引用
    }
    unset($item); // 解除引用

    // 2. 掛載子節點到父節點
    $roots = [];
    foreach ($map as $id => &$node) {
        $pid = $node[$pidKey];
        if ($pid == 0 || !isset($map[$pid])) {
            $roots[] = &$node; // 根節點
        } else {
            $map[$pid][$childKey][] = &$node; // 掛載到父節點
        }
    }
    unset($node);

    return $roots;
}

$tree = buildTreeLinear($categories);
// 結構同遞迴版,但效能 O(n) 且無遞迴深度限制

四、樹狀結構輸出與應用

1. 縮排顯示(後台分類列表)

function printTree(array $tree, int $depth = 0): void
{
    foreach ($tree as $node) {
        echo str_repeat('│   ', $depth) . '├─ ' . $node['name'] . "\n";
        if (!empty($node['children'])) {
            printTree($node['children'], $depth + 1);
        }
    }
}
printTree($tree);
/*
├─ 電子產品
│   ├─ 手機
│   │   ├─ iPhone
│   │   └─ Android
│   └─ 筆電
└─ 服飾鞋包
    └─ 男裝
        └─ 襯衫
*/

2. 產生下拉選單(<optgroup>)

function buildSelectOptions(array $tree, int $depth = 0): string
{
    $html = '';
    foreach ($tree as $node) {
        $indent = str_repeat('— ', $depth);
        $html .= "";
        if (!empty($node['children'])) {
            $html .= buildSelectOptions($node['children'], $depth + 1);
        }
    }
    return $html;
}
echo "";

3. 取得指定節點的所有子孫 ID(含自己)

function getDescendantIds(array $tree, int $targetId): array
{
    $ids = [];
    $stack = $tree;
    while ($stack) {
        $node = array_pop($stack);
        if ($node['id'] == $targetId) {
            // 找到目標,收集整棵子樹
            $collect = function (array $subTree) use (&$collect, &$ids) {
                foreach ($subTree as $n) {
                    $ids[] = $n['id'];
                    if (!empty($n['children'])) $collect($n['children']);
                }
            };
            $collect([$node]);
            break;
        }
        if (!empty($node['children'])) {
            $stack = array_merge($stack, $node['children']);
        }
    }
    return $ids;
}

// 使用:刪除分類前檢查是否有子分類
$childIds = getDescendantIds($tree, 3); // [3,5,6]

4. 麵包屑導航(從節點追溯到根)

function getBreadcrumb(array $flatData, int $targetId): array
{
    $map = array_column($flatData, null, 'id'); // id => row
    $path = [];
    $currentId = $targetId;
    while ($currentId && isset($map[$currentId])) {
        $node = $map[$currentId];
        $path[] = ['id' => $node['id'], 'name' => $node['name']];
        $currentId = $node['pid'];
    }
    return array_reverse($path);
}

$breadcrumb = getBreadcrumb($categories, 5);
// [電子產品, 手機, iPhone]

五、效能比較(10,000 筆測試)

演算法時間記憶體遞迴深度限制
遞迴建樹~45 ms~8 MB受限於 xdebug.max_nesting_level (預設 256)
單次遍歷 O(n)~3 ms~6 MB無限制

六、資料庫層面優化

  • 遞迴 CTE (MySQL 8.0+, PostgreSQL):WITH RECURSIVE cte AS (SELECT ... UNION ALL SELECT ... FROM cte JOIN ...) 直接在 SQL 取得樹或路徑。
  • Closure Table:額外儲存所有祖先-後代關係,查詢子樹/路徑極快,寫入稍複雜。
  • Nested Set / MPTT:左/右值編碼,查詢子樹極快,但移動節點成本高。

結語

多級分類樹狀結構生成,**資料量小用遞迴清晰易維護,資料量大用單次遍歷 O(n) 高效能**。掌握樹的遍歷(深度優先/廣度優先)、子樹收集、路徑追溯等核心操作,並結合資料庫層面優化(CTE、Closure Table),即可輕鬆應對無限級分類的各種業務需求。

copyright © 萬盛學電腦網 all rights reserved