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用this.root调用，这意味着上例中的参数为A。 node.left存在，紧接着用参数traverseInOrder调用B。
  • 在B的调用中，node.left存在，紧接着用参数traverseInOrder调用D。
    • 在D的调用中，node.left不存在（node.left虚假），因此使用参数result.push(node.data);调用D。在下一步中，node.right是伪造的，它跟随traversInOrder并带有参数D。我们回到B。
  • 我们回到调用B，并且由于刚完成带有traversInOrder的D，因此将使用参数result.push(node.data)调用B。接下来，node.right是真实的，因此traverseInOrder与node.right一起被调用。
    • 在E处E虚假，使用参数node.left调用result.push。 E虚假是此处结束了node.right的呼叫。我们回到调用E的地方，因为当我们从此处返回到A的调用时，它就在此时结束。
• [在使用参数B调用时，我们刚刚完成了左节点，A被称为result.push(node.data);，下一个A是真实的，因此使用右侧节点调用了node.right，这意味着参数result.push(node.data)。] >

与C，F，G相同。