Нерекурсивный (итеративный) обход дерева на примере получения плоского списка всех файлов внутри папки

база знаний
, ,
#1

Всем привет!

Пришлось недавно решать задачу синхронизации файлов между ftp-сервером и git-репозиторием, в рамках чего нужно было сколлектить файлы. Сам код отправки возможно разрешат выложить потом. А сейчас про алгоритм получения списка файлов для отправки.

Идея простая: обойти дерево и пути всех файлов сложить в плоский список. Но от рекурсии решили отказаться на всякий случай. Вряд ли бы достигли ее дна, но рисковать не хотелось ввиду огромной и неизвестной структуры папок на ftp, поэтому решили сразу сделать итеративный обход.

И я бы хотел поделиться примером алгоритма итеративного обхода дерева папок на примера коллекта файлов на локальной машине:

"use strict"

var fs = require("fs");
var path = require("path");

var traversal = root => {
    var files = [];
    var folders = [root];

    while (folders.length != 0) {

        var folder = folders.shift();
        var fileNames = fs.readdirSync(folder);

        for (var fileName of fileNames) {
            var filePath = path.resolve(folder, fileName);
            if (fs.statSync(filePath).isDirectory()) {
                folders.push(filePath);
            } else {
                files.push(filePath);
            };
        };
    };
    return files;
};

var main = module.exports.main = () => traversal(process.cwd());

if (require.main === module) main();

Суть простая:

  • создается итерируемый список folders с изначально одним элементом - корневой папкой
  • в цикле из итерируемого списка выталкивается первая папка, которая анализируется
  • в цикле крутится код, который проверяет, что если элемент внутри папки является папкой, то она добавляется в конец итерируемого списка папок, а если файлом - то в плоский список файлов.
  • критерием окончания цикла является отсутствие папок в итерируемом списке (все папки проверены)

Такой алгоритм обхода дерева называется обход в ширину.

Оригинал на гитхабе.

1 лайк