Level Bypass order of common tree (n-ary tree) in java

Question

(In case you want to avoid a long explanation, all I'm looking for is a level traversal for a generic tree (n-ary tree) in java. The code above works and needs a function to display the level order. I looked around for an hour, but couldn’t find a link to the generic n-ary trees. I would understand if soemone could help me create the LevelOrderDisplay function on top of my code, as this will help me understand the queue error that I get. Thank you!)

I am trying to implement a tree view of Autosys work schedules at work. Since each task (process) can have one or more dependent tasks on them, I decided to go with an n-ary tree implementation so that I can map the stream. I use java collections for the same. I need to do a level traversal to display work dependencies. First print root, then all nodes on the first level, and then all nodes on the level 2, etc.

I tried to find more than an hour on StackOverflow, but most of the examples I came across were for binary trees. I understand that I need to use a queue for this.

From what I got during my research, the algorithm should look like this: Please correct me if this is not the case and if possible, specify the code for this. Alternative approaches are also welcome, but what I'm really looking for is a simple walkthrough of the elementary level of a shared tree.

Allows you to make this resource-intensive thread to implement a shared tree. Most of the code already works. Please, help.

Algo: 

For each node, a node is first visited, and then its child nodes are placed in the FIFO queue.

 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 

For some strange reason, I was unable to queue in my Eclipse IDE. I imported java.util. *; I missed something here, please review the errors below.

First try:

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

Error: LinkedList type is not common; it cannot be parameterized with arguments

Second attempt:

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

Error: - QueueList cannot be resolved for type

The structure of the current tree for reference:

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

The output of the current display function is in preliminary order: 100 90 20 30 50 200 300 70 For this, I need a level bypass. The required conclusion.

 > 100 > 90 50 70 > 20 30 200 300 

This is working code if someone wants to run it on their computer and add a level order bypass function. Please provide comments for queuing operations since I am stuck.

Thanks!

 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

The following seems to work. For additional credit, the iteration can be performed with an extended loop and interrupted at any time. You might want to add access modifiers.

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

Test code:

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