Java幅優先検索の素敵なプリント

Question

これは、幅優先検索用のコードです。 レベルごとに印刷したいと思います。 1行、1レベル。

public static void printTreeBreadthFirst(Tree t) 
{ 
    Node root = t.getRoot(); 
    Queue<Node> queue = new LinkedList<Node>() ; 
     if (root == null) 
      return; 
     queue.clear(); 
     queue.add(root); 
     while(!queue.isEmpty()){ 
      Node<?> node = queue.remove(); 
      System.out.println(node.getData() + " "); 
      if(node.getChildren().isEmpty()) 
       continue; 
      else 
       queue.addAll(node.getChildren()); 
     } 
} 

しかし、これはすべて同じ行に印刷されるため、素晴らしい印刷ではありません。 この素晴らしいプリントをどのように実装できますか？

EDIT：（ルート（child1の（子1.1、子1.2）（子2（子2.1））（child3）） NICE出力：

root       (level 1) 
child1 - child2 - child3  (level 2) 
child1.1 - child1.2 - child2.1 (level 3) 

Answer 1

取得するにはすてきなプリント INPUTの例所望の「素敵なプリント」、あなたはキューからノードを引き出したとき。そのため、あなたがキューに挿入するよ新しい構造を作成する必要がありますlevelが欠落している、例えば

class NodeLevel { 
    private Node node; 
    private int level; 
    // ... constructor, getters, ... 
} 

そしてたび新しい要素をキューに追加するには、を使用します。。

ので、レベル1と第1のインサートルート：

NodeList nodeList = queue.remove(); 
Node<?> node = nodeList.getNode(); 
int level = nodeList.getLevel(); 
// pretty print using the node & level 

そしてlevel + 1と新しい子を追加：

node.getChildren().forEach(child -> queue.add(new NodeList(child, level + 1))); 

queue.add(new NodeList(root, 1)); 

あなたは、キューから要素を削除するレベルを保存

または、levelを取得するときは、 NodeList、あなたはすべての反復で追加をしないので：

int childLevel = nodeList.getLevel() + 1; 
//pretty print 

Answer 2

複雑な部分は、与えられたレベルが終了したときに知ることです。ノードは自分のレベルを知らない（一般的に）けど、彼らが持っているどのように多くの祖先カウントすることでそれを見つけることができます。

public static void getLevel(Node n) { 
    return n == null ? 0 : 1 + getLevel(n.getParentNode()); 
} 

もう一つ、これらのレベルを計算するためのより効率的な方法は、ノード自身、店舗内に格納することですQueueでこれらの拡張ノード：

public class NodeWithLevel { 
    private Node node; 
    private int level; 
    ... 
} 

は今、あなただけのレベルを確認するように印刷コードを変更する必要があります。レベルを上げると、次の行をスキップする必要があります。

int currentLevel = 0; // level of root 
while (...) { 
    ... 
    System.out.print(node.getData() + " - "); 
    if (getLevel(node) > currentLevel) { 
     currentLevel ++; 
     System.out.println(" (level " + currentLevel + ")"); 
    } 
    if(node.getChildren().isEmpty()) 
    ... 
} 

これは正確には求められていませんが、近いです。最後の" - "を削除してレベルを調整するには、印刷する前に行全体を保存し、出力を生成する前に最長行の長さを確認する必要があります。