Two traversal methods in Node – depth first and breadth first

In traversal of tree structure, it can be divided into pre-order, mid-order and follow-up in order, and depth-first and breadth-first in traversal mode. This article realizes recursive deletion of directory structure in NodeJS by using pre-order depth-first and pre-order breadth-first, and experiences traversal of tree structure. This article will use a lot of NodeJS core module fs method, you can through NodeJS file operation – fs basic use to understand the method and usage of fs module used in the article.

Sequential depth-first implements recursive deletion of file directories

1. Implementation of synchronization

The function we want to implement takes the path to the root folder to be deleted, which will be deleted after executing the function.

Const fs = require(const fs = require("fs");
const path = require("path"); // Depth-first sync deletes foldersfunctionRmDirDepSync (p) {// Get the Stats object of the root folderlet statObj = fs.statSync(p); // Check if the folder is a folderif (statObj.isdirectory ()) {// Look inside the folderlet dirs= fs.readdirSync(p); // Concatenate internal files and folders into the correct pathdirs= dirs.map(dir => path.jion(p, dir)); // loop recursive processingdirsInside each file or folderfor (let i = 0; i < dirs.length; i++) {
            rmDirDepSync(dirs[i]); } // Delete the folder fs.rmdirsync (p) after the processing is complete; }else{// Delete fs.unlinksync (p); } // call rmDirDepSync("a");Copy the code

The above code passes a when calling rmDirDepSync, checks whether a is a folder, deletes the file directly if not, and looks at the file directory if not, uses map to concatenate the root file path to the name of each member, and returns a set of valid paths, loops through the set and recurses to each item, and repeats the operation. Finally, delete all files and folders in the root folder, and delete the root folder.

2. Asynchronous callback implementation

Synchronous implementation will block the execution of the code, each time to execute a file operation, must be completed after the execution of the next line of code, compared to synchronous, asynchronous way performance is better, we use asynchronous callback to achieve recursive deletion of the file directory function.

The function takes two arguments. The first argument is also the path to the root folder. The second argument is a callback function that is executed after the file directory has been deleted.

Const fs = require(const fs = require("fs");
const path = require("path"); // Depth-first asynchronous (callback function) delete folderfunctionRmDirDepCb (p, callback) {fs.stat(p, (err,statObj) => {// Check whether the directory is a folderif (statObj.isdirectory ()) {fs.readdir(p, (err,dirs) => {// Concatenate folder members into a collection of valid pathsdirs= dirs.map(dir => path.join(p, dir)); The next method is used to check each path in the collectionfunctionNext (index) {// Delete the upper directory if all members are checked and deletedif (index === dirs.length) returnfs.rmdir(p, callback); // Perform recursion on each file or folder under the path, calling back to recursive next to check for the next item in the path set rmDirDepCb(dirs[index], () => next(index + 1));
                }
                next(0);
            });
        } else{// Delete fs.unlink(p, callback); }}); // call rmDirDepCb("a", () => {
    console.log("Deletion completed"); }); // Delete completedCopy the code

The above method also follows the depth-first approach, and the main idea is the same as synchronous. The implementation of asynchronous callback is more abstract, not by looping through the path of each member of the folder, but by calling next and recursively executing next and maintaining the index variable when the file is successfully deleted.

3. Asynchronous Promise implementation

In the asynchronous callback implementation, there are many levels of nested callback, which can be confusing to code readability and maintainability. In the ES6 specification, promises were introduced to solve the problem of “callback hell,” so we use promises as well.

The argument to the function is the path to the root folder to delete. This time the argument is not needed because the logic in the callback can be executed by chain-calling the then method after calling the function.

Const fs = require(const fs = require("fs");
const path = require("path"); // Depth-first asynchronous (Promise) delete foldersfunction rmDirDepPromise(p) {
    returnNew Promise((resolve, reject) => {fs.stat(p, (err,))statObj) => {// Check whether the directory is a folderif (statObj.isdirectory ()) {fs.readdir(p, (err,dirs) => {// Concatenate folder members into a collection of valid pathsdirs= dirs.map(dir => path.join(p, dir)); // Convert all paths to promisesdirs= dirs.map(dir => rmDirDepPromise(dir)); // Delete the parent directory promise.all ()dirs).then(() => fs.rmdir(p, resolve));
                });
            } else{// delete fs.unlink(p, resolve); }}); }); // call rmDirDepPromise("a").then(() => {
    console.log("Deletion completed"); }); // Delete completedCopy the code

