java中泛型树（n元树）的级顺序遍历

Question

（为了避免冗长的解释，我所要寻找的只是java中泛型树（n元树）的级别顺序遍历。提供的代码正常工作，需要级别顺序显示功能。环顾四周一个小时，但找不到通用n元树的参考。如果soemone能帮助我在代码上构建LevelOrderDisplay函数，我将不胜感激，因为它将帮助我理解我遇到的队列错误。谢谢

我一直在尝试在工作中实现Autosys作业计划的树表示。由于每个作业（流程）可以有一个或多个依赖作业，因此我决定使用n元树实现，以便映射流程。我使用java集合来实现同样的目的。我需要执行级别顺序遍历以显示作业依赖关系。首先打印根，然后打印级别1上的所有节点，然后打印级别2上的所有节点，依此类推。

我试图在StackOverflow上搜索一个多小时，但我遇到的大多数示例都是关于二叉树的。我知道我需要使用队列来完成此操作。

从我在研究中得到的，算法应该看起来像：如果这是错误的，请纠正我，如果可能的话，提供一个代码。替代方法也很受欢迎，但我真正要找的是一个简单的泛型树的基本级顺序遍历。

让我们为通用树实现提供一个资源丰富的线程。大部分代码已经在运行。请帮忙。

Algo:

对于每个节点，首先访问该节点，然后将其子节点放入FIFO队列。

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children (first left then right children) to q
    c) Dequeue a node from q and assign it’s value to temp_node

出于某种奇怪的原因，我无法在EclipseIDE中声明队列。我已经导入了java。util.*；我这里遗漏了一些东西，请看下面的错误。

第一次尝试：

Queue<NaryTreeNode> BFSqueue = new LinkedList<NaryTreeNode>();

错误：LinkedList类型不是泛型；不能使用参数对其进行参数化

第二次尝试：

QueueList<NaryTreeNode> BFSqueue = new QueueList<NaryTreeNode>();

错误：-QueueList无法解析为类型

当前树结构供参考：

     root(100)
    /      |       \
  90       50       70
  /        \
20 30   200  300

当前显示功能的输出是预先排序的：100 90 20 30 50 200 300 70我需要一个相同的水平顺序遍历。所需输出。

> 100
> 90 50 70
> 20 30 200 300

如果有人想在他们的机器上运行它并添加级别顺序遍历函数，那么这是一个工作代码。请提供对队列操作的注释解释，因为这正是我遇到的问题。

谢谢

import java.util.*;
import java.io.*;
import java.util.List;

//The node for the n-ary tree
public class NaryTreeNode {
  int data;
  List <NaryTreeNode> nary_list = new ArrayList<NaryTreeNode>();
}


public class NaryTree {

  void display(NaryTreeNode t) {
    if(t==null)
      return;

    System.out.print(t.data + " ");

    for(NaryTreeNode n : t.nary_list) 
          display(n) ;            //Recursive Call
 }


  public static void main(String args[]){

    NaryTree t1 = new NaryTree();

    NaryTreeNode root = new NaryTreeNode();

    root.data = 100;

    NaryTreeNode lev_11 = new NaryTreeNode();   lev_11.data=90;
    NaryTreeNode lev_12 = new NaryTreeNode();   lev_12.data=50;
    NaryTreeNode lev_13 = new NaryTreeNode();   lev_13.data=70;
    NaryTreeNode lev_21 = new NaryTreeNode();   lev_21.data=20;
    NaryTreeNode lev_22 = new NaryTreeNode();   lev_22.data=30;
    NaryTreeNode lev_23 = new NaryTreeNode();   lev_23.data=200;
    NaryTreeNode lev_24 = new NaryTreeNode();   lev_24.data=300;

    //Add all the nodes to a list.

    List<NaryTreeNode> temp2 = new ArrayList<NaryTreeNode>();  //Level two first branch
    temp2.add(lev_21);
    temp2.add(lev_22);

    List<NaryTreeNode> temp3 = new ArrayList<NaryTreeNode>();  //level two second branch
    temp3.add(lev_23);
    temp3.add(lev_24);

    lev_11.nary_list.addAll(temp2);
    lev_12.nary_list.addAll(temp3);

    List<NaryTreeNode> temp = new ArrayList<NaryTreeNode>();  //level one
    temp.add(lev_11);
    temp.add(lev_12);
    temp.add(lev_13);


    // Add Temp to root  to form a leaf of the root
    root.nary_list.addAll(temp);

    // root=null;
    //Call the display function.
    t1.display(root);
  }
}

Answer 1

下面这些似乎行得通。为了获得额外的积分，迭代可以通过增强的for循环来完成，并随时中止。可能需要添加访问修饰符。

import java.util.*;

class NaryTree {
    final int data;
    final List<NaryTree> children;

    public NaryTree(int data, NaryTree... children) {
        this.data = data;
        this.children = Arrays.asList(children);
    }

    static class InOrderIterator implements Iterator<Integer> {
        final Queue<NaryTree> queue = new LinkedList<NaryTree>();

        public InOrderIterator(NaryTree tree) {
            queue.add(tree);
        }

        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override
        public Integer next() {
            NaryTree node = queue.remove();
            queue.addAll(node.children);
            return node.data;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    Iterable<Integer> inOrderView = new Iterable<Integer>() {
        @Override
        public Iterator<Integer> iterator() {
            return new InOrderIterator(NaryTree.this);
        } 
    };
}

测试代码：

public class Test {
    public static void main(String[] args) throws Exception {
        NaryTree tree = new NaryTree(100,
            new NaryTree(90, 
                new NaryTree(20),
                new NaryTree(30)
            ), new NaryTree(50, 
                new NaryTree(200),
                new NaryTree(300)
            ), new NaryTree(70)
        );
        for (int x : tree.inOrderView) {
            System.out.println(x);
        }
    }
}

Answer 2

使用队列的级别顺序遍历：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.stream.Collectors;

public class LevelOrderTraversal {
    static class Node {
        int data;

        Node children[];

        Node(int data, int n) {
            children = new Node[n];
            this.data = data;
        }
    }

    public static void main(String[] args) {
        /*  
                       1 
                    /  |  \ 
                   2   3   4 
                 / | \ 
                5  6  7 
        */
        int n = 3;
        Node root = new Node(1, n);
        root.children[0] = new Node(2, n);
        root.children[1] = new Node(3, n);
        root.children[2] = new Node(4, n);
        root.children[0].children[0] = new Node(5, n);
        root.children[0].children[1] = new Node(6, n);
        root.children[0].children[2] = new Node(7, n);

        List<List<Integer>> levelList = levelOrder(root);
        for (List<Integer> level : levelList) {
            for (Integer val : level) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levelList = new ArrayList<>();

        if (root == null) {
            return levelList;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> level = new ArrayList<>();

            while (n-- > 0) {
                Node node = queue.remove();
                level.add(node.data);
                queue.addAll(Arrays.stream(node.children).filter(Objects::nonNull).collect(Collectors.toList()));
            }
            levelList.add(level);
        }
        return levelList;
    }

}