javascript - 关于 javascript 和 BST 递归的初学者问题

Question

我正在尝试拓宽我对递归的有限理解。我一直在研究二叉搜索树，目前正在尝试实现遍历功能。我开始使用预序遍历，没问题，然后转向对我来说似乎更棘手的按序遍历。我无法自己找出递归解决方案，所以我用谷歌搜索并发现了同一答案的许多变体 -

function inOrderHelper(root) {
   if (root !== null) {
      inOrderHelper(root.left);
      console.log(root.data);
      inOrderHelper(root.right);
   }
}

非常简单的代码和更简单的解释，但都没有帮助我理解这个函数到底在做什么。所以，既然你们之前给了我很大的帮助，我希望你们能帮助我扩展我的知识。

1. 程序如何知道在树完成之前停止？在我看来，它应该继续转到运行者的左侧节点，直到它为空，此时它将跳过console.log
2. 程序如何知道节点已经被打印？在我看来，它只会在遍历到最大值之前重复或一次打印最小值，但显然节点正在以某种方式被检查。
3. 如何打印所有值？例如，如果第二小的值是第三小的值的右节点，那么第二小的值如何解释？

Answer 1

理解代码的最简单方法通常是使用调试器进行尝试。 Chrome 有一个 excellent debugger您可以使用它来逐行单步执行代码，因为它是实时运行的。

下一个最简单的方法是使用控制台日志打印出正在发生的事情，这就是大多数超过一定年龄的程序员在调试器使事情变得更容易之前弄清楚发生了什么的方式。

由于我无法坐在您旁边打开调试器，所以让我们做下一个最好的事情并添加一些控制台日志，以便我们可以看到发生了什么:

function inOrderHelper(root) {
   console.group("Entering inOrderHelper with ", root);
   if (root !== null && root !== undefined) {
      console.log("Root is not null, so continue");

      console.group("Traversing down the left node");
      inOrderHelper(root.left);
      console.groupEnd();

      console.log("The root value is ", root.value);

      console.group("Traversing down the right node");
      inOrderHelper(root.right);
      console.groupEnd();
   } else {
      console.log("Root is null, so back up");
   }
   console.log("Exiting inOrderHelper");
   console.groupEnd();
}

让我们尝试一个 BST 示例:

在 JavaScript 中可以将其构造为如下所示:

{
  left: {
    left: {
      value: 1,
    },
    value: 2,
    right: {
      value: 3,
    },
  },
  value: 4,
  right: {
    value: 5,
  },
}

您可以run this code in your browser's dev tools通过粘贴上面的函数(并按 Enter 键)，然后像这样调用它:

inOrderHelper({
  left: {
    left: {
      value: 1,
    },
    value: 2,
    right: {
      value: 3,
    },
  },
  value: 4,
  right: {
    value: 5,
  },
})

结果应该是这样的:

Entering inOrderHelper with  {left: {…}, value: 4, right: {…} }
  Root is not null, so continue
  Traversing down the left node
  Entering inOrderHelper with  {left: {…}, value: 2, right: {…}}
    Root is not null, so continue
    Traversing down the left node
    Entering inOrderHelper with  { value: 1 }
      Root is not null, so continue
      Traversing down the left node
      Entering inOrderHelper with  undefined
        Root is null, so back up
        Exiting inOrderHelper

      The root value is  1

      Traversing down the right node
      Entering inOrderHelper with  undefined
        Root is null, so back up
        Exiting inOrderHelper
      Exiting inOrderHelper

    The root value is 2

    Traversing down the right node
    Entering inOrderHelper with { value: 3 }
      Root is not null, so continue
      Traversing down the left node
      Entering inOrderHelper with  undefined
        Root is null, so back up
        Exiting inOrderHelper

      The root value is  3

      Traversing down the right node
      Entering inOrderHelper with  undefined
        Root is null, so back up
        Exiting inOrderHelper
      Exiting inOrderHelper
    Exiting inOrderHelper

  The root value is 4

  Traversing down the right node
  Entering inOrderHelper with { value: 5 }
    Root is not null, so continue
    Traversing down the left node
    Entering inOrderHelper with  undefined
      Root is null, so back up
      Exiting inOrderHelper

    The root value is 5

    Traversing down the right node
    Entering inOrderHelper with  undefined
      Root is null, so back up
      Exiting inOrderHelper
    Exiting inOrderHelper
  Exiting inOrderHelper

您还可以使用在线工具，例如 BinaryTreeVisualizer ，查看动画演示。

How does the program know to stop before the tree is finished? It seems to me that it should continue to go to the runner's left node until it is null, at which point it will skip the console.log

请注意，当函数从左侧向下递归时，当递归函数返回时，控制权返回到父函数，父函数继续从右侧向下延伸。当递归函数返回时，它不会立即结束父函数。父函数像对待任何其他函数一样对待递归函数。它调用它，然后当它返回时，继续下一件事。

How does the program know that a node has already been printed? It seems to me that it would just print the minimum value repeatedly or once before traversing to the maximum value but apparently the nodes are being checked off somehow.

这就是 javascript 有点令人困惑的地方。本质上，该函数尝试从左侧和右侧向下移动，但如果根值是字符串，例如 "B"，则 root.left 和 root.right 引用不存在的属性。在 javascript 中，它不会抛出错误，而是返回 undefined。因此，当我们在 root.left 上递归并且该值为 undefined 时，我们什么也不做。

因此，在我们的示例树中:

{
  left: {
    left: {
      value: 1,
    },
    value: 2,
    right: {
      value: 3,
    },
  },
  value: 4,
  right: {
    value: 5,
  },
}

我们的第一个根是{ left: { ... }, value: 4, right: { value: 5 } }

当我们向左移动时，根现在是{ left: { value: 1 }, value: 2, right: { value: 3 } }。

当我们再次向左走时，根现在是{ value: 1 }。

当我们再次向左走时，根现在未定义，因此我们什么也不做，并返回到根为{ value: 1 }的上一个调用。

我们打印1。

然后我们转到右侧，根现在未定义，因此我们什么也不做，并返回到根为{ value: 1 }的上一个调用。

我们已经完成了 { value: 1 }，因此我们返回到上一个调用，其中根为 { left: { value: 1 }, value: 2, right: { 值:3 } }

我们打印2。

现在我们向下到右侧，并像向左侧一样重复该过程，打印 3。

然后我们回到上一个根，{ left: { ... }, value: 4, right: { value: 5 } }

我们打印4。

我们转到右侧，与前面的示例一样，打印 5。

我们返回，因为我们已经到达原始函数调用，所以我们返回并结束程序。

最终结果是我们打印了 1, 2, 3, 4, 5 ，按此顺序。

How are all the values printed? For example, if the second smallest value is the right node of the third smallest, value, how is the second smallest value account for?

我不确定你在问什么，但重要的是要注意这个函数不会对树进行排序。它只是报告值。因此，如果 BST 构造不正确(例如，较小的值是较大值的右侧)，那么它也会乱序打印这些值。