Node中的兩種遍歷方式-深度優先和廣度優先（附Node刪除檔案例子進行詳解）

樹的基本概念

樹（Tree）是 n 個結點的有限集， n 為 0 時，稱為空樹，在任意一棵非空樹中有且僅有一個特定的被稱為根（Root）的結點，當 n 大於 1 時，其餘結點可分為 m 個互不相交的有限集 T1 、 T2 、 ...... 、 Tm ，其中每一個集合本身又是一棵樹，並且稱為 SubTree ，即根的子樹。

需要強調的是， n>0 時根結點是唯一的，不可能存在多個根結點， m>0 時，子樹的個數沒有限制，但它們一定是互不相交的。

從根開始定義起，根為第一層，根的孩子為第二層，若某結點在第 l 層，則其子樹就在第 l+1 層，其雙親在同一層的結點互為 “堂兄弟”，樹中結點的最大層級數稱為樹的深度（Depth）或高度。

在對樹結構進行遍歷時，按順序可分為先序、中序和後續，按遍歷的方式可分為深度優先和廣度優先，我們這篇文章就通過使用先序深度優先和先序廣度優先來實現 NodeJS 中遞迴刪除目錄結構，體會對樹結構的遍歷，文章中會大量用到 NodeJS 核心模組 fs 的方法，可以通過 ofollow,noindex">NodeJS 檔案操作 —— fs 基本使用 來了解文中用到的 fs 模組的方法及用法。

先序深度優先實現遞迴刪除檔案目錄

深度優先的意思就是在遍歷當前檔案目錄的時候，如果子資料夾內還有內容，就繼續遍歷子資料夾，直到遍歷到最深層不再有資料夾，則刪除其中的檔案，再刪除這個資料夾，然後繼續遍歷它的 “兄弟”，直到內層檔案目錄都被刪除，再刪除上一級，最後根資料夾為空，刪除根資料夾。

1、同步的實現

我們要實現的函式引數為要刪除的根資料夾的路徑，執行函式後會刪除這個根資料夾。

深度優先 —— 同步

// 引入依賴模組
const fs = require("fs");
const path = require("path");

// 先序深度優先同步刪除資料夾
function rmDirDepSync(p) {
// 獲取根資料夾的 Stats 物件
let statObj = fs.statSync(p);

// 檢查該資料夾的是否是資料夾
if (statObj.isDirectory()) {
// 檢視資料夾內部
let dirs = fs.readdirSync(p);

// 將內部的檔案和資料夾拼接成正確的路徑
dirs = dirs.map(dir => path.jion(p, dir));

// 迴圈遞迴處理 dirs 內的每一個檔案或資料夾
for (let i = 0; i < dirs.length; i++) {
rmDirDepSync(dirs[i]);
}

// 等待都處理完後刪除該資料夾
fs.rmdirSync(p);
} else {
// 若是檔案則直接刪除
fs.unlinkSync(p);
}
}

// 呼叫
rmDirDepSync("a");複製程式碼

上面程式碼在呼叫 rmDirDepSync 時傳入 a ，先判斷 a 是否是資料夾，不是則直接刪除檔案，是則檢視檔案目錄，使用 map 將根檔案路徑拼接到每一個成員的名稱前，並返回合法的路徑集合，迴圈這個集合並對每一項進行遞迴，重複執行操作，最終實現刪除根資料夾內所有的檔案和資料夾，並刪除根資料夾。

2、非同步回撥的實現

同步的實現會阻塞程式碼的執行，每次執行一個檔案操作，必須在執行完畢之後才能執行下一行程式碼，相對於同步，非同步的方式效能會更好一些，我們下面使用非同步回撥的方式來實現遞迴刪除檔案目錄的函式。

函式有兩個引數，第一個引數同樣為根資料夾的路徑，第二個引數為一個回撥函式，在檔案目錄被全部刪除後執行。

深度優先 —— 非同步回撥

// 引入依賴模組
const fs = require("fs");
const path = require("path");

