级别顺序，树遍历 - 如何跟踪级别？

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

当知道节点数量增加一倍时，可以跟踪该级别。 例如，在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在两者之间。