java中通用树(n元树)的层序遍历

本文介绍了java中通用树(n元树)的层序遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ (如果您想避免冗长的解释，我所寻找的只是java中泛型树(n元树)的级别顺序遍历.提供的代码有效并且需要级别顺序显示功能.环顾了一个小时，但找不到对通用 n 元树的引用.如果 soemone 能帮助我在我的代码之上构建 LevelOrderDisplay 函数，我将不胜感激，因为它将帮助我理解我得到的队列错误.谢谢！)我一直试图在工作中实现 Autosys 作业计划的树形表示.由于每个作业(进程)可以有一个或多个依赖作业，我决定采用 n 元树实现，以便我可以映射流程.我正在使用 java 集合.我需要执行级别顺序遍历以显示作业依赖项.首先打印根，然后是第一层的所有节点，然后是第二层的所有节点，依此类推.我尝试在 StackOverflow 上搜索了一个多小时，但我遇到的大多数示例都是二叉树.我明白我需要为此使用队列.根据我在研究过程中得到的信息，算法应该如下所示:如果这是错误的，请纠正我，如果可能，请提供代码.也欢迎使用其他方法，但我真正要寻找的是通用树的简单基本级顺序遍历.让我们将此作为通用树实现的资源丰富的线程.大部分代码已经可以工作了.请帮忙.算法:对于每个节点，首先访问该节点，然后将其子节点放入一个 FIFO 队列.printLevelorder(tree)1)创建一个空队列q2) temp_node = root/*从根开始*/3) 当 temp_node 不为 NULL 时循环a) 打印 temp_node->data.b) 将 temp_node 的孩子(先是左孩子，然后是右孩子)排队到 qc) 从 q 中取出一个节点并将其值赋给 temp_node出于某种奇怪的原因，我无法在 Eclipse IDE 中声明队列.我已经导入了 java.util.*;我在这里遗漏了一些东西，请查看以下错误.第一次尝试:QueueBFSqueue = 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 {整数数据；列表 nary_list = new ArrayList();}公共类 NaryTree {无效显示(NaryTreeNode t){如果(t==null)返回;System.out.print(t.data + " ");for(NaryTreeNode n : t.nary_list)显示(n)；//递归调用}公共静态无效主(字符串参数[]){NaryTree t1 = new NaryTree();NaryTreeNode root = new 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;//将所有节点添加到列表中.列表temp2 = new ArrayList();//二级第一分支temp2.​​add(lev_21);temp2.​​add(lev_22);列表temp3 = new ArrayList();//二级二级分支temp3.add(lev_23);temp3.add(lev_24);lev_11.nary_list.addAll(temp2);lev_12.nary_list.addAll(temp3);列表temp = new ArrayList();//一级临时添加(lev_11)；临时添加(lev_12)；临时添加(lev_13)；//将 Temp 添加到根以形成根的叶子root.nary_list.addAll(temp);//根=空；//调用显示函数.t1.display(root);}} 解决方案 使用 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 = 数据；}}公共静态无效主(字符串 [] args){/*1/|2 3 4/|5 6 7*/整数 n = 3;节点根=新节点(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);列表>levelList = levelOrder(root);for (List level : levelList) {for (Integer val : level) {System.out.print(val + " ");}System.out.println();}}公共静态列表>levelOrder(节点根){列表>levelList = new ArrayList();如果(根==空){返回级别列表；}队列queue = new LinkedList();队列.添加(根)；而 (!queue.isEmpty()) {int n = queue.size();列表级别 = 新的 ArrayList();而 (n-- > 0) {节点 node = queue.remove();level.add(node.data);queue.addAll(Arrays.stream(node.children).filter(Objects::nonNull).collect(Collectors.toList()));}levelList.add(level);}返回级别列表；}}(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 q2) 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_nodeFor 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>();2nd Attempt:QueueList<NaryTreeNode> BFSqueue = new QueueList<NaryTreeNode>();Current Tree Structure for reference: root(100) / | 90 50 70 /20 30 200 300The output of the current display function is in pre order:100 90 20 30 50 200 300 70I need a level order traversal for the same.Required output.> 100> 90 50 70> 20 30 200 300This 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 treepublic 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; }} 这篇关于java中通用树(n元树)的层序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！