Iterate through a fileSystem without using Binary tree or recursion

Question

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

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.

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.

Answer 1

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:

• Enqueue root of directories and mark root as discovered
• while queue is not empty
• dequeue and process element
• discover adjacent edges - children
• for every child, if not marked already and is a directory, mark and queue

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.

Edit:

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