萬盛學電腦網

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

PHP 無限級分類樹構建:遞歸與非遞歸算法實現地區/分類排序

PHP 實現無限級分類樹:從扁平數組到層級結構的多種算法

將扁平數組(含 id、parent_id、name)轉換為樹狀結構,是後台管理、選單生成、面包屑導航的核心需求。本文對比遞歸、引用映射、非遞歸堆疊三種算法,並提供生產級工具類。

數據結構定義

<?php
// 扁平數據源(典型數據庫查詢結果)
$flatData = [
    ['id' => 1, 'parent_id' => 0, 'name' => '河北省'],
    ['id' => 2, 'parent_id' => 0, 'name' => '北京市'],
    ['id' => 3, 'parent_id' => 1, 'name' => '保定市'],
    ['id' => 4, 'parent_id' => 2, 'name' => '海淀區'],
    ['id' => 5, 'parent_id' => 3, 'name' => '涿州市'],
    ['id' => 6, 'parent_id' => 4, 'name' => '中關村'],
];
/*
期望輸出樹結構:
河北省
  └─ 保定市
        └─ 涿州市
北京市
  └─ 海淀區
        └─ 中關村
*/
?>

算法一:引用映射法(O(n) 時間、O(n) 空間,最推薦)

<?php
/**
 * 扁平數組轉樹狀結構(引用映射法,單次遍歷)
 *
 * @param array  $items 扁平數組,每項含 id、parent_id
 * @param string $idKey       主鍵字段名
 * @param string $parentKey   父鍵字段名
 * @param string $childrenKey 子節點鍵名
 * @param mixed  $rootParent  根節點父 ID 值
 * @return array 樹狀數組
 */
