java - 不使用二叉树或递归来迭代文件系统

Question

我在这里看到过有关此主题的类似问题，但没有一个真正帮助我掌握解决此问题的步骤。

给定一个队列和一个 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 中的解决方案，但广度优先搜索可以非递归方式实现。

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

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

要获取子项，您需要: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);
  }
}