在Java泛型树（N叉树）的等级序遍历 [英] Level Order traversal of a generic tree(n-ary tree) in java
问题描述
（如果你想避免冗长的解释，都是我找的是一个级别的序遍历中的Java泛型树（N叉树）的code供给的作品，需要等级秩序显示功能。环顾四周，一个小时，但无法找到引用通用正叉树。请问AP preciate如果soemone能帮助我建立LevelOrderDisplay功能在我的code顶部，因为它会帮助我了解队列错误我收到，谢谢！）
我一直在努力实现一棵树再$ P $的Autosys作业调度工作psentation。由于每个作业（进程）能对他们一个或以上的相关工作，我决定去与一个n元树实现，这样我可以映射流。我使用Java集合为同一个。我需要执行层面序遍历来显示作业的依赖性。 首先打印根，然后在一个层面上，所有的节点，然后在2级等所有节点。
我试图寻找在计算器上一个小时，但是最让我碰到的例子是二进制树。我也明白，我需要使用此队列。
从我我的研究过程中得到的，该算法应该是这样的： 请纠正我，如果这是错误的，如果可能的话，这提供了一个code。 替代方法也是受欢迎的，但我所真正需要的是一个通用的树的简单的初级层次序遍历。
让我们使这对通用的树实现一个足智多谋的线程。大部分的code已经工作。请大家帮帮忙。
算法中：
有关的每个节点中，首先在节点被访问，然后它的子节点被放入一个FIFO队列。
printLevelorder（树）
1）创建一个空的队列q
2）temp_node =根/ *从根*启动/
3）循环而temp_node不为NULL
一）打印temp_node-＆GT;的数据。
B）排队temp_node的孩子（第一左再右子女）为q
C）从q出列一个节点，并赋予它的价值temp_node
由于一些奇怪的原因，我一直没能在我的Eclipse IDE申报队列。 我已导入的java.util。*; 我失去了一些东西在这里，请看看下面的错误。
第一次尝试：
问答LT; NaryTreeNode＆GT; BFSqueue =新的LinkedList＆LT; NaryTreeNode＆GT;（）;
错误：类型的LinkedList不是通用的;它不能与参数参数化
第二尝试：
QueueList＆LT; NaryTreeNode＆GT; BFSqueue =新QueueList＆LT; NaryTreeNode＆GT;（）;
错误： - QueueList不能被解析为一个类型
仅供参考当前树结构：
根（100）
/ | \
90 50 70
/ \
20 30 200 300
目前显示功能的输出是pre顺序： 100 90 20 30 50 200 300 70 我需要一个层次序遍历的一样。 所需的输出。
＆GT; 100
＆GT; 90 50 70
＆GT; 20 30 200 300
这是，如果有人想他们的机器上运行它，并添加水平序遍历功能的工作code。请提供评论的解释为队列操作，因为这是我在哪里卡住了。
谢谢！
进口的java.util。*;
进口java.io. *;
进口的java.util.List;
//对于n进制树的节点
公共类NaryTreeNode {
int数据;
名单＆LT; NaryTreeNode＆GT; nary_list =新的ArrayList＆LT; NaryTreeNode＆GT;（）;
}
公共类NaryTree {
无效显示器（NaryTreeNode T）{
如果（T == NULL）
返回;
System.out.print（t.data +）;
对于（NaryTreeNode N：t.nary_list）
显示器（N）; //递归调用
}
公共静态无效的主要（字符串的args []）{
NaryTree T1 =新NaryTree（）;
NaryTreeNode根=新NaryTreeNode（）;
root.data = 100;
NaryTreeNode lev_11 =新NaryTreeNode（）; lev_11.data = 90;
NaryTreeNode lev_12 =新NaryTreeNode（）; lev_12.data = 50;
NaryTreeNode lev_13 =新NaryTreeNode（）; lev_13.data = 70;
NaryTreeNode lev_21 =新NaryTreeNode（）; lev_21.data = 20;
NaryTreeNode lev_22 =新NaryTreeNode（）; lev_22.data = 30;
NaryTreeNode lev_23 =新NaryTreeNode（）; lev_23.data = 200;
NaryTreeNode lev_24 =新NaryTreeNode（）; lev_24.data = 300;
//所有节点添加到列表。
名单＆LT; NaryTreeNode＆GT; TEMP2 =新的ArrayList＆LT; NaryTreeNode＆GT;（）; //二级第一家分行
temp2.add（lev_21）;
temp2.add（lev_22）;
名单＆LT; NaryTreeNode＆GT; TEMP3 =新的ArrayList＆LT; NaryTreeNode＆GT;（）; //二级第二支
temp3.add（lev_23）;
temp3.add（lev_24）;
lev_11.nary_list.addAll（TEMP2）;
lev_12.nary_list.addAll（TEMP3）;
名单＆LT; NaryTreeNode＆GT;临时=新的ArrayList＆LT; NaryTreeNode＆GT;（）; //其中一个级别
temp.add（lev_11）;
temp.add（lev_12）;
temp.add（lev_13）;
//添加临时根形成根叶
root.nary_list.addAll（临时）;
//根= NULL;
//调用显示功能。
t1.display（根）;
}
}
下面似乎工作。对于加分，迭代可与增强的for循环来完成，并且终止在任何时间。您可能要添加访问修饰符。
进口的java.util。*;
类NaryTree {
最终诠释数据;
最后的名单，其中，NaryTree＆GT;儿童;
公共NaryTree（int数据，NaryTree ......孩子）{
this.data =数据;
this.children = Arrays.asList（儿童）;
}
静态类InOrderIterator实现迭代器＆LT;整数GT; {
最后的问答LT; NaryTree＆GT;队列=新的LinkedList＆LT; NaryTree＆GT;（）;
公共InOrderIterator（NaryTree树）{
queue.add（树）;
}
@覆盖
公共布尔规则hasNext（）{
返回queue.isEmpty（）！;
}
@覆盖
下一个公开整数（）{
NaryTree节点= queue.remove（）;
queue.addAll（node.children）;
返回node.data;
}
@覆盖
公共无效删除（）{
抛出新UnsupportedOperationException异常（）;
}
}
可迭代＆LT;整数GT; inOrderView =新的可迭代＆LT;整数GT;（）{
@覆盖
公共迭代器＆LT;整数GT;迭代（）{
返回新InOrderIterator（NaryTree.this）;
}
};
}
测试code：
公共类测试{
公共静态无效的主要（字串[] args）抛出异常{
NaryTree树=新NaryTree（100，
新NaryTree（90，
新NaryTree（20），
新NaryTree（30）
），新NaryTree（50，
新NaryTree（200），
新NaryTree（300）
），新NaryTree（70）
）;
对于（INT X：tree.inOrderView）{
的System.out.println（X）;
}
}
}
(In case you want to avoid the lengthy explanation, all I am looking for is a level order traversal for a generic-tree(n-ary tree) in java. The code supplied works and needs the level order display function. Looked around for an hour but couldnt find reference to generic n-ary trees. Would appreciate if soemone can help me build the LevelOrderDisplay function on top of my code as it will help me understand the queue error that I am getting. Thanks! )
I have been trying to implement a tree representation of Autosys job schedules at work. As each job(process) can have one or or more dependent job on them, i decided to go with a n-ary tree implementation so that i can map the flow. I am using java collections for the same. I need to perform a level order traversal to display job dependencies. First Print Root, then all nodes on level one and then all nodes on level 2 and so on.
I tried to search for over an hour on StackOverflow but most the examples I came across were for Binary Trees. I do understand that I need to use a queue for this.
From what i got during my research, the algorithm should look like: Please correct me if this is wrong and if possible, provide a code for this. Alternate approaches are also welcome but what I am really looking for is a simple elementary level order traversal of a generic tree.
Lets make this a resourceful thread for generic tree implementation. Most of the code is already working. Please help.
Algo:
For each node, first the node is visited and then it’s child nodes are put in a 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 have not been able to declare a queue in my Eclipse IDE. I have imported java.util.*; I am missing something here, please have a look at the below errors.
1st Attempt:
Queue<NaryTreeNode> BFSqueue = new LinkedList<NaryTreeNode>();
Error: The type LinkedList is not generic; it cannot be parameterized with arguments
2nd Attempt:
QueueList<NaryTreeNode> BFSqueue = new QueueList<NaryTreeNode>();
Error: - QueueList cannot be resolved to a type
Current Tree Structure for reference:
root(100)
/ | \
90 50 70
/ \
20 30 200 300
The output of the current display function is in pre order: 100 90 20 30 50 200 300 70 I need a level order traversal for the same. Required output.
> 100
> 90 50 70
> 20 30 200 300
This is a working code if someone wants to run it on their machine and add the level order traversal function. Please provide commented explanation for the queue operations as that is where 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);
}
}
The following seems to work. For extra credit, iteration can be done with an enhanced for loop, and aborted 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);
}
}
}
这篇关于在Java泛型树（N叉树）的等级序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
