使用承诺评估递归树路径的顺序

Question

这段代码声称首先使用目录进行处理，然后递归处理子目录。但顺序不会是目录 A 目录 A/子目录 C 目录 B 。A 和 B 是根目录的子项

const {join} = require('path');
const {promisify} = require('util');
const fs = require('fs');
const readdir = promisify(fs.readdir);
const stat = promisify(fs.stat);
async function $readDir (dir, acc = []) {
await Promise.all((await readdir(dir)).map(async file => {
file = join(dir, file);
return (await stat(file)).isDirectory() && acc.push(file) && 
$readDir(file, acc);
}));
return acc;
}

顺序似乎是 root：/dirA root：/dirb root：/dirA/dirC 在应许树中，内在的人首先得到满足 最后的顺序是吗？

Answer 1

您正在寻找的算法称为BFS或"广度优先搜索"。它不仅适用于目录，也适用于一般图形遍历。

并不是说这通常不是递归算法。

这个想法是在一个回合中访问每个级别，并将您从队列中的下一个级别找到的所有内容推送，然后处理该队列：

const { join } = require('path');
const fs = require('fs').promises;
async function readdirRecursive (dir, acc = []) {
var queue = [dir];
while(queue.length > 0) {
var next = queue.shift();
// this code does this sequentially and not concurrently
// if you want to make multiple fs calls then you can by storing
// levels and doing the call once - per - level, but you already had
// that
if (!(await fs.stat(file)).isDirectory()) {
return; // file, return
}
// put code that does something with dir here
const files = await fs.readdir(next);
// add all the new candidates
queue.push(...files.map(f => path.join(next, f)); 
}
}

Answer 2

所有映射到子目录数组的函数调用都同时运行，如果你只是推送到累加器数组，则根本没有保证的顺序。

要解决此问题，请按顺序遍历目录：

async function readDirRecursive(dir, acc = []) {
for (const file of await readdir(dir)) {
const path = join(dir, file);
if ((await stat(path)).isDirectory()) {
acc.push(path);
await readDirRecursive(path, acc);
}
}
return acc;
}

或者只是不使用共享累加器，而是按照您想要的顺序正确连接并发遍历的结果：

async function readDirRecursive(dir) {
const paths = await Promise.all((await readdir(dir)).map(async file => {
const path = join(dir, file);
if ((await stat(path)).isDirectory())
return [path, ...await readDirRecursive(path, acc)];
else
return [];
});
return [].concat(...paths);
}