在不使用二叉树或递归的情况下遍历文件系统

Question

我在这里看到过关于此主题的类似问题，但 none 确实帮助我掌握了解决此问题的步骤。

给定一个队列和一个 rootNode ，我如何遍历它？我首先了解我必须将我开始的节点排入队列，但我对如何实现 next() 方法感到困惑。而且必须是广度优先遍历。

对于 next() 方法，我有这个：

 public File next(){
    while(the peek() is a directory ("parent"){
      use lists() to return the array of files
      iterate thru those and add to queue
      remove the first node
     }
return peek();

如果我只有一个文件目录，它似乎可以工作。另外，我正在寻找伪代码而不是代码。我只是在迷茫我是否在正确的道路上。

Answer 1

如果出于某种原因，您坚持非递归解决方案，尽管 FileVisitor 绝对是 Java 中的解决方案，广度优先搜索可以非递归实现。

这是一般定义，标记用于避免循环引用，尽管在这种情况下您不会使用它：

排队目录的根并将根标记为已发现
当队列不为空时
出列和处理元素
发现相邻边 - children
对于每个 child，如果尚未标记并且是一个目录，则标记并排队

要获得 children，您需要：String[] directories = file.list()。确保您排队的是目录而不是文件调用 file.isDirectory() 并仅将目录加入队列。

排队前不需要做标记，目录之间不会有循环引用。

编辑：

这里是递归广度优先搜索，可以用上面的伪代码修改成迭代

import java.io.File;
import java.util.LinkedList;
import java.util.Queue;

public class BFSRecursive {

public static void main(String[] args) {

    File file = new File("D:/Tomcat");

    Queue<File> files = new LinkedList<>();
    files.add(file);
    bfs(files);

}

private static void bfs(Queue<File> files) {

    if (files.isEmpty())
        return;

    File file = files.poll();
    System.out.println(file.getName());

    String[] directories = file.list();

    for(String child: directories) {
        File childFile = new File(file.getAbsolutePath() +"/"+ child);

        if (childFile.isDirectory())
            files.add(childFile);
    }

    bfs(files);
  }
}

在不使用二叉树或递归的情况下遍历文件系统

Iterate through a fileSystem without using Binary tree or recursion

java

queue