Geek for Geeks 方法找到 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

假设我们有一棵树，下一层有 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 个元素仍然来自上一层。

Answer 2

看看评论是否清楚：

        // 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
            }
        }

Geek for Geeks 方法找到 BST 的高度

Geek for geeks method to find height of BST

java

algorithm

queue

binary-search-tree