泛型N进制树（每个子节点超过两个节点的树）在Java中使用List进行树遍历

Question

我一直在尝试在工作中实现Autosys作业计划的树表示。由于每个作业（流程）可以有一个或多个依赖作业，因此我决定使用n元树实现，以便映射流程。我使用java集合来实现同样的目标。

Q1（已解决）：目前的问题是显示功能被挂在一个无限循环中。我尝试寻找现有的线程，但无法遇到使用迭代器进行遍历的示例。

Q2：（打开）显示功能以后序方式遍历树。我希望以一种级别顺序的方式遍历它，其中节点以级别为基础进行打印。根，然后是级别1上的所有节点，然后是级别2上的所有节点，依此类推。DFS遍历的链接作为另一个问题发布在下面的链接中。（大家好，我还有一个关于同一棵树的水平顺序遍历的问题，我已经在下面给出的链接上发布了这个问题。如果你们能提供帮助，我会很高兴。java中泛型树（n元树）的水平顺序遍历让我们为泛型树提供更多资源。）

我们能不能把这篇文章作为一篇有n元树的新手的足智多谋的文章，因为我发现基本的例子很少。

这是我的代码，我从一个有三个子节点的根节点开始。我计划稍后扩展此功能。

一个基本问题。不建议在递归中使用迭代器。我尝试在display（）中定义一个迭代器，但仍然不起作用。

当前树结构：

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

输出是后序的（不确定这是否意味着DFS）。

20 30 90 200 300 50 70 100

密码

import java.util.*;
import java.io.*;
import java.util.List;

//The node for the n-ary tree


public class NaryTree 
{
//The display function traverses the tree

void display(NaryTreeNode t)
{
    Iterator<NaryTreeNode> IT = t.nary_list.iterator();
    if(!(IT.hasNext()))   //If the node does not  have any children, enter.
    {
    //    System.out.println("No more childs of this node");
        System.out.print( t.data + " ");
        return;
    }

    while(IT.hasNext()){
        display(IT.next()) ;            //Recursive Call
    }

   System.out.print(t.data + " ");
}

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

    List<NaryTreeNode> temp = new ArrayList<NaryTreeNode>();  //level one
    temp.add(lev_11);
    temp.add(lev_12);
    temp.add(lev_13);

    lev_11.nary_list.addAll(temp2);
    lev_12.nary_list.addAll(temp3);
    //Add Temp to root  to form a leaf of the root

    root.nary_list.addAll(temp);
    //Call the display function.
    t1.display(root);

###

Answer 1

在我看来，每次循环都要创建一个新的迭代器，所以每个迭代器都设置为列表的开头。稍后我将尝试添加规范引用。尝试：

    Iterator<NsryTreeNode> i = t.nary_list.iterator();
    while(i.hasNext()){
        display(t.nary_list.iterator().next()) ;            //Recursive Call
    }

你可能想看看http://docs.oracle.com/javase/tutorial/collections/interfaces/list.html。您可能会发现ListIterator具有值。

Answer 2

我对Java了解不够，无法理解该循环中可能发生的事情，但我觉得它很可疑；按照我的理解，每次循环中都会创建一个新的迭代器。

我还建议您考虑使用第一个子节点/下一个兄弟而不是在每个节点中放置列表的选项。在此系统中，每个节点引用（最多）两个其他节点：其第一个子节点（如果有子节点）和下一个同级节点（除非它是其父节点的最后一个同级节点）。然后，您可以在同级列表中遍历同级列表以枚举子节点，而不会在每个节点中都产生可变长度数组的所有开销。

Answer 3

nary_list.iterator()

每次创建一个新的迭代器。因此，如果列表中有任何内容，这将是一个无限循环；它每次运行时都会创建一个新的迭代器，并且始终包含元素：

while(t.nary_list.iterator().hasNext()){

如果要直接使用迭代器，可以执行以下操作：

Iterator<NaryTreeNode> iterator = t.nary_list.iterator();
while (iterator.hasNext()) {

但是，您也可以在Java中使用for each循环来减少冗长：

for (NaryTreeNode node : t.nary_list) 

编辑

我还将按此顺序编写display函数，以便在耗尽迭代器后打印当前节点的值，而不必询问！hasNext（）：

// Display all of my children
for (NaryTreeNode node : t.nary_list) {
    display(node);
}

// Display myself
System.out.println("Value is: " + t.data);