深入了解 JavaScript 递归和调用栈优先遍历
Understand JavaScript Recursion and Call Stack in Depth First Traversal
我有一个完美的平衡二叉树：
1
/ \
2 5
/ \ / \
3 4 6 7
具有DF遍历的简单节点结构：
function TreeNode(val){
this.val = val
this.left = this.right = null
this.addLeft = function(node){
this.left = node
}
this.addRight = function(node){
this.right = node
}
}
function visit(node){
console.log(node.val)
}
function traverse(node){
if (node == null) return
visit(node)
if(node.left){
traverse(node.left)
}
if(node.right){
traverse(node.right)
}
}
我创建节点来表示树结构：
let rootNode = new TreeNode(1)
let node_A = new TreeNode(2)
let node_B = new TreeNode(5)
let node_C = new TreeNode(3)
let node_D = new TreeNode(4)
let node_E = new TreeNode(6)
let node_F = new TreeNode(7)
rootNode.addLeft(node_A)
rootNode.addRight(node_B)
node_A.addLeft(node_C)
node_A.addRight(node_D)
node_B.addLeft(node_E)
node_B.addRight(node_F)
调用 traverse(rootNode) 正确打印出来：
1
2
3
4
5
6
7
我了解递归的工作原理，但仍然对 JavaScript 如何在调用堆栈中处理它感到有点困惑。 traverse(rootNode) 首先被放入调用堆栈，然后它到达 if 条件，在这里它检查 rootNode 是否还有一个节点，所以它继续沿着路径向下直到它到达最后一个节点，这是TreeNode(3)。调用栈是这样的：
| |
| |
| traverse(TreeNode(3)) |
| traverse(TreeNode(2)) |
| traverse(rootNode) |
|_____________________________| |
TreeNode(3) 没有任何 node.left 或 node.right 所以它 returns 到 if 条件，然后向下检查 node.right，第二个条件。然后它看到 TreeNode(2) 确实有一个 node.right 并遍历到 TreeNode(4) 并将其压入堆栈。
现在这部分让我很困惑。当 traverse(TreeNode(4) 完成时，JavaScript 如何跟踪调用 rootNode.right？换句话说，它怎么知道在左分支结束时切换到右分支？因为输出打印 1 到 7，所以调用堆栈必须是：
| |
| traverse(TreeNode(7)) |
| traverse(TreeNode(6)) |
| traverse(TreeNode(5)) |
| traverse(TreeNode(4)) |
| traverse(TreeNode(3)) |
| traverse(TreeNode(2)) |
| traverse(rootNode) |
|_____________________________|
但我相信栈顶会最先弹出return，所以输出应该从7开始，而不是1。所以我的第二个问题是为什么控制台日志正确打印出从 1 到 7.
的结果
好吧，您的解释遗漏了一些重要的步骤，我认为这会让您得出一些无效的结论。特别是，堆栈永远不会像
traverse(TreeNode(7))
traverse(TreeNode(6))
traverse(TreeNode(5))
traverse(TreeNode(4))
traverse(TreeNode(3))
traverse(TreeNode(2))
traverse(rootNode)
郑重声明，其中 none 是 javascript 特有的；所以我真的认为这是关于提高你对递归的理解程度。
让我们更详细地了解您的 traverse(rootNode) 通话。所以当然调用堆栈开始像
0: traverse ( node = rootNode ) {
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
这里我使用的符号使一些事情更加明确：
- 我在通话前输入了号码；这样，例如，我可以将上述调用称为 "call 0 on the stack"
- 我展示了每次调用的参数赋值
- 我显示了每个调用背后的函数代码，箭头
=> 指示通过该特定调用的代码的当前进度。这里我们即将执行第一条指令。
按照您似乎使用的约定，最近推送的（下一个弹出）项目将显示在顶部。
所以现在 node 是 rootNode 而不是 null，它不会立即 return。在任何递归开始之前，它会在 rootNode 上调用 visit()，它会继续并打印 1。这是您的解释中似乎缺少的事情之一 - 访问节点（并打印它们的值） 在 任何递归之前，因此它们在您遍历时被打印，当您第一次到达时每个节点。
然后它检查 left 并找到一个真值（在这种情况下，另一个节点对象），所以它调用 traverse(node.left) 我们最终得到一个像
这样的堆栈
1: traverse ( node = node_A )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
所以我们再次从新的 node 值开始执行 traverse()，它不为空，所以我们继续 visit(node) - 因为 node 是 node_A，打印 2。然后它检查 left，这是真实的 (node_C)，我们得到
2: traverse ( node = node_C )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
node_C 不为空，因此它得到 visit()ed 并打印 3。现在我们检查 left，但它是错误的 (undefined)。所以我们检查 right，它也是假的 (undefined)。所以我们 return 现在堆栈显示
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
现在我们已经在堆栈中调用 1 的 traverse() 代码中途，所以我们从中断的地方（在 => 处）继续。所以现在我们检查 right，这是真的，我们得到
2: traverse ( node = node_D )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ => }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
现在visit将打印4（因为node是node_D，而left和right都是假的，所以我们return 至
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ => }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
但是堆栈上的调用 1 已经到达其代码的末尾，所以它 returns 并且我们转到
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
Call 0 从它停止的地方接起，这意味着它将要检查 right（我认为这回答了你原来的问题）。执行在右分支上的执行方式与在左分支上执行的方式完全相同，堆栈在不同时间包含对 rootNode, node_B、rootNode, node_B, node_E、rootNode, node_B 的调用（但使用部分执行的代码），然后是 rootNode, node_B, node_F，然后是最后一次 rootNode, node_B（代码即将完成），然后返回到 rootNode，然后是对 traverse 的初始调用终于 returns.
我有一个完美的平衡二叉树：
1
/ \
2 5
/ \ / \
3 4 6 7
具有DF遍历的简单节点结构：
function TreeNode(val){
this.val = val
this.left = this.right = null
this.addLeft = function(node){
this.left = node
}
this.addRight = function(node){
this.right = node
}
}
function visit(node){
console.log(node.val)
}
function traverse(node){
if (node == null) return
visit(node)
if(node.left){
traverse(node.left)
}
if(node.right){
traverse(node.right)
}
}
我创建节点来表示树结构：
let rootNode = new TreeNode(1)
let node_A = new TreeNode(2)
let node_B = new TreeNode(5)
let node_C = new TreeNode(3)
let node_D = new TreeNode(4)
let node_E = new TreeNode(6)
let node_F = new TreeNode(7)
rootNode.addLeft(node_A)
rootNode.addRight(node_B)
node_A.addLeft(node_C)
node_A.addRight(node_D)
node_B.addLeft(node_E)
node_B.addRight(node_F)
调用 traverse(rootNode) 正确打印出来：
1
2
3
4
5
6
7
我了解递归的工作原理，但仍然对 JavaScript 如何在调用堆栈中处理它感到有点困惑。 traverse(rootNode) 首先被放入调用堆栈，然后它到达 if 条件，在这里它检查 rootNode 是否还有一个节点，所以它继续沿着路径向下直到它到达最后一个节点，这是TreeNode(3)。调用栈是这样的：
| |
| |
| traverse(TreeNode(3)) |
| traverse(TreeNode(2)) |
| traverse(rootNode) |
|_____________________________| |
TreeNode(3) 没有任何 node.left 或 node.right 所以它 returns 到 if 条件，然后向下检查 node.right，第二个条件。然后它看到 TreeNode(2) 确实有一个 node.right 并遍历到 TreeNode(4) 并将其压入堆栈。
现在这部分让我很困惑。当 traverse(TreeNode(4) 完成时，JavaScript 如何跟踪调用 rootNode.right？换句话说，它怎么知道在左分支结束时切换到右分支？因为输出打印 1 到 7，所以调用堆栈必须是：
| |
| traverse(TreeNode(7)) |
| traverse(TreeNode(6)) |
| traverse(TreeNode(5)) |
| traverse(TreeNode(4)) |
| traverse(TreeNode(3)) |
| traverse(TreeNode(2)) |
| traverse(rootNode) |
|_____________________________|
但我相信栈顶会最先弹出return，所以输出应该从7开始，而不是1。所以我的第二个问题是为什么控制台日志正确打印出从 1 到 7.
好吧，您的解释遗漏了一些重要的步骤，我认为这会让您得出一些无效的结论。特别是，堆栈永远不会像
traverse(TreeNode(7))
traverse(TreeNode(6))
traverse(TreeNode(5))
traverse(TreeNode(4))
traverse(TreeNode(3))
traverse(TreeNode(2))
traverse(rootNode)
郑重声明，其中 none 是 javascript 特有的；所以我真的认为这是关于提高你对递归的理解程度。
让我们更详细地了解您的 traverse(rootNode) 通话。所以当然调用堆栈开始像
0: traverse ( node = rootNode ) {
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
这里我使用的符号使一些事情更加明确：
- 我在通话前输入了号码；这样，例如，我可以将上述调用称为 "call 0 on the stack"
- 我展示了每次调用的参数赋值
- 我显示了每个调用背后的函数代码，箭头
=>指示通过该特定调用的代码的当前进度。这里我们即将执行第一条指令。
按照您似乎使用的约定，最近推送的（下一个弹出）项目将显示在顶部。
所以现在 node 是 rootNode 而不是 null，它不会立即 return。在任何递归开始之前，它会在 rootNode 上调用 visit()，它会继续并打印 1。这是您的解释中似乎缺少的事情之一 - 访问节点（并打印它们的值） 在 任何递归之前，因此它们在您遍历时被打印，当您第一次到达时每个节点。
然后它检查 left 并找到一个真值（在这种情况下，另一个节点对象），所以它调用 traverse(node.left) 我们最终得到一个像
1: traverse ( node = node_A )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
所以我们再次从新的 node 值开始执行 traverse()，它不为空，所以我们继续 visit(node) - 因为 node 是 node_A，打印 2。然后它检查 left，这是真实的 (node_C)，我们得到
2: traverse ( node = node_C )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
node_C 不为空，因此它得到 visit()ed 并打印 3。现在我们检查 left，但它是错误的 (undefined)。所以我们检查 right，它也是假的 (undefined)。所以我们 return 现在堆栈显示
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
现在我们已经在堆栈中调用 1 的 traverse() 代码中途，所以我们从中断的地方（在 => 处）继续。所以现在我们检查 right，这是真的，我们得到
2: traverse ( node = node_D )
| => if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ }
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ => }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
现在visit将打印4（因为node是node_D，而left和right都是假的，所以我们return 至
1: traverse ( node = node_A ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| }
| if(node.right){
| traverse(node.right)
|_ => }
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
但是堆栈上的调用 1 已经到达其代码的末尾，所以它 returns 并且我们转到
0: traverse ( node = rootNode ) {
| if (node == null) return
| visit(node)
|
| if(node.left){
| traverse(node.left)
| => }
| if(node.right){
| traverse(node.right)
|_ }
Call 0 从它停止的地方接起，这意味着它将要检查 right（我认为这回答了你原来的问题）。执行在右分支上的执行方式与在左分支上执行的方式完全相同，堆栈在不同时间包含对 rootNode, node_B、rootNode, node_B, node_E、rootNode, node_B 的调用（但使用部分执行的代码），然后是 rootNode, node_B, node_F，然后是最后一次 rootNode, node_B（代码即将完成），然后返回到 rootNode，然后是对 traverse 的初始调用终于 returns.