在不使用二叉树或递归的情况下遍历文件系统 [英] Iterate through a fileSystem without using Binary tree or recursion

问题描述

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

I have seen to similar questions here on this topic but none really helped me grasp the steps to solve this.

给定一个队列和一个 rootNode ，我如何遍历它?我首先明白我必须将我开始的节点加入队列，但我对如何实现 next() 方法感到困惑.也必须是广度优先遍历.

Given a queue, and a rootNode , how can I iterate through it? I understand first I have to enqueue the node I start with, but I am confused on how to implement the next() method. Also it has to be breadth-first traversal.

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

for the next() method I have this:

 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();

如果我只有一个文件目录，它似乎可以工作.另外，我正在寻找伪代码而不是代码.我只是对自己是否走在正确的道路上感到困惑.

It seems to work if I have a single file directory. Also, I am looking for a pseucode not the code. I am just confused on whether I am on the right path or not.

推荐答案

如果由于某种原因，你坚持使用非递归解决方案，虽然 FileVisitor 在 Java 中肯定是这样的，广度优先搜索可以非递归实现.

If, for some reason, you insist on non recursive solution, although FileVisitor is definitely way to go with this in Java, breadth first search can be implemented non recursively.

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

This is general definition, marking is used to avoid circular referencing although you wont have that in this case:

• 将目录的根加入队列并将根标记为已发现
• 当队列不为空时
• 出队和进程元素
• 发现相邻的边缘 - 孩子
• 对于每个孩子，如果尚未标记并且是一个目录，则标记和队列

要获得孩子，您需要:String[] 目录 = file.list().确保您正在排队目录而不是文件调用 file.isDirectory() 并仅将目录入队.

To get children you need: String[] directories = file.list(). To make sure you are queuing directories and not files call file.isDirectory() and enqueue only directories.

您无需在排队前进行标记，因为您不会在目录之间进行循环引用.

You do not need to do marking before queuing as you won't have circular reference between directories.

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

Here is recursive breadth first search, you can modify it into iterative with the pseudo code above.

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);
  }
}

这篇关于在不使用二叉树或递归的情况下遍历文件系统的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！