Обход N-арного дерева в ширину

Question

Я кодирую N-арное представление дерева иерархий файловой системы, которое содержит некоторую информацию о каталогах / файлах. Каждый узел в дереве состоит из родительского узла и списка его дочерних элементов (если есть) и содержится в отдельном объекте дерева. Насколько я знаю, это не самый красноречивый способ реализации дерева, но я достаточно глубоко погружен в проект, в который возвращаться не стоит.

public class TreeNode {

    private FileSystemEntry data;
    private TreeNode parent;
    private ArrayList<TreeNode> children;
    private boolean directory; //separates files from folders (files have no children) 

Древовидная структура определяется как отдельный объект, так как там будет несколько деревьев.

public class DirectoryTree {

    private TreeNode Root;
    private int numNodes;
    private TreeNode Focus;

Я понимаю, что мне нужно будет использовать очередь для добавления каждого узла, пока я пересекаю его дочерние элементы (или что-то подобное).

Вот первое рекурсивное решение глубины, которое печатает имена каждого файла / каталога, просто для справки.

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

}

Я чувствую, что это должна быть только небольшая модификация, чтобы сначала углубиться в глубину, но я не могу обойти это

Answer 1

Сначала создайте очередь только с корневым узлом, обрабатывайте ее до тех пор, пока она не станет пустой. Чтобы сначала обработать вывод узла, а затем добавить все его дочерние элементы в очередь:

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