// 先序深度優先非同步（回撥函式）刪除資料夾
function rmDirDepCb(p, callback) {
// 獲取傳入路徑的 Stats 物件
fs.stat(p, (err, statObj) => {
// 判斷路徑下是否為資料夾
if (statObj.isDirectory()) {
// 是資料夾則檢視內部成員
fs.readdir(p, (err, dirs) => {
// 將資料夾成員拼接成合法路徑的集合
dirs = dirs.map(dir => path.join(p, dir));

// next 方法用來檢查集合內每一個路徑
function next(index) {
// 如果所有成員檢查並刪除完成則刪除上一級目錄
if (index === dirs.length) return fs.rmdir(p, callback);

// 對路徑下每一個檔案或資料夾執行遞迴，回撥為遞迴 next 檢查路徑集合中的下一項
rmDirDepCb(dirs[index], () => next(index + 1));
}
next(0);
});
} else {
// 是檔案則直接刪除
fs.unlink(p, callback);
}
});
}

// 呼叫
rmDirDepCb("a", () => {
console.log("刪除完成");
});

// 刪除完成複製程式碼

上面方法也遵循深度優先，與同步相比較主要思路是相同的，非同步回撥的實現更為抽象，並不是通過迴圈去處理的資料夾下的每個成員的路徑，而是通過呼叫 next 函式和在成功刪除檔案時遞迴執行 next 函式並維護 index 變數實現的。

3、非同步 Promise 的實現

在非同步回撥函式的實現方式中，回撥巢狀層級非常多，這在對程式碼的可讀性和維護性上都造成困擾，在 ES6 規範中，Promise 的出現就是用來解決 “回撥地獄” 的問題，所以我們也使用 Promise 來實現。

函式的引數為要刪除的根資料夾的路徑，這次之所以不需要傳 callback 引數是因為 callback 中的邏輯可以在呼叫函式之後鏈式呼叫 then 方法來執行。

// 引入依賴模組
const fs = require("fs");
const path = require("path");

// 先序深度優先非同步（Promise）刪除資料夾
function rmDirDepPromise(p) {
return new Promise((resolve, reject) => {
// 獲取傳入路徑的 Stats 物件
fs.stat(p, (err, statObj) => {
// 判斷路徑下是否為資料夾
if (statObj.isDirectory()) {
// 是資料夾則檢視內部成員
fs.readdir(p, (err, dirs) => {
// 將資料夾成員拼接成合法路徑的集合
dirs = dirs.map(dir => path.join(p, dir));

// 將所有的路徑都轉換成 Promise
dirs = dirs.map(dir => rmDirDepPromise(dir));

// 陣列中路徑下所有的 Promise 都執行了 resolve 時，刪除上級目錄
Promise.all(dirs).then(() => fs.rmdir(p, resolve));
});
} else {
// 是檔案則直接刪除
fs.unlink(p, resolve);
}
});
});
}

// 呼叫
rmDirDepPromise("a").then(() => {
console.log("刪除完成");
});

// 刪除完成
複製程式碼

複製程式碼

與非同步回撥函式的方式不同的是在呼叫 rmDirDepPromise 時直接返回了一個 Promise 例項，而在刪除檔案成功或在刪除資料夾成功時直接呼叫了 resolve ，在一個子資料夾下直接將這些成員通過遞迴 rmDirDepPromise 都轉換為 Promise 例項，則可以用 Primise.all 來監聽這些成員刪除的狀態，如果都成功再呼叫 Primise.all 的 then 直接刪除上一級目錄。

4、非同步 async/await 的實現

Promise 版本相對於非同步回撥版本從程式碼的可讀性上有所提升，但是實現邏輯還是比較抽象，沒有同步程式碼的可讀性好，如果想要 “魚” 和 “熊掌” 兼得，既要效能又要可讀性，可以使用 ES7 標準中的 async/await 來實現。

由於 async 函式的返回值為一個 Promise 例項，所以引數只需要傳被刪除的根資料夾的路徑即可。

深度優先 —— 非同步 async/await

// 引入依賴模組
const fs = require("fs");
const path = require("path");
const { promisify } = require("util");

// 將用到 fs 模組的非同步方法轉換成 Primise
const stat = promisify(fs.stat);
const readdir = promisify(fs.readdir);
const rmdir = promisify(fs.rmdir);
const unlink = promisify(fs.unlink);

// 先序深度優先非同步（async/await）刪除資料夾
async function rmDirDepAsync(p) {
// 獲取傳入路徑的 Stats 物件
let statObj = await stat(p);

// 判斷路徑下是否為資料夾
if (statObj.isDirectory()) {
// 是資料夾則檢視內部成員
let dirs = await readdir(p);

// 將資料夾成員拼接成合法路徑的集合
dirs = dirs.map(dir => path.join(p, dir));

// 迴圈集合遞迴 rmDirDepAsync 處理所有的成員
dirs = dirs.map(dir => rmDirDepAsync(dir));

// 當所有的成員都成功
await Promise.all(dirs);

// 刪除該資料夾
await rmdir(p);
} else {
// 是檔案則直接刪除
await unlink(p);
}
}

