レベルオーダー、ツリートラバーサル - レベルの追跡方法？

Question

バイナリツリーをレベル順または幅優先順にトラバースしながらレベルを追跡する方法は？

バイナリツリーのノードには、左右参照のみがあります。

ノードの各行を区別したいと思っています。

private static Queue<Node> traverseLevelOrder(final Node node) 
{ 
    final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for traversal. 
    final Queue<Node> permanentQueue = new LinkedList<Node>(); // Permanent queue is used for node storage. 

    // Add the root node, as current, to the queue. 
    Node current = node; 
    temporaryQueue.add(current); 
    permanentQueue.add(current); 

    while (!temporaryQueue.isEmpty()) 
    { 
     current = temporaryQueue.remove(); 
     System.out.println(String.valueOf(current)); 

     // Check current's children. 
     if (current != null) 
     { 
      final Node left = current.getLeft(); 
      final Node right = current.getRight(); 

      current = left; 
      if (current != null) 
      { 
       temporaryQueue.add(current); 
       permanentQueue.add(current); 
      } 

      current = right; 
      if (current != null) 
      { 
       temporaryQueue.add(current); 
       permanentQueue.add(current); 
      } 
     } 
    } 

    return permanentQueue; 
} 

Answer 1

各レベルのノード数が2倍になることがわかっている場合は、レベルを把握することができます。 たとえば、レベル0にはノードが1つしかありません。レベル1では、2つのノードがあります。レベル2では、4つのノードがあります。レベル3には8つのノードがあります。レベル4では、16のノードがあります。等

Javaでレベル順トラバーサルを使用して配列にノードの各レベルをグループ化するためのコードは次のように見えるかもしれ：

private static Node[][] toArrayLevels(final Node node) 
{ 
    final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for level-order traversal. 

    final ArrayList<Node[]> tree = new ArrayList<Node[]>(); // Levels containing their nodes. 
    ArrayList<Node> nodes = new ArrayList<Node>(); // Current level containing its nodes. 

    Node[][] treeArray = new Node[][]{}; 
    Node[] nodesArray = new Node[]{}; 

    Node current = node; // Level 0. 
    int level = 1; // Node's children are level 1. 
    temporaryQueue.add(current); 

    nodes.add(current); 
    tree.add(nodes.toArray(nodesArray)); 

    nodes = new ArrayList<Node>(2); 

    while (!temporaryQueue.isEmpty()) 
    { 
     // When the nodes completely fill the maximum spaces (2^level) allowed on the current level, start the next level. 
     if (nodes.size() >= Math.pow(2, level)) 
     { 
      tree.add(nodes.toArray(nodesArray)); 
      nodes = new ArrayList<Node>((int) Math.pow(2, level)); 
      level += 1; 
     } 

     current = temporaryQueue.remove(); 

     // Check current's children. 
     if (current != null) 
     { 
      final Node left = current.getLeft(); 
      final Node right = current.getRight(); 

      temporaryQueue.add(left); 
      nodes.add(left); 

      temporaryQueue.add(right); 
      nodes.add(right); 
     } 
     else 
     { 
      // Null nodes fill spaces used to maintain the structural alignment of the tree. 
      nodes.add(null); 
      nodes.add(null); 
     } 
    } 

    // Push remaining nodes. 
    if (nodes.size() > 0) 
    { 
     tree.add(nodes.toArray(nodesArray)); 
    } 

    return (tree.toArray(treeArray)); 
} 

をそれが現在のレベルのノードの数をチェックします。ノードが現在のレベルを満たすと、ノードは新しいレベルを開始します。

例として、バイナリツリーは次のようになります。ここでは

Level 0:        60 
         /       \ 
Level 1:    50        65 
       /   \    /   \ 
Level 2:  49    55    --    66 
      / \  / \  / \  / \ 
Level 3: --  --  --  --  --  --  --  71 

は例の出力である：ここで

System.out.println(Arrays.deepToString(binaryTree.toArrayLevels())); 

[[{60}], [{50}, {65}], [{49}, {55}, null, {66}], [null, null, null, null, null, null, null, {71}], [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]] 

[ 
    [{60}], // Level 0. 
    [{50}, {65}], // Level 1. 
    [{49}, {55}, null, {66}], // Level 2. 
    [null, null, null, null, null, null, null, {71}], // Level 3. 
    [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null] // Level 4. 
] 

はJavaScriptバージョンです：

function toArrayLevels(node) 
{ 
    var temporary = []; // Temporary is used for level-order traversal. 

    var tree = []; // Levels containing their nodes. 
    var nodes = []; // Current level containing its nodes. 

    var current = node; // Level 0. 
    var level = 1; // Node's children are level 1. 

    temporary.push(current); 
    tree.push([current]); 

    while (temporary.length > 0) 
    { 
     // When the nodes completely fill the maximum spaces (2^level) allowed on the current level, start the next level. 
     if (nodes.length >= Math.pow(2, level)) 
     { 
      tree.push(nodes); 
      nodes = []; 
      level += 1; 
     } 

     current = temporary.shift(); 

     // Check current's children. 
     if (current !== null) 
     { 
      var left = current.left; 
      var right = current.right; 

      temporary.push(left); 
      nodes.push(left); 

      temporary.push(right); 
      nodes.push(right); 
     } 
     else 
     { 
      // Null nodes fill spaces used to maintain the structural alignment of the tree. 
      nodes.push(null); 
      nodes.push(null); 
     } 
    } 

    // Push remaining nodes. 
    if (nodes.length > 0) 
    { 
     tree.push(nodes); 
    } 

    return tree; 
} 

Answer 2

public void bfs(Node root) { 
    Queue<Node> q = new LinkedList<Node>(); 
    Node dummy = new Node(null); 

    q.add(root); 
    q.add(dummy); 

    while(!q.isEmpty()) { 
     Node curr = q.poll(); 

     if(curr != null) { 
      System.out.print(curr.data + " "); 

      if(curr.left != null) 
       q.insert(curr.left); 
      if(curr.right !== null) 
       q.insert(curr.right); 
     } else { 
      System.out.println(); 
      if(!q.isEmpty()) 
       q.insert(dummy); 
     } 
    } 
} 

このコードはnullで-間のノードを表示しません：

はここでレベル順トラバーサルのための私の方法です。