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。当没有node.left时，会调用步骤2：result.push(node.data);
这是我不太理解的部分。现在尝试运行node.right && traverseInOrder(node.right)，但是没有node.right，但它并没有退出函数，而是返回到步骤2，result.push(node.data);。

这是否源于步骤1中多次递归调用导致的排队？

- burtonLowel

Answer 1

让我们看一个例子。假设下面这棵树将会被按照中序遍历的方式遍历。

• 第一个traverseInOrder使用this.root调用，这意味着上面示例中的参数为A。node.left存在，因此将使用参数B调用traverseInOrder。
  • 在调用B时，node.left存在，因此将使用参数D调用traverseInOrder。
    • 在调用D时，node.left不存在（node.left为假），因此将使用参数D调用result.push(node.data);。接下来，node.right为假，因此traversInOrder使用参数D结束。我们回到了B。
  • 我们回到了使用参数B的调用，并且因为使用D的traversInOrder刚刚结束，所以将使用参数B调用result.push(node.data)。由于下一个node.right为真，因此将使用node.right即E调用traverseInOrder。
    • 在E处，node.left为假，result.push将使用参数E调用。由于使用E的调用结束了，因此node.right为假。我们回到了使用A的调用，因为当我们从这里返回到B的调用时，它在此处结束。
• 在使用参数A的调用中，我们刚刚完成了左节点，因此对于A将调用result.push(node.data);，接下来node.right为真，因此将使用右节点即参数C调用result.push(node.data)。

在C、F、G方面也是一样的。

- Milan Tenk

---

这太棒了，非常感谢您花费时间和精力！ - burtonLowel

Answer 2

tenkmilan已经非常出色地展示了如何构想这段代码。

在此，我选择一种不同的路径，编写一个更简单的inorder遍历。很明显，这可以很好地映射到提供的代码中。

inorder遍历很简单。preorder和postorder是另外两种最常见的树遍历方式，它们适用于任意有限的树。Inorder只对二叉树进行定义，并使用节点的left和right子节点。遍历顺序是先（递归）遍历左子树，然后访问节点本身，最后（递归）遍历右子树。

我们可以简单地编写这样的遍历：

const inorder = (tree) =>
  tree 
    ? [
        ... inorder (tree .left),
        tree .data,
        ... inorder (tree .right)
      ]
    : []

我们有一个基本情况，即所查看的节点为空时，我们只需要返回一个空数组。在一般情况下，我们将递归调用左边的left .tree与当前节点的值以及右边的right .tree拼接在一起。

这就是中序遍历的全部内容。您可以在以下代码片段中看到它的运行：

const inorder = (tree) =>
  tree 
    ? [
        ... inorder (tree .left),
        tree .data,
        ... inorder (tree .right)
      ]
    : []

const tree = {
  data: 'F',
  left: {
    data: 'B',
    left: {data: 'A'},
    right: {
      data: 'D',
      left: {data: 'C'},
      right: {data: 'E'}
    }
  },
  right: {
    data: 'H',
    left: {data: 'G'},
    right: {data: 'I'}
  }
}

console .log (inorder (tree))

当然，这适用于作为纯JS对象存储的简单树。 但将示例代码映射回来很容易。 我猜如果您能理解这个，您可以很快理解那个。

- Scott Sauyet

---

这个回答和之前的一样出色！谢谢Scott！ - burtonLowel

太棒了的例子！<3 - jdnichollsc