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 ループ内で設定されたときに 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設定されます。あなたはそれがここで働くのを見ることができます。treestack

于 2012-09-15T01:21:45.680 に答える
2

コメントを提供し、JSFiddleを作成しました。これがお役に立てば幸いです

    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 に答える