级别顺序遍历java中的通用树（n-ary树）

（如果你想避免冗长的解释，我正在寻找的是java中generics树（n-ary树）的级别顺序遍历。提供的代码工作并需要级别顺序显示function。一小时但无法找到对通用n-ary树的引用。如果soemone可以帮助我在我的代码之上构建LevelOrderDisplay函数，将会很感激，因为它将帮助我理解我得到的队列错误。谢谢！）

我一直在尝试在工作中实现Autosys作业计划的树表示。 由于每个作业（进程）可以有一个或多个依赖作业，我决定使用n-ary树实现，以便我可以映射流。 我正在使用java集合。 我需要执行级别顺序遍历来显示作业依赖性。 首先打印Root，然后是第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 

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

第一次尝试：

 Queue BFSqueue = new LinkedList(); 

错误：LinkedList类型不是通用的; 它不能用参数参数化

第二次尝试：

 QueueList BFSqueue = new QueueList(); 

错误： – 无法将QueueList解析为类型

当前树形结构供参考：

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

当前显示function的输出是预先订购的：100 90 20 30 50 200 300 70我需要进行级别订单遍历。 要求的输出。

 > 100 > 90 50 70 > 20 30 200 300 

如果有人想在他们的机器上运行它并添加级别顺序遍历function，这是一个有效的代码。 请提供有关队列操作的注释说明，因为这是我遇到的问题。

谢谢！

 import java.util.*; import java.io.*; import java.util.List; //The node for the n-ary tree public class NaryTreeNode { int data; List  nary_list = new ArrayList(); } 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 temp2 = new ArrayList(); //Level two first branch temp2.add(lev_21); temp2.add(lev_22); List temp3 = new ArrayList(); //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 temp = new ArrayList(); //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 children; public NaryTree(int data, NaryTree... children) { this.data = data; this.children = Arrays.asList(children); } static class InOrderIterator implements Iterator { final Queue queue = new LinkedList(); 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 inOrderView = new Iterable() { @Override public Iterator 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); } } }