您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 樹狀結構遍歷三大演算法實作比較

編輯：PHP 綜合知識

前言

檔案系統掃描、分類目錄遞迴、組織架構圖譜等場景都需要遍歷樹狀結構。本文實作並比較三種經典演算法：遞迴深度優先、堆疊模擬深度優先、佇列廣度優先，並附記憶體與效能測試程式碼。

演算法一：遞迴深度優先

function rec_list_files($from = '.') {
    if (!is_dir($from)) return [];
    $files = [];
    if ($dh = opendir($from)) {
        while (false !== ($file = readdir($dh))) {
            if ($file === '.' || $file === '..') continue;
            $path = $from . DIRECTORY_SEPARATOR . $file;
            if (is_file($path)) $files[] = $path;
            $files = array_merge($files, rec_list_files($path)); // 遞迴
        }
        closedir($dh);
    }
    return $files;
}

特點：程式碼最簡潔，但深層目錄易導致堆疊溢位；array_merge 重複複製陣列，效能較差。

演算法二：堆疊模擬深度優先（非遞迴）

function deep_first_list_files($from = '.') {
    if (!is_dir($from)) return false;
    $files = [];
    $dirs = [$from]; // 堆疊
    while (null !== ($dir = array_pop($dirs))) {
        if ($dh = opendir($dir)) {
            while (false !== ($file = readdir($dh))) {
                if ($file === '.' || $file === '..') continue;
                $path = $dir . DIRECTORY_SEPARATOR . $file;
                if (is_dir($path)) $dirs[] = $path; // 壓入堆疊
                else $files[] = $path;
            }
            closedir($dh);
        }
    }
    return $files;
}

特點：避免遞迴深度限制，記憶體佔用僅存放待處理目錄堆疊，效能優於遞迴版。

演算法三：佇列廣度優先（非遞迴）

function breadth_first_files($from = '.') {
    $queue = [rtrim($from, DIRECTORY_SEPARATOR) . DIRECTORY_SEPARATOR];
    $files = [];
    while ($base = array_shift($queue)) {
        if ($handle = opendir($base)) {
            while (false !== ($child = readdir($handle))) {
                if ($child === '.' || $child === '..') continue;
                $full = $base . $child;
                if (is_dir($full)) {
                    $queue[] = $full . DIRECTORY_SEPARATOR; // 入隊
                } else {
                    $files[] = $full;
                }
            }
            closedir($handle);
        }
    }
    return $files;
}

特點：逐層展開，適合需要「最短路徑」或「層級輸出」的場景；佇列在極寬目錄樹下可能佔用大量記憶體。

效能測試框架

function profile($func, $trydir) {
    $mem1 = memory_get_usage();
    $time_start = microtime(true);
    $list = $func($trydir);
    $time = microtime(true) - $time_start;
    $mem2 = memory_get_peak_usage();
    printf("函式: %s | 檔案數: %d | 耗時: %.2fs | 峰值記憶體: %.2f KB\n",
        $func, count($list), $time, ($mem2-$mem1)/1024);
}

profile('rec_list_files', 'D:\www\server');
profile('deep_first_list_files', 'D:\www\server');
profile('breadth_first_files', 'D:\www\server');

選擇指南

場景	推薦演算法	理由
一般檔案掃描、目錄樹輸出	堆疊深度優先	記憶體穩定、無遞迴限制、實作簡單
尋找最近檔案、層級式 UI 渲染	佇列廣度優先	天然按層級順序產出
極深但窄的目錄結構（如節點式儲存）	遞迴深度優先	程式碼最短，深度通常不超過 PHP 限制
需平行處理、分散式掃描	廣度優先	佇列易於拆分為多 Worker 消費

現代 PHP 最佳實務

使用 RecursiveDirectoryIterator + RecursiveIteratorIterator 內建 SPL 類別，自動處理迭代、過濾、排序。
搭配 FilterIterator 實現自訂過濾（如僅列出 .jpg）。
大量檔案時啟用 Generator (yield) 逐個產出，避免一次載入全部路徑至記憶體。