0

私は、職場で Autosys ジョブ スケジュールのツリー表現を実装しようとしています。各ジョブ (プロセス) には 1 つ以上の依存ジョブを含めることができるため、フローをマッピングできるように、n-ary ツリーの実装を使用することにしました。私は同じためにJavaコレクションを使用しています。

Q1(解決済み): 今のところの問題は、表示機能が無限ループでハングアップすることです。既存のスレッドを探してみましたが、反復子を使用したトラバーサルの例を見つけることができませんでした。

Q2:(OPEN)表示機能はツリーをPost orderでたどります。ノードがレベルごとに印刷されるレベル順にトラバースしたいと思います。ルート、レベル 1 のすべてのノード、レベル 2 のすべてのノードなど。DFS トラバーサルのリンクは、以下のリンクに別の質問として投稿されています。（こんにちは、同じツリーのレベル順トラバーサルについて別の質問があります。以下のリンクに質問を投稿しました。助けていただければ幸いです。 一般的なツリーのレベル順トラバーサル（n-ary tree ) in java これを一般的なツリーに対してより機知に富んだものにしましょう.)

私はそこに基本的な例がほとんど見つからなかったので、これを n-ary ツリーに慣れていない人々のための機知に富んだ投稿にすることができますか?

これは、3 つの子を持つルート ノードから始めた私のコードです。これは後で拡張する予定です。

初歩的な質問です。再帰で反復子を使用することはお勧めしません。display() で Iterator を個別に定義しようとしましたが、それでも機能しませんでした。

現在のツリー構造:

     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

そのループで何が起こっているのかを理解するのに十分なJavaの知識はありませんが、私には疑わしいようです。私が読んだ方法では、ループを通過するたびに新しいイテレータを作成しています。

また、すべてのノードにリストを配置する代わりに、最初の子/次の兄弟を使用するオプションを検討することをお勧めします。このシステムでは、すべてのノードが (多くても) 2 つの他のノードを参照します: 最初の子 (子がある場合) と次の兄弟 (親の最後の兄弟でない場合)。次に、兄弟リストを兄弟リストをたどって子ノードを列挙できます。すべてのノードで可変長配列のすべてのオーバーヘッドが発生することはありません。

于 2012-10-06T20:20:54.153 に答える