0

我一直在尝试在工作中实现 Autosys 作业计划的树表示。由于每个作业（流程）都可以有一个或多个相关作业，因此我决定使用 n-ary tree 实现，以便我可以映射流程。我使用相同的 java 集合。

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

Q2:(OPEN)显示函数以Post order方式遍历树。我想以级别顺序方式遍历它，其中节点在级别基础上打印。根，然后是一级的所有节点，然后是二级的所有节点，依此类推。DFS 遍历的链接作为另一个问题发布在下面的链接中。（大家好，我对同一棵树的级别顺序遍历还有另一个问题，我已经在下面给出的链接上发布了这个问题。如果你们能提供帮助，我会很高兴。 通用树的级别顺序遍历（n-ary tree ) 在 java 中 让我们为泛型树提供更多资源。)

我们可以为刚接触 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);

} }

4

3 回答 3

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)

编辑

我还将按此顺序编写显示函数，以便在用尽迭代器后打印当前节点的值，而不必询问!hasNext()：

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

// Display myself
System.out.println("Value is: " + t.data);
于 2012-10-06T20:29:59.633 回答
2

在我看来，您每次都在通过循环创建一个新的迭代器，因此每个迭代器都设置为列表的开头。稍后我将尝试添加规范参考。尝试：

    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 具有价值。

于 2012-10-06T20:14:37.863 回答
2

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

我还建议您考虑使用 first-child/next-sibling 选项，而不是在每个节点中放置一个列表。在这个系统中，每个节点（最多）引用两个其他节点：它的第一个子节点（如果它有任何子节点）和它的下一个兄弟节点（除非它是其父节点的最后一个兄弟节点）。然后，您可以通过兄弟列表遍历兄弟列表以枚举子节点，并且您最终不会在每个节点中遇到可变长度数组的所有开销。

于 2012-10-06T20:20:54.153 回答