PHP 樹形結構非遞歸實現：父節點/子節點鏈接數組構建算法

問題與思路

傳統遞歸構建樹形結構在深度較大時易導致棧溢出，且性能一般。本文提供**非遞歸、基於引用賦值**的 O(n) 算法，一次遍歷即可構建父節點樹或子節點樹。

核心代碼

1. 構建父節點樹 find_parent()

function find_parent($ar, $id='id', $pid='pid') {
    // 步驟1: 建立 ID -> 節點映射表
    foreach ($ar as $v) $t[$v[$id]] = $v;
    
    // 步驟2: 遍歷建立父節點引用
    foreach ($t as $k => $item) {
        if ($item[$pid]) {
            // 關鍵：使用引用賦值 & 避免數據複製
            if (!isset($t[$item[$pid]]['parent'][$item[$pid]])) {
                $t[$item[$id]]['parent'][$item[$pid]] = &$t[$item[$pid]];
            }
        }
    }
    return $t;
}

2. 構建子節點樹 find_child()

function find_child($ar, $id='id', $pid='pid') {
    foreach ($ar as $v) $t[$v[$id]] = $v;
    
    foreach ($t as $k => $item) {
        if ($item[$pid]) {
            // 將當前節點作為子節點掛載到父節點
            $t[$item[$pid]]['child'][$item[$id]] = &$t[$k];
        }
    }
    return $t;
}

測試數據與輸出

$data = array(
    array('ID'=>1, 'PARENT'=>0, 'NAME'=>'祖父'),
    array('ID'=>2, 'PARENT'=>1, 'NAME'=>'父親'),
    array('ID'=>3, 'PARENT'=>1, 'NAME'=>'叔伯'),
    array('ID'=>4, 'PARENT'=>2, 'NAME'=>'自己'),
    array('ID'=>5, 'PARENT'=>4, 'NAME'=>'兒子'),
);

$c = find_child($data, 'ID', 'PARENT');
print_r($c);

輸出結構

Array
(
    [1] => Array
        (
            [ID] => 1
            [PARENT] => 0
            [NAME] => 祖父
            [child] => Array
                (
                    [2] => Array
                        (
                            [ID] => 2
                            [PARENT] => 1
                            [NAME] => 父親
                            [child] => Array
                                (
                                    [4] => Array
                                        (
                                            [ID] => 4
                                            [PARENT] => 2
                                            [NAME] => 自己
                                            [child] => Array
                                                (
                                                    [5] => Array
                                                        (
                                                            [ID] => 5
                                                            [PARENT] => 4
                                                            [NAME] => 兒子
                                                        )
                                                )
                                        )
                                )
                        )
                    [3] => Array
                        (
                            [ID] => 3
                            [PARENT] => 1
                            [NAME] => 叔伯
                        )
                )
        )
    // ... 其餘節點同理包含 child 結構
)

算法優勢分析

關鍵技術點解析

1. 哈希映射表：$t[$v[$id]] = $v 實現 O(1) 節點查找
2. 引用賦值 (&)：子節點/父節點指向同一內存地址，修改同步，節省內存
3. 單次遍歷：無需遞歸調用，適合超大數據集
4. 鍵名保留：結果數組以 ID 為鍵，便於直接訪問任意節點

應用場景擴展

• 無限級分類（商品分類、評論回覆）
• 組織架構樹（部門、員工）
• 菜單權限樹
• 文件系統目錄結構

注意事項

• 輸入數組必須為鄰接列表格式（每行含 id、pid）
• 根節點 pid 為 0 或 null
• 返回數組包含**所有節點**，每個節點掛載了 parent/child 子樹，非單一根樹
• 若需單一根樹，可篩選 $item[$pid] == 0 的節點