// 呼叫
rmDirDepAsync("a").then(() => {
console.log("刪除完成");
});

// 刪除完成複製程式碼

在遞迴 rmDirDepAsync 時，所有子資料夾內部的成員必須都刪除成功，才刪除這個子資料夾，在使用 unlink 刪除檔案時，必須等待檔案刪除結束才能讓 Promise 執行完成，所以也需要 await ，所有遞迴之前的非同步 Promise 都需要在遞迴內部的非同步 Promise 執行完成後才能執行完成，所以涉及到非同步的操作都使用了 await 進行等待。

先序廣度優先實現遞迴刪除檔案目錄

廣度優先的意思是遍歷資料夾目錄的時候，先遍歷根資料夾，將內部的成員路徑一個一個的存入陣列中，再繼續遍歷下一層，再將下一層的路徑都存入陣列中，直到遍歷到最後一層，此時陣列中的路徑順序為第一層的路徑，第二層的路徑，直到最後一層的路徑，由於要刪除的資料夾必須為空，所以刪除時，倒序遍歷這個陣列取出路徑進行檔案目錄的刪除。

在廣度優先的實現方式中同樣按照同步、非同步回撥、和 非同步 async/await 這幾種方式分別來實現，因為在拼接儲存路徑陣列的時候沒有非同步操作，所以單純使用 Promise 沒有太大的意義。

1、同步的實現

引數為根資料夾的路徑，內部的 fs 方法同樣都使用同步方法。

廣度優先 —— 同步

// 引入依賴模組
const fs = require("fs");
const path = require("path");

// 先序廣度優先同步刪除資料夾
function rmDirBreSync(p) {
let pathArr = [p]; // 建立儲存路徑的陣列，預設存入根路徑
let index = 0; // 用於儲存取出陣列成員的索引
let current; // 用於儲存取出的成員，即路徑

// 如果陣列中能找到當前指定索引的項，則執行迴圈體，並將該項存入 current
while ((current = arr[index++])) {
// 獲取當前從陣列中取出的路徑的 Stats 物件
let statObj = fs.statSync(current);

// 如果是資料夾，則讀取內容
if (statObj.isDirectory()) {
let dirs = fs.readdir(current);

// 將獲取到的成員路徑處理為合法路徑
dirs = dirs.map(dir => path.join(current, dir));

// 將原陣列的成員路徑和處理後的成員路徑重新解構在 pathArr 中
pathArr = [...pathArr, ...dirs];
}
}

// 逆序迴圈 pathArr
for (let i = pathArr.length - 1; i >= 0; i--) {
let pathItem = pathArr[i]; // 當前迴圈項
let statObj = fs.statSync(pathItem); // 獲取 Stats 物件

// 如果是資料夾則刪除資料夾，是檔案則刪除檔案
if (statObj.isDirectory()) {
fs.rmdirSync(pathItem);
} else {
fs.unlinkSync(pathItem);
}
}
}

// 呼叫
rmDirBreSync("a");複製程式碼

通過 while 迴圈廣度遍歷，將所有的路徑按層級順序存入 pathArr 陣列中，在通過 for 反向遍歷陣列，對遍歷到的路徑進行判斷並呼叫對應的刪除方法， pathArr 後面的項儲存的都是最後一層的路徑，從後向前路徑的層級逐漸減小，所以反向遍歷不會導致刪除非空資料夾的操作。

2、非同步回撥的實現

函式有兩個引數，第一個引數為根資料夾的路徑，第二個為 callback ，在刪除結束後執行。

廣度優先 —— 非同步回撥

// 引入依賴模組
const fs = require("fs");
const path = require("path");