Copy the code

Unlike the asynchronous callback function, which returns a Promise instance directly when rmDirDepPromise is called, resolve is called directly when a file is deleted or a folder is deleted successfully. All can be used to monitor the deletion status of these members. If they are all successful, then call the then of Primise. All to directly delete the directory at the upper level.

4, asynchronous async/await implementation

The Promise version improves the readability of the code compared to the asynchronous callback version, but the implementation logic is still abstract and not as readable as synchronous code. If you want to achieve both performance and readability, you can use async/await in THE ES7 standard to achieve this.

Since the async function returns a Promise instance, the argument only needs to be passed the path to the deleted root folder.

Const fs = require(const fs = require("fs");
const path = require("path");
const { promisify } = require("util"); // Convert the asynchronous methods used in the FS module to Primise conststat = promisify(fs.stat);
const readdir = promisify(fs.readdir);
const rmdir = promisify(fs.rmdir);
const unlink = promisify(fs.unlink);

// 先序深度优先异步（async/await）删除文件夹
async functionRmDirDepAsync (p) {// Get the Stats object for the incoming pathlet statObj = await stat(p); // Check whether the directory is a folderif (statObj.isdirectory ()) {// If it is a folder, view the internal memberslet dirs= await readdir(p); // Concatenates folder members into a collection of valid pathsdirs= dirs.map(dir => path.join(p, dir)); // Loop set recursive rmDirDepAsync processes all membersdirs= dirs.map(dir => rmDirDepAsync(dir)); // When all members have successfully await Promise. All (dirs); // Delete the folder await rmdir(p); }else{// delete await unlink(p); } // call rmDirDepAsync("a").then(() => {
    console.log("Deletion completed"); }); // Delete completedCopy the code

In recursive rmDirDepAsync, all the members inside the subfolder must be deleted successfully before the subfolder is deleted. In unlink deleting files, the Promise execution must wait for the file deletion to complete, so we also need await. All asynchronous promises before recursion can be completed only after the execution of the asynchronous Promise within recursion is completed, so all operations involving asynchracy are waiting with await.

Sequential breadth first to achieve recursive deletion of file directories

In the breadth-first implementation, synchronous, asynchronous callback, and asynchronous async/await are implemented separately. Since there are no asynchronous operations when concatenating storage path arrays, it doesn’t make much sense to use promises alone.

1. Implementation of synchronization

The parameter is the path to the root folder. The internal FS methods also use synchronous methods.

Const fs = require(const fs = require("fs");
const path = require("path"); // Delete folders synchronously firstfunction rmDirBreSync(p) {
    letpathArr = [p]; // Create an array of storage paths. By default, store the root pathletindex = 0; // The index used to store the retrieved array membersletcurrent; // If the current index item can be found in the array, the body of the loop is executed and the item is stored to currentwhile((current = arr[index++])) {// get the Stats object of the path currently fetched from the arraylet statObj = fs.statSync(current); // If it is a folder, the contents are readif (statObj.isDirectory()) {
            let dirs= fs.readdir(current); // Process the obtained member path as a valid pathdirs= dirs.map(dir => path.join(current, dir)); PathArr = [...pathArr,...dirs]; pathArr = [...pathArr,...dirs]; }} // reverse loop pathArrfor (let i = pathArr.length - 1; i >= 0; i--) {
        letpathItem = pathArr[i]; // Current loop itemlet statObj = fs.statSync(pathItem); // If it is a folder, delete the folder; if it is a file, delete the fileif (statObj.isDirectory()) {
            fs.rmdirSync(pathItem);
        } else{ fs.unlinkSync(pathItem); } // Call rmDirBreSync("a");Copy the code

