萬盛學電腦網

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

PHP 無限級分類樹形結構生成:引用賦值法的極致優雅實現

拒絕遞歸:PHP 無限級分類樹構建的引用賦值黑科技

傳統遞歸構建樹形結構存在性能瓶頸(重複遍歷、深度限制、內存開銷)。本文介紹一種基於 PHP 引用賦值的單次遍歷 O(n) 算法,代碼極簡卻極其高效。

核心算法:單次遍歷 + 引用賦值

<?php
function generateTree($items) {
    $tree = [];
    
    foreach ($items as $item) {
        // 關鍵:引用賦值 &$items[$item['id']]
        if (isset($items[$item['pid']])) {
            // 父節點存在:掛載到父節點的 son 屬性
            $items[$item['pid']]['son'][] = &$items[$item['id']];
        } else {
            // 根節點:加入樹根
            $tree[] = &$items[$item['id']];
        }
    }
    
    return $tree;
}

// 測試數據:ID 為鍵名,便於 O(1) 查找父節點
$items = [
    1 => ['id' => 1, 'pid' => 0, 'name' => '安徽省'],
    2 => ['id' => 2, 'pid' => 0, 'name' => '浙江省'],
    3 => ['id' => 3, 'pid' => 1, 'name' => '合肥市'],
    4 => ['id' => 4, 'pid' => 3, 'name' => '長豐縣'],
    5 => ['id' => 5, 'pid' => 1, 'name' => '安慶市'],
];

$tree = generateTree($items);
print_r($tree);
?>

輸出結構

Array
(
    [0] => Array
        (
            [id] => 1
            [pid] => 0
            [name] => 安徽省
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [pid] => 1
                            [name] => 合肥市
                            [son] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 4
                                            [pid] => 3
                                            [name] => 長豐縣
                                        )
                                )
                        )
                    [1] => Array
                        (
                            [id] => 5
                            [pid] => 1
                            [name] => 安慶市
                        )
                )
        )
    [1] => Array
        (
            [id] => 2
            [pid] => 0
            [name] => 浙江省
        )
)

極致精簡版(5 行核心代碼)

<?php
function generateTree($items) {
    foreach ($items as $item) {
        // 引用賦值:將當前節點掛載到父節點的 son[$id] 下
        $items[$item['pid']]['son'][$item['id']] = &$items[$item['id']];
    }
    // 返回虛擬根節點 0 的子節點
    return isset($items[0]['son']) ? $items[0]['son'] : [];
}
?>

核心機制深度解析

關鍵點解釋
數組鍵名為 ID確保 $items[$pid] 為 O(1) 查找,無需遍歷
引用賦值 &父節點持有子節點的引用而非副本,修改同步生效
虛擬根節點 0統一處理頂級節點,無需特殊判斷
單次遍歷時間複雜度 O(n),遞歸法通常 O(n log n) 甚至 O(n²)

樹形數據的遍歷輸出(仍需遞歸)

生成樹結構後,前端渲染或導出仍需遞歸遍歷:

<?php
function renderTree($tree, $level = 0) {
    foreach ($tree as $node) {
        echo str_repeat('  ', $level) . $node['name'] . "\n";
        if (!empty($node['son'])) {
            renderTree($node['son'], $level + 1);
        }
    }
}

renderTree($tree);
/* 輸出:
安徽省
  合肥市
    長豐縣
  安慶市
浙江省
*/
?>

前端渲染建議

  • Vue/React:配合遞歸組件渲染 <TreeNode :node="node" />
  • jQuery:生成巢狀 <ul><li> 結構,配合 CSS 縮進
  • 選中/展開狀態管理:在節點對象添加 expanded、selected 字段

適用場景與限制

適用:行政區劃、商品分類、組織架構、菜單權限、評論回覆等層級不超過 10 層、節點數 < 10 萬的場景
不適用:極深層級(>100)、極大數據量(>100萬)、頻繁增刪改需實時維護樹結構的場景(建議 Closure Table 或物化路徑)

copyright © 萬盛學電腦網 all rights reserved