1
var count = function(tree) {
    var stack = [];
    var count = 0;
    for (var node = tree; node; count++, node = stack.pop()) {
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    return count;
};

上面的代码工作并返回二叉树中的节点数。

我很困惑这是如何工作的。不var stack = [];创建空数组?

如果是这样,在 for 循环中设置时 node 是否不会变为 0,从而使两个 if 语句都返回 false 并且不运行?

编辑:我刚刚意识到代码node = stack.pop()在循环体结束之前不会被执行。因此,直到该点的节点将包含传递到过程中的当前节点(从头节点开始)。

为这个平凡的问题道歉,我想该睡觉了

4

3 回答 3

3

您可以将其重写为:

var count = function(tree) {
    var stack = [];
    var count = 0;
    var node = tree; // set node to the tree (the tree's root node)
    while (node) { // while the node is not null
        // The way these pushes are done, it's basically doing a depth first search
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
        count++;
        node = stack.pop();
    }
    return count;
};

换句话说,node它在运行时不会变为零,因为它stack是空的。它设置为tree,而不是stack你可以看到它在这里工作

于 2012-09-15T01:21:45.680 回答
2

我提供了评论并创建了一个JS Fiddle。我希望这有帮助

    var count = function(tree) {
    // Stack is by default empty (empty array)
    var stack = [];

    var count = 0;

    // Initially set node to the tree root. 'node' always points to the item being processed. 
    // Each node can have left and right children. 
    // They can be null as well.
    // Comparison is to check if the 'node' is undefined or null 
    // count is incremented if a left or right children is found. 
    // stack.pop() removes the top most element from the array/stack. 

    for (var node = tree; node; count++, node = stack.pop()) {

      // verify if left child exists, then push. This will add to the count when it is popped.  

      if (node.left) stack.push(node.left);

      // verify if right child exists, then push. This will add to the count when it is popped.

  if (node.right) stack.push(node.right);
    }
    return count;
};
于 2012-09-15T01:20:58.103 回答
0
// Count is a function that takes a binary tree, each node in the binary tree
// has a left and a right child. The tree itself is also such a note, namely
// the root node of the tree. What Count does with this tree is count the
// amount of nodes.
var count = function(tree) {
    // We first create a new stack, which we plan to use for counting.        
    var stack = [];

    // The initial count is zero.
    var count = 0;

    // Initial: We first take the root node.
    // Condition: As long as node exists.
    // Incrementation: We increment count, and take another node of the stack.
    for (var node = tree; node; count++, node = stack.pop()) {
        // For the current node, place it's left and right node on the stack.
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }

    // Remember: Init --> Body --> Incr --> Cond --> Body --> Incr --> Cond ...

    // Now that all nodes have passed through the stack, return the count.
    return count;
};

假设树是这样的:

   1
  / \
 2   3
    / \
   4   5

事情是这样的:

  • 堆栈为空,计数为 0。
  • 它以“1”开始,在堆栈中添加子“2”和“3”。
  • 它增加计数(0 - > 1)并获取堆栈的一个节点,即“2”。
  • 它以“2”继续,它没有孩子。
  • 它增加计数 (1 -> 2) 并获取堆栈的一个节点,即“3”。
  • 它以“2”继续,它在堆栈上添加子“4”和“5”。
  • 它增加计数(2 -> 3)并获取堆栈的一个节点,即“4”。
  • 它以“4”继续,它没有孩子。
  • 它增加计数(3 -> 4)并获取堆栈的一个节点,即“5”。
  • 它以“5”继续,它没有孩子。
  • 它增加了计数(4 -> 5)并且不能获取堆栈的节点,它会停止。
  • 最终计数 5 被返回。
于 2012-09-15T01:27:57.467 回答