Through the breadth traversal of the while loop, all paths are stored in the pathArr array in hierarchical order. After the reverse traversal of the number group through for, the path traversed is judged and the corresponding deletion method is called. The items after pathArr are stored in the path of the last layer, and the hierarchy of the path from back to front gradually decreases. So reverse traversal does not result in deleting a non-empty folder.

2. Asynchronous callback implementation

The function takes two arguments, the first being the path to the root folder and the second callback, which is executed after deletion.

Const fs = require(const fs = require("fs");
const path = require("path"); // sequential breadth-first asynchronous (callback function) delete folderfunction rmDirBreCb(p, callback) {
    letpathArr = [p]; // Create an array of storage paths. By default, store the root pathfunctionNext (index) {// If everything is done, the deleted function is calledif (index === pathArr.length) returnremove(); // Retrieve the file path in the arrayletcurrent = arr[index]; Fs. stat(currrent, (err,statObj) => {// Check whether it is a folderif (statObj.isdirectory ()) {fs.readdir(current, (err,dirs) => {// Change the member name of the array to a valid pathdirs= dirs.map(dir => path.join(current, dir)); PathArr = [...pathArr,...dirs]; pathArr = [...pathArr,...dirs]; // Next (index + 1); }); }else{// Next (index + 1); }}); } next(0); // Delete the functionfunction remove() {
        functionNext (index) {// If the deletion is complete, execute the callback functionif (index < 0) returncallback(); // Get the last item of the arrayletcurrent = pathArr[index]; Fs.stat (current, (err,statObj) => {// Delete files or folders directlyif (statObj.isDirectory()) {
                    fs.rmdir(current, () => next(index - 1));
                } else{ fs.unlink(current, () => next(index - 1)); }}); } next(arr.length - 1); } // call rmDirBreCb("a", () => {
    console.log("Deletion completed"); }); // Delete completedCopy the code

The first step is to construct an array of storage paths, and the second step is to reverse delete the corresponding files or folders in the array. To ensure performance, both processes are implemented by recursive next functions and maintaining the variables that store the indexes, rather than through a loop.

In the process of array construction, if the deletion function “remove” is called after the completion of array construction, and the callback is called after the completion of deletion in “remove”, the implementation idea is the same. The judgment conditions are set during recursion. If the recursion is not continued after the completion of array construction or deletion, the corresponding function is directly executed and jumps out.

3, asynchronous async/await implementation

The argument is the path to delete the root folder. Since async eventually returns a Promise instance, no callback is required. The logic after deletion can be implemented by calling then that returns the Promise instance.

Const fs = require(const fs = require("fs");
const path = require("path");
const { promisify } = require("util"); // Convert the asynchronous methods used in the FS module to Primise conststat= promisify(fs.stat); const readdir = promisify(fs.readdir); const rmdir = promisify(fs.rmdir); const unlink = promisify(fs.unlink); Async /await delete folder asyncfunction rmDirBreAsync(p) {
    letpathArr = [p]; // Create an array of storage paths. By default, store the root pathletindex = 0; // Retrieve the index of the path from the array // continue the loop if the item existswhile(index ! == patharr.length) {// Retrieve the current pathletcurrent = pathArr[index]; // Get the Stats objectlet statObj = await stat(current); // Check if it is a folderif (statObj.isdirectory ()) {// View the folder memberslet dirs= await readdir(current); // Change the path set to a valid path setdirs= dirs.map(dir => path.join(current, dir)); // Merge the array of storage paths pathArr = [...pathArr,...dirs]; } index++; }letcurrent; // Delete path // loop out pathwhile((current = patharr.pop ())) {// Get the Stats objectlet statObj = await stat(current); // Delete all files and folders directlyif (statObj.isDirectory()) {
            await rmdir(current);
        } else{ await unlink(current); }} // Call rmDirBreAsync("a").then(() => {
    console.log("Deletion completed"); }); // Delete completedCopy the code

All of the above are written synchronously, but the operation on the file is asynchronous and waits with await, and the creation of an array of paths and reverse deletion is done through a while loop.

conclusion