关于使用 BST 在 javascript 中递归的初学者问题
beginner question on recursion in javascript with BST
我正在努力拓宽我对递归的有限理解。我一直在研究二叉搜索树，目前正在尝试实现遍历功能。我从使用预序遍历开始，没有问题，然后转向对我来说似乎更棘手的顺序。我无法自己找出递归解决方案，所以我用谷歌搜索并找到了相同答案的许多变体-
function inOrderHelper(root) {
if (root !== null) {
inOrderHelper(root.left);
console.log(root.data);
inOrderHelper(root.right);
}
}
非常简单的代码和更简单的解释，其中 none 帮助我理解了这个函数到底在做什么。所以，既然你们之前帮了我大忙，我希望你们能帮助我在这里扩展我的知识。
- 程序如何知道在树完成之前停止？在我看来，它应该继续走到跑步者的左节点，直到它为空，此时它将跳过 console.log
- 程序如何知道一个节点已经被打印出来了？在我看来，它只会在遍历到最大值之前重复或一次打印最小值，但显然节点正在以某种方式被检查。
- 如何打印所有值？例如，如果第二小的值是第三小的value的右节点，那么第二小的值怎么占？
1 function inOrder(root) {
2 if (!root) return;
3 inOrderHelper(root.left);
4 console.log(root.data);
5 inOrderHelper(root.right);
6 }
7
8 inOrder(root) // 2 4 6 7 9
Q1
第 2 行永远停止递归。
在图表的左下角，节点 2 被评估，然后 inOrder 以 left 作为参数调用，即 undefined。第 2 行的计算结果为 true 并立即计算为 returns。一旦它返回到调用点，就继续执行。评估第 4 行，这意味着 2 被打印到控制台。然后评估第 5 行。每次算法遇到没有左子树或右子树的节点时都会发生这种情况。
Q2
它利用编程语言本身基于堆栈的特性来跟踪它在图中的位置。每次调用函数时，都会将一个新的堆栈帧添加到堆栈中，而每次函数完成时，都会删除该堆栈帧。
Q3
节点是根据它们在图中的位置而不是它们的值打印的。
const root = {
data: 7,
left: {
data: 4,
left: {
data: 2
},
right: {
data: 6
}
},
right: {
data: 9
}
}
function inOrder(root) {
if (!root)
return;
inOrder(root.left);
console.log(root.data);
inOrder(root.right);
}
inOrder(root)
理解代码最简单的方法通常是使用调试器进行尝试。 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 粘贴上面的函数（并按回车键）然后像这样调用它：
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
注意当函数向左向下递归时，当递归函数returns时，控制returns到父函数，继续向右向下。当一个递归函数returns时，它不会立即结束父函数。父函数像对待任何其他函数一样对待递归函数。它会调用它，然后，当它 return 时，继续下一件事。
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 中，它不会抛出错误，而只是 returns undefined。因此，当我们递归 root.left 并且该值为 undefined 时，我们什么都不做。
因此，在我们的示例树中：
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
我们的第一个根是{ left: { ... }, value: 4, right: { value: 5 } }
当我们向左移动时，root 现在是 { left: { value: 1 }, value: 2, right: { value: 3 } }。
当我们再次向左走时，根现在是 { value: 1 }。
当我们再次向左移动时，根现在是 undefined，所以我们什么也不做，return 到之前的调用，根是 { value: 1 }。
打印1.
然后我们向右走，根现在是 undefined，所以我们什么都不做，return 到之前的调用，根是 { value: 1 }.
我们已经完成了 { value: 1 }，所以我们 return 到上一个根为 { left: { value: 1 }, value: 2, right: { value: 3 } }
的调用
打印2.
现在我们向右走，和向左一样重复这个过程，打印 3。
然后我们回到上一个根，{ left: { ... }, value: 4, right: { value: 5 } }
打印4.
我们向右走，与前面的示例一样，打印 5。
我们 return 并且，由于我们已经到达原始函数调用，我们 return 并结束程序。
最后的结果是我们依次打印了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 构造不正确（例如，较小的值是较大值的右边），那么它也会乱序打印这些值。
正如其他人所说，使用 Chrome 调试器逐步执行此代码是开始了解正在发生的事情的好方法。我建议您也绘制自己的图片，类似于其他人在他们的答案中显示的图片，以帮助您了解调试器正在做什么。
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
函数不断访问左节点，直到到达叶子。然后它逐渐returns，打印出数据，并访问每个正确的节点。程序将在访问树中的每个节点后终止。
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.
它不会像您假设的那样跟踪访问过的节点。它尽可能地遍历树的左侧，然后返回根并沿途访问右侧。
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?
因为在每次递归调用时，它都会打印当前 "root" 的值。
我正在努力拓宽我对递归的有限理解。我一直在研究二叉搜索树，目前正在尝试实现遍历功能。我从使用预序遍历开始，没有问题，然后转向对我来说似乎更棘手的顺序。我无法自己找出递归解决方案，所以我用谷歌搜索并找到了相同答案的许多变体-
function inOrderHelper(root) {
if (root !== null) {
inOrderHelper(root.left);
console.log(root.data);
inOrderHelper(root.right);
}
}
非常简单的代码和更简单的解释，其中 none 帮助我理解了这个函数到底在做什么。所以，既然你们之前帮了我大忙，我希望你们能帮助我在这里扩展我的知识。
- 程序如何知道在树完成之前停止？在我看来，它应该继续走到跑步者的左节点，直到它为空，此时它将跳过 console.log
- 程序如何知道一个节点已经被打印出来了？在我看来，它只会在遍历到最大值之前重复或一次打印最小值，但显然节点正在以某种方式被检查。
- 如何打印所有值？例如，如果第二小的值是第三小的value的右节点，那么第二小的值怎么占？
1 function inOrder(root) {
2 if (!root) return;
3 inOrderHelper(root.left);
4 console.log(root.data);
5 inOrderHelper(root.right);
6 }
7
8 inOrder(root) // 2 4 6 7 9
Q1
第 2 行永远停止递归。
在图表的左下角，节点 2 被评估，然后 inOrder 以 left 作为参数调用，即 undefined。第 2 行的计算结果为 true 并立即计算为 returns。一旦它返回到调用点，就继续执行。评估第 4 行，这意味着 2 被打印到控制台。然后评估第 5 行。每次算法遇到没有左子树或右子树的节点时都会发生这种情况。
Q2
它利用编程语言本身基于堆栈的特性来跟踪它在图中的位置。每次调用函数时，都会将一个新的堆栈帧添加到堆栈中，而每次函数完成时，都会删除该堆栈帧。
Q3
节点是根据它们在图中的位置而不是它们的值打印的。
const root = {
data: 7,
left: {
data: 4,
left: {
data: 2
},
right: {
data: 6
}
},
right: {
data: 9
}
}
function inOrder(root) {
if (!root)
return;
inOrder(root.left);
console.log(root.data);
inOrder(root.right);
}
inOrder(root)
理解代码最简单的方法通常是使用调试器进行尝试。 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 粘贴上面的函数（并按回车键）然后像这样调用它：
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
注意当函数向左向下递归时，当递归函数returns时，控制returns到父函数，继续向右向下。当一个递归函数returns时，它不会立即结束父函数。父函数像对待任何其他函数一样对待递归函数。它会调用它，然后，当它 return 时，继续下一件事。
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 中，它不会抛出错误，而只是 returns undefined。因此，当我们递归 root.left 并且该值为 undefined 时，我们什么都不做。
因此，在我们的示例树中：
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
我们的第一个根是{ left: { ... }, value: 4, right: { value: 5 } }
当我们向左移动时，root 现在是 { left: { value: 1 }, value: 2, right: { value: 3 } }。
当我们再次向左走时，根现在是 { value: 1 }。
当我们再次向左移动时，根现在是 undefined，所以我们什么也不做，return 到之前的调用，根是 { value: 1 }。
打印1.
然后我们向右走，根现在是 undefined，所以我们什么都不做，return 到之前的调用，根是 { value: 1 }.
我们已经完成了 { value: 1 }，所以我们 return 到上一个根为 { left: { value: 1 }, value: 2, right: { value: 3 } }
打印2.
现在我们向右走，和向左一样重复这个过程，打印 3。
然后我们回到上一个根，{ left: { ... }, value: 4, right: { value: 5 } }
打印4.
我们向右走，与前面的示例一样，打印 5。
我们 return 并且，由于我们已经到达原始函数调用，我们 return 并结束程序。
最后的结果是我们依次打印了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 构造不正确（例如，较小的值是较大值的右边），那么它也会乱序打印这些值。
正如其他人所说，使用 Chrome 调试器逐步执行此代码是开始了解正在发生的事情的好方法。我建议您也绘制自己的图片，类似于其他人在他们的答案中显示的图片，以帮助您了解调试器正在做什么。
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
函数不断访问左节点，直到到达叶子。然后它逐渐returns，打印出数据，并访问每个正确的节点。程序将在访问树中的每个节点后终止。
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.
它不会像您假设的那样跟踪访问过的节点。它尽可能地遍历树的左侧，然后返回根并沿途访问右侧。
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?
因为在每次递归调用时，它都会打印当前 "root" 的值。