Javascript：二叉搜索树中顺序遍历递归混淆

Question

给出下面的代码，我对操作顺序如何恰好获得二叉搜索树的有序遍历感到有点困惑。

BinarySearchTree.prototype.inOrder = function() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traverseInOrder(node) {       
        node.left && traverseInOrder(node.left);
        result.push(node.data);
        node.right && traverseInOrder(node.right);
      }
      traverseInOrder(this.root);
      return result;
    };
}

我尝试添加调试器语句并遵循，但我迷失了方向：

  function traverseInOrder(node) {       
    node.left && traverseInOrder(node.left); //step 1
    result.push(node.data);  //step 2
    node.right && traverseInOrder(node.right); //step 3
  }

node.left && traverseInOrder(node.left);（步骤 1）运行然后再次运行然后再次运行。最后，当没有时node.left，步骤 2 被调用：result.push(node.data);
这是它让我迷失的部分。现在它尝试运行node.right && traverseInOrder(node.right)，但没有node.right运行，但它没有退出该函数，而是返回到步骤 2 result.push(node.data);，。

这是从步骤 1 中的多个递归调用中排队的吗？

Answer 1

让我们看一个例子。让它成为下面将要遍历的树in order。

• 第一个traverseInOrder被调用 with this.root，这意味着上面示例中的参数是A。存在node.left，随后traverseInOrder用参数调用B。
  • 在调用Bexists时node.left，紧随其后的traverseInOrder是带参数的调用D。
    • 在调用中D node.left不存在（node.left为假），因此result.push(node.data);使用参数进行调用D。接下来的步骤node.right是falsy，跟着traversInOrderwith参数D就完成了。我们回到B.
  • 我们又回到call B，因为traversInOrderwithD刚刚结束，result.push(node.data)所以会调用with参数B。由于 nextnode.right是 true 所以traverseInOrder被称为 with the node.rightso with E。
    • AtE node.left为假，result.push用参数 调用E。此处结束的node.right通话是假的。E我们回到 call A，因为当我们从这里返回到 call 时，B它的调用此时就完成了。
• 在使用参数调用时，A我们刚刚完成了左节点，result.push(node.data);被调用A，并且下一个node.right是真值，因此result.push(node.data)使用右节点调用，这意味着参数C。

C、F、G 的情况也是如此。