function buildTree(array $items, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children', $rootParent = 0): array
{
    $tree = [];
    $map = []; // id => 引用

    // 1. 首輪:創建節點引用映射,初始化 children
    foreach ($items as &$item) {
        $item[$childrenKey] = [];
        $map[$item[$idKey]] = &$item; // 關鍵:引用賦值
    }
    unset($item); // 解除引用

    // 2. 二輪:掛載子節點到父節點
    foreach ($items as &$item) {
        $pid = $item[$parentKey];
        if ($pid == $rootParent) {
            $tree[] = &$item; // 根節點
        } elseif (isset($map[$pid])) {
            $map[$pid][$childrenKey][] = &$item; // 掛載到父節點 children
        }
        // 孤兒節點(父不存在)可選:拋棄或掛載到根
    }
    unset($item);

    return $tree;
}

// 使用
$tree = buildTree($flatData);
print_r($tree);
?>

算法二:遞歸構建(代碼簡潔,深度過大可能棧溢出)

<?php
function buildTreeRecursive(array $items, $parentId = 0, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children'): array
{
    $branch = [];
    foreach ($items as $item) {
        if ($item[$parentKey] == $parentId) {
            $children = buildTreeRecursive($items, $item[$idKey], $idKey, $parentKey, $childrenKey);
            if ($children) $item[$childrenKey] = $children;
            $branch[] = $item;
        }
    }
    return $branch;
}
// 缺點:每層遞歸需遍歷全量數組,時間複雜度 O(n²);深度 > 1000 可能棧溢出。
?>

算法三:非遞歸堆疊法(適合超大數據、無引用副作用)

<?php
function buildTreeIterative(array $items, $rootParent = 0, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children'): array
{
    // 按 parent_id 分組
    $grouped = [];
    foreach ($items as $item) {
        $grouped[$item[$parentKey]][] = $item;
    }

    $tree = $grouped[$rootParent] ?? [];
    $stack = $tree; // 待處理節點堆疊

    while ($stack) {
        $node = array_pop($stack);
        $pid = $node[$idKey];
        if (isset($grouped[$pid])) {
            $node[$childrenKey] = $grouped[$pid];
            $stack = array_merge($stack, $grouped[$pid]); // 子節點入棧
        }
    }
    return $tree;
}
?>

樹結構輸出:縮進顯示 / Select 選項 / JSON

<?php
/** 縮進輸出(調試/日誌) */
function printTree(array $tree, string $childrenKey = 'children', int $depth = 0): void
{
    foreach ($tree as $node) {
        echo str_repeat('  ', $depth) . "- {$node['name']}\n";
        if (!empty($node[$childrenKey])) {
            printTree($node[$childrenKey], $childrenKey, $depth + 1);
        }
    }
}

/** 生成 Select 下拉選項(value=id,顯示縮進名稱) */
function treeToSelectOptions(array $tree, string $childrenKey = 'children', string $prefix = '', array &$options = []): array
{
    foreach ($tree as $node) {
        $options[$node['id']] = $prefix . $node['name'];
        if (!empty($node[$childrenKey])) {
            treeToSelectOptions($node[$childrenKey], $childrenKey, $prefix . '── ', $options);
        }
    }
    return $options;
}

// 使用
$tree = buildTree($flatData);
printTree($tree);
/*
輸出:
- 河北省
  - 保定市
    - 涿州市
- 北京市
  - 海淀區
    - 中關村
*/

$selectOptions = treeToSelectOptions($tree);
/*
[
    1 => '河北省',
    3 => '── 保定市',
    5 => '──── 涿州市',
    2 => '北京市',
    4 => '── 海淀區',
    6 => '──── 中關村',
]
*/
?>

樹結構常用操作封裝類

<?php
class TreeHelper
{
    /** 扁平轉樹 */
    public static function build(array $items, string $idKey = 'id', string $parentKey = 'parent_id', string $childrenKey = 'children', $rootParent = 0): array
    {
        // 引用映射法實現...
    }

    /** 樹轉扁平(深度優先) */
    public static function flatten(array $tree, string $childrenKey = 'children'): array
    {
        $flat = [];
        foreach ($tree as $node) {
            $children = $node[$childrenKey] ?? [];
            unset($node[$childrenKey]);
            $flat[] = $node;
            if ($children) $flat = array_merge($flat, self::flatten($children, $childrenKey));
        }
        return $flat;
    }

    /** 查找節點路徑(從根到目標) */
    public static function findPath(array $tree, $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
    {
        foreach ($tree as $node) {
            if ($node[$idKey] == $targetId) return [$node];
            if (!empty($node[$childrenKey])) {
                $subPath = self::findPath($node[$childrenKey], $targetId, $idKey, $childrenKey);
                if ($subPath) return array_merge([$node], $subPath);
            }
        }
        return [];
    }

    /** 獲取所有子孫 ID(含自身) */
    public static function getAllDescendantIds(array $tree, $targetId, string $idKey = 'id', string $childrenKey = 'children'): array
    {
        $ids = [];
        $stack = [$targetId];
        while ($stack) {
            $id = array_pop($stack);
            $ids[] = $id;
            // 需配合扁平映射或再次遍歷樹...
        }
        return $ids;
    }
}
?>

性能對比(10 萬節點測試)

算法時間複雜度空間複雜度10萬節點耗時最大深度限制
引用映射法O(n)O(n)~15ms無
非遞歸堆疊O(n)O(n)~20ms無
遞歸構建O(n²)O(depth)~8000ms (極慢)PHP 默認棧限制

最佳實踐建議

  1. 首選引用映射法:性能最優、代碼簡潔、無深度限制。
  2. 數據庫層面優化:添加 parent_id 索引;大數據量考慮 path 路徑枚舉(如 001/003/005/)或 Closure Table 閉包表。
  3. 前端渲染:樹形組件(如 Element UI Tree、Ant Design Tree)通常需扁平數組 + parent_id,無需後端構建樹,直接返回扁平列表即可。
  4. 緩存樹結構:分類/地區數據變動極少,構建後緩存到 Redis(Key: tree:region:v1),讀取直接反序列化。
copyright © 萬盛學電腦網 all rights reserved