java中通用树(n-ary树)的级别顺序遍历
(如果您想避免冗长的解释，我正在寻找的只是java中通用树(n-ary tree)的级别顺序遍历.提供的代码有效并且需要级别顺序显示功能.环顾了一小时，但找不到对通用 n 元树的引用.如果 soemone 可以帮助我在我的代码之上构建 LevelOrderDisplay 函数将不胜感激，因为它将帮助我理解我得到的队列错误.谢谢！)
我一直在尝试实现 Autosys 工作计划的树形表示.由于每个作业(流程)都可以有一个或多个相关作业，因此我决定使用 n-ary tree 实现，以便我可以映射流程.我正在使用 java 集合.我需要执行级别顺序遍历以显示作业依赖关系.首先打印根，然后是第一层的所有节点，然后是第二层的所有节点，依此类推.
我试图在 StackOverflow 上搜索一个多小时，但我遇到的大多数示例都是针对二叉树的.我明白我需要为此使用队列.
根据我在研究过程中得到的信息，算法应该如下所示:如果这是错误的，请纠正我，如果可能，请提供代码.也欢迎替代方法，但我真正要寻找的是通用树的简单基本级顺序遍历.
让我们让它成为通用树实现的资源丰富的线程.大多数代码已经在工作了.请帮忙.
算法:对于每个节点，首先访问该节点，然后将其子节点放入 FIFO 队列中.
printLevelorder(树)1) 创建一个空队列 q2) temp_node = root/*从root开始*/3) 当 temp_node 不为 NULL 时循环a) 打印 temp_node->data.b) 将 temp_node 的子节点(先左后右子节点)排入 qc) 从 q 中取出一个节点并将其值分配给 temp_node由于某种奇怪的原因，我无法在我的 Eclipse IDE 中声明队列.我已经导入了 java.util.*；我在这里遗漏了一些东西，请查看以下错误.
第一次尝试:
队列BFSqueue = new LinkedList(); <块引用>
错误:LinkedList 类型不是通用的；它不能用参数进行参数化
第二次尝试:
QueueListBFSqueue = new QueueList(); <块引用>
错误:- QueueList 无法解析为类型
当前树结构供参考:
根(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.*;导入java.io.*；导入 java.util.List；//n叉树的节点公共类 NaryTreeNode {整数数据；列出 <NaryTreeNode>nary_list = new ArrayList();}公共类 NaryTree {无效显示(NaryTreeNode t){如果(t==空)返回;System.out.print(t.data + " ");for(NaryTreeNode n : t.nary_list)显示(n)；//递归调用}公共静态无效主要(字符串参数[]){NaryTree t1 = new NaryTree();NaryTreeNode root = new NaryTreeNode();根.数据 = 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；//将所有节点添加到列表中.列出<NaryTreeNode>temp2 = new ArrayList();//二级第一分支temp2.add(lev_21);temp2.add(lev_22);列出<NaryTreeNode>temp3 = new ArrayList();//二级二级分支temp3.add(lev_23);temp3.add(lev_24);lev_11.nary_list.addAll(temp2);lev_12.nary_list.addAll(temp3);列出<NaryTreeNode>temp = new ArrayList();//一级temp.add(lev_11);temp.add(lev_12);temp.add(lev_13);//将 Temp 添加到根以形成根的叶子root.nary_list.addAll(temp);//root=null;//调用显示函数.t1.display(根)；}} 使用Queue进行层序遍历:
import java.util.ArrayList;导入 java.util.Arrays；导入 java.util.LinkedList；导入 java.util.List；导入 java.util.Objects；导入 java.util.Queue；导入 java.util.stream.Collectors；公共类 LevelOrderTraversal {静态类节点 {整数数据；节点孩子[];节点(整数数据，整数 n){孩子=新节点[n]；this.data = 数据；}}公共静态无效主要(字符串[]参数){/*1/|2 3 4/|5 6 7*/诠释 n = 3;节点根 = 新节点(1，n)；root.children[0] = 新节点(2，n)；root.children[1] = 新节点(3, n);root.children[2] = 新节点(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);列表<列表<整数>>levelList = levelOrder(root);for (List level : levelList) {对于(整数值:级别){System.out.print(val + " ");}System.out.println();}}公共静态列表<List<Integer>>levelOrder(节点根){列表<列表<整数>>levelList = new ArrayList<>();如果(根==空){返回级别列表；}队列<节点>queue = new LinkedList<>();queue.add(root);而(！queue.isEmpty()){int n = queue.size();列表<整数>level = new ArrayList<>();而 (n-- > 0) {节点 node = queue.remove();level.add(node.data);queue.addAll(Arrays.stream(node.children).filter(Objects::nonNull).collect(Collectors.toList()));}levelList.add(级别);}返回级别列表；}} (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);
}
}
解决方案
Level-order traversal using Queue:
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;
}
}
相关文章