广度优先 N 叉树遍历

Question

我正在编写文件系统层次结构的 N 叉树表示，其中包含一些关于 directories/files 的信息。树中的每个节点都由一个父节点及其子节点列表（如果有）组成，并且包含在一个单独的 Tree 对象中。据我所知，这不是最 eloquent 实现树的方法，但我已经深入到不值得回头的项目中了。

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;

我知道我需要使用一个队列来添加每个节点，同时我遍历它的子节点（或类似的东西）。

这里有一个深度优先递归的解决方案，打印每个file/directory的名字，仅供参考。

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

广度优先 N 叉树遍历

Breadth-First N-ary tree traversal

java

filesystems

breadth-first-search

n-ary-tree