怪胎怪才方法找到BST

Question

的高度我複製此代碼http://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/

其中消除隊列目前的水平和排隊的所有節點下一級的所有節點正在發生的事情

// An iterative java program to find height of binary tree 

import java.util.LinkedList; 
import java.util.Queue; 

// A binary tree node 
class Node { 

    int data; 
    Node left, right; 

    Node(int item) { 
     data = item; 
     left = right; 
    } 
} 

class BinaryTree { 

    static Node root; 

    // Iterative method to find height of Bianry Tree 
    int treeHeight(Node node) { 
     // Base Case 
     if (node == null) { 
      return 0; 
     } 

     // Create an empty queue for level order tarversal 
     Queue<Node> q = new LinkedList(); 

     // Enqueue Root and initialize height 
     q.add(node); 
     int height = 0; 

     while (1 == 1) { 

      // nodeCount (queue size) indicates number of nodes 
      // at current lelvel. 
      int nodeCount = q.size(); 
      if (nodeCount == 0) { 
       return height; 
      } 

      height++; 


/* 

This is the part where I'm very much confused , I can understand that the peek out the 1st node in queue to newnode and removes the 1st node in queue .. 


The part I can't understand is why we add nodes to that 1st position and decrease nodeCount at the end of each loop just for running the while loop until queue gets empty ??? 


So won't we have 0 as q.size() value later ??? I'm damn confused guys !!! Help me !!! 

*/ 

      // Dequeue all nodes of current level and Enqueue all 
      // nodes of next level 
      while (nodeCount > 0) { 
       Node newnode = q.peek(); 
       q.remove(); 
       if (newnode.left != null) { 
        q.add(newnode.left); 
       } 
       if (newnode.right != null) { 
        q.add(newnode.right); 
       } 
       nodeCount--; 
      } 
     } 
    } 

    // Driver program to test above functions 
    public static void main(String args[]) { 

     BinaryTree tree = new BinaryTree(); 
     tree.root = new Node(1); 
     tree.root.left = new Node(2); 
     tree.root.right = new Node(3); 
     tree.root.left.left = new Node(4); 
     tree.root.left.right = new Node(5); 
     System.out.println("Height of tree is " + tree.treeHeight(root)); 

    } 
} 

我無法理解的部分

Answer 1

若見註釋使其清零：

 // Dequeue all nodes of current level and Enqueue all 
     // nodes of next level 
     while (nodeCount > 0) { 

      //make a copy of the node at the top of the queue 
      Node newnode = q.peek(); 

      //remove the node to be checked from the queue so it will not be checked again 
      q.remove(); 

      //since node was removed, update the number of nodes to be checked 
      nodeCount--; 

      //check top node is connected to other nodes 
      if (newnode.left != null) { 
       q.add(newnode.left); //add left node to queue to be checked 
      } 
      if (newnode.right != null) { 
       q.add(newnode.right); //add right node to queue to be checked 
      } 
     } 

Answer 2

想象一下，我們在下一層有一棵樹，其中有n個節點。所以nodeCount是n。

while循環將迭代隊列中的第一個n值。回想一下，隊列是FIFO，所以只有第一個n節點將被彈出。添加的新節點不會添加到您寫的第一個位置，而是添加到最後一個位置（隊列，而不是堆棧）。

因此，循環將只通過n節點運行，留下隊列中剩下的部分作爲下一層節點。

---

例如：假設你有3節點如下：

Removed: none 
Queue: ['level_a_1', 'level_a_2', 'level_a_3'] 

在這種情況下，nodeCount是3。從上一層

Removed: 'level_a_1' 
Queue: ['level_a_2', 'level_a_3', 'level_b_1', 'level_b_2'] 

但是，正如你所看到的，要去除殘留2元素仍在：當我們排隊的新元素，它們被添加到年底。