0

(長い説明を避けたい場合、私が探しているのは Java のジェネリック ツリー (n-ary ツリー) のレベル オーダー トラバーサルだけです。提供されたコードは機能し、レベル オーダー表示機能が必要です。 1 時間かかりましたが、一般的な n-ary ツリーへの参照が見つかりませんでした.soemone が私のコードの上に LevelOrderDisplay 関数を構築するのを手伝ってくれるとありがたいです.それは私が得ているキューエラーを理解するのに役立ちます.ありがとう!

私は、職場で Autosys ジョブ スケジュールのツリー表現を実装しようとしています。各ジョブ (プロセス) には 1 つ以上の依存ジョブを含めることができるため、フローをマッピングできるように、n-ary ツリーの実装を使用することにしました。同じためにJavaコレクションを使用しています。ジョブの依存関係を表示するには、レベル順トラバーサルを実行する必要があります。最初にルートを出力し、次にレベル 1 のすべてのノード、次にレベル 2 のすべてのノードなどを出力します。

StackOverflow で 1 時間以上検索しようとしましたが、出くわしたほとんどの例はバイナリ ツリーに関するものでした。これにはキューを使用する必要があることを理解しています。

調査中に得たものから、アルゴリズムは次のようになります。これが間違っている場合は修正してください。可能であれば、これのコードを提供してください。別のアプローチも歓迎しますが、私が本当に探しているのは、ジェネリック ツリーの単純な基本レベルの順序トラバーサルです。

これをジェネリック ツリーの実装のための機知に富んだスレッドにしましょう。ほとんどのコードはすでに機能しています。助けてください。

Algo:

各ノードについて、最初にノードが訪問され、次にその子ノードが FIFO キューに入れられます。

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

奇妙な理由で、Eclipse IDE でキューを宣言できませんでした。java.util.*; をインポートしました。ここに何かが欠けています。以下のエラーを見てください。

1 回目の試行:

Queue<NaryTreeNode> BFSqueue = new LinkedList<NaryTreeNode>();

エラー: LinkedList 型はジェネリックではありません。引数でパラメータ化することはできません

2 回目の試行:

QueueList<NaryTreeNode> BFSqueue = new QueueList<NaryTreeNode>();

エラー: - QueueList を型に解決できません

参照用の現在のツリー構造:

     root(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.*;
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);
  }
}
4

2 に答える 2

2

以下はうまくいくようです。追加のクレジットとして、強化された for ループを使用して反復を実行し、いつでも中止することができます。アクセス修飾子を追加したい場合があります。

import java.util.*;

class NaryTree {
    final int data;
    final List<NaryTree> children;

    public NaryTree(int data, NaryTree... children) {
        this.data = data;
        this.children = Arrays.asList(children);
    }

    static class InOrderIterator implements Iterator<Integer> {
        final Queue<NaryTree> queue = new LinkedList<NaryTree>();

        public InOrderIterator(NaryTree tree) {
            queue.add(tree);
        }

        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override
        public Integer next() {
            NaryTree node = queue.remove();
            queue.addAll(node.children);
            return node.data;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    Iterable<Integer> inOrderView = new Iterable<Integer>() {
        @Override
        public Iterator<Integer> iterator() {
            return new InOrderIterator(NaryTree.this);
        } 
    };
}

テストコード:

public class Test {
    public static void main(String[] args) throws Exception {
        NaryTree tree = new NaryTree(100,
            new NaryTree(90, 
                new NaryTree(20),
                new NaryTree(30)
            ), new NaryTree(50, 
                new NaryTree(200),
                new NaryTree(300)
            ), new NaryTree(70)
        );
        for (int x : tree.inOrderView) {
            System.out.println(x);
        }
    }
}
于 2012-10-08T20:31:13.703 に答える