I'm coding up an N-ary tree representation of file system hierarchies, which contains some information about the directories/files. Each node in the tree consists of a parent node, and a list of its children (if any) and is contained within a seperate Tree object. This isn't the most eloquent method of implementing a tree as far as i'm aware, but I'm far enough into the project where it isn't worth going back.
public class TreeNode {
private FileSystemEntry data;
private TreeNode parent;
private ArrayList<TreeNode> children;
private boolean directory; //separates files from folders (files have no children)
The tree structure is defined as its own separate object, since there will be several trees.
public class DirectoryTree {
private TreeNode Root;
private int numNodes;
private TreeNode Focus;
I understand that I will need to use a queue to add each node to while i traverse its children (or something similar).
Here's a Depth first recursive solution that prints the names of each file/directory, just for reference.
public void PrintTreeNames() {
PrintTreeNames(this.Root);
}
private void PrintTreeNames(TreeNode n) {
if (!n.isDirectory()) {
System.out.println(n.getData().getName());
} else {
for (int i = 0; i < n.getChildren().size(); i++) {
PrintTreeNames(n.getChildren().get(i));
}
System.out.println(n.getData().getName());
}
}
I feel like it should only be a small modification to get from depth first to breadth first but I can't seem to get my head round it
Create the queue initially with just the root node, process the queue until it is empty. To process a node output it first, then add all of it's children to the queue:
public void PrintTreeNames() {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(this.root);
TreeNode current;
while ((current = queue.poll()) != null) {
PrintTreeNames(current, queue);
}
}
private void PrintTreeNames(TreeNode n, Queue<TreeNode> queue) {
System.out.println(n.getData().getName());
if (n.isDirectory()) {
for (int i = 0; i < n.getChildren().size(); i++) {
queue.add(n.getChildren().get(i));
}
}
}