// 先序廣度優先非同步（回撥函式）刪除資料夾
function rmDirBreCb(p, callback) {
let pathArr = [p]; // 建立儲存路徑的陣列，預設存入根路徑

function next(index) {
// 如果已經都處理完，則呼叫刪除的函式
if (index === pathArr.length) return remove();

// 取出陣列中的檔案路徑
let current = arr[index];

// 獲取取出路徑的 Stats 物件
fs.stat(currrent, (err, statObj) => {
// 判斷是否是資料夾
if (statObj.isDirectory()) {
// 是資料夾讀取內部成員
fs.readdir(current, (err, dirs) => {
// 將陣列中成員名稱修改為合法路徑
dirs = dirs.map(dir => path.join(current, dir));

// 將原陣列的成員路徑和處理後的成員路徑重新解構在 pathArr 中
pathArr = [...pathArr, ...dirs];

// 遞迴取出陣列的下一項進行檢測
next(index + 1);
});
} else {
// 如果是檔案則直接遞迴獲取陣列的下一項進行檢測
next(index + 1);
}
});
}
next(0);

// 刪除的函式
function remove() {
function next(index) {
// 如果全部刪除完成，執行回撥函式
if (index < 0) return callback();

// 獲取陣列的最後一項
let current = pathArr[index];

// 獲取該路徑的 Stats 物件
fs.stat(current, (err, statObj) => {
// 不管是檔案還是資料夾都直接刪除
if (statObj.isDirectory()) {
fs.rmdir(current, () => next(index - 1));
} else {
fs.unlink(current, () => next(index - 1));
}
});
}
next(arr.length - 1);
}
}

// 呼叫
rmDirBreCb("a", () => {
console.log("刪除完成");
});

// 刪除完成複製程式碼

在呼叫 rmDirBreCb 時主要執行兩個步驟，第一個步驟是構造儲存路徑的陣列，第二個步驟是逆序刪除陣列中對應的檔案或資料夾，為了保證效能，兩個過程都是通過遞迴 next 函式並維護儲存索引的變數來實現的，而非迴圈。

在構造陣列的過程中如果構造陣列完成後，呼叫的刪除函式 remove ，在 remove 中在刪除完成後，呼叫的 callback ，實現思路是相同的，都是在遞迴時設定判斷條件，如果構造陣列或刪除結束以後不繼續遞迴，而是直接執行對應的函式並跳出。

3、非同步 async/await 的實現

引數為刪除根資料夾的路徑，因為 async 最後返回的是 Promise 例項，所以不需要 callback ，刪除後的邏輯可以通過呼叫返回 Promise 例項的 then 來實現。

廣度優先 —— 非同步 async/await

// 引入依賴模組
const fs = require("fs");
const path = require("path");
const { promisify } = require("util");

// 將用到 fs 模組的非同步方法轉換成 Primise
const stat = promisify(fs.stat);
const readdir = promisify(fs.readdir);
const rmdir = promisify(fs.rmdir);
const unlink = promisify(fs.unlink);

// 先序廣度優先非同步（async/await）刪除資料夾
async function rmDirBreAsync(p) {
let pathArr = [p]; // 建立儲存路徑的陣列，預設存入根路徑
let index = 0; // 去陣列中取出路徑的索引

// 如果存在該項則繼續迴圈
while (index !== pathArr.length) {
// 取出當前的路徑
let current = pathArr[index];

// 獲取 Stats 物件
let statObj = await stat(current);

// 判斷是否是資料夾
if (statObj.isDirectory()) {
// 檢視資料夾成員
let dirs = await readdir(current);

// 將路徑集合更改為合法路徑集合
dirs = dirs.map(dir => path.join(current, dir));

// 合併儲存路徑的陣列
pathArr = [...pathArr, ...dirs];
}
index++;
}

let current; // 刪除的路徑

// 迴圈取出路徑
while ((current = pathArr.pop())) {
// 獲取 Stats 物件
let statObj = await stat(current);

// 不管是檔案還是資料夾都直接刪除
if (statObj.isDirectory()) {
await rmdir(current);
} else {
await unlink(current);
}
}
}

// 呼叫
rmDirBreAsync("a").then(() => {
console.log("刪除完成");
});

// 刪除完成複製程式碼

上面的寫法都是使用同步的寫法，但對檔案的操作都是非同步的，並使用 await 進行等待，在建立路徑集合的陣列和倒序刪除的過程都是通過 while 迴圈實現的。

總結

深度優先和廣度優先的兩種遍歷方式應該是考慮具體場景選擇最適合的方式使用，上面這麼多實現遞迴刪除檔案目錄的方法中，重點在於體會深度遍歷和廣度遍歷的不同，其實在類似於遞迴刪除檔案目錄的這種功能使用深度優先更適合一些。