0

ジェネリックツリーのレベルオーダー（BFS）トラバーサルを実行するために、以下のリンクに記載されているコードに対して次の表示関数を記述しました。問題は、各レベルが2回印刷されることです。誰かが理由を教えてもらえますか？この関数のない元のコードは、誰かが実装全体を必要とする場合に備えて、以下のリンクにあります。それ以外の場合は、以下のdisplayBFS関数を見て、値が繰り返される理由を教えてください。

Javaでのジェネリックツリー（n-aryツリー）のレベル順序トラバーサル

ありがとう！

void displayBFS(NaryTreeNode n)
{
    Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();

    if(n!=null)
    {
        q.add(n);
        System.out.println(n.data);
    }

    while(n!=null)
    {
        for(NaryTreeNode x:n.nary_list)
        {
            q.add(x);
            System.out.println(x.data );
        }        
        n =  q.poll();
    }  
}

参考のための現在のツリー構造：

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

出力：100 90 50 70 90 50 70 20 30200300 20
30200300

4

1 に答える 1

4

問題は、ルートノードを2回処理することです。最初にルートノードをキューに追加し（行内q.add(n)）、最初にに到達する前にn = q.poll()処理し、次にキューから取り出して再度処理します。

他のすべてが正しいので、ルート以外の各ノードのコピーを2つしか取得できません。ダブリングはルートで1回だけ発生します。

これを修正するには、行を削除するかq.add(n)（ルートノードがなくてもルートノードを処理するため）、次のように変更します。

    while(n!=null)
    {
        ...
        n =  q.poll();
    }

これに：

    while((n = q.poll()) != null)
    {
        ...
    }

その最初の余分な時間でルートノードを処理しないようにします。

于 2012-10-09T21:05:40.803 に答える