了解 BST 遍历的打印输出
Understanding printed output for a BST traversal
我正在尝试了解以下代码的工作原理。代码按应有的方式执行，但我不理解其中的部分内容。
二叉搜索树的中序遍历方法：
def traverse(self):
def io(node):
print("restart") #added to code see whats happening
if node is not None: print("b4 app", node.data) #added to code see whats happening
if node.left: io(node.left)
result.append(node.data)
if node is not None: print("aft app",node.data,node.right is None) #added to code see whats happening
if node.right: #[1] skipped bc node.right is None
print("inside right") #added to code see whats happening
io(node.right)
if self.root is None:
return None
else:
result=[]
io(self.root)
return result
这是二叉搜索树 Node class 的结构：
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left=left
self.right=right
这是遍历 BST 的输出：
restart
b4 app 9
restart
b4 app 4 #[3]
restart
b4 app 3
aft app 3 True # <--- I thought it would end here? [0]
aft app 4 False #[2]
inside right
restart
b4 app 6
aft app 6 True
aft app 9 False
inside right
restart
b4 app 17
aft app 17 True
[3, 4, 6, 9, 17] #<-- ordered list of nodes (this output is correct)
它正在遍历的 BST：
"""
9
/ \
4 17
/ \
3 6
"""
函数到达我指向的点后（见[0]），node.right是None，因此代码中的下一个if语句是跳过（参见 [1]）。这是代码最后一次在结束前再次调用自身（据我所知？）。
如果跳过此 if 语句 -- 最后一次调用 io 函数 -- 递归如何继续？
此外，从输出的下一行可以看出（参见 [2]），它继续 node=4、node.left=3、node.right=6，即node=3 的父级并被提前传递到函数中（参见 [3]）。
那么 io 函数是如何被再次调用的，为什么输入是 node=4？
这段代码写 tree traversal 是一种非常混乱的方式，但它看起来基本上是正确的。此外，输出打印在不寻常的位置并带有误导性标签，因此让我们在继续您的问题之前彻底重写它。
下面是编写中序二叉树遍历的直接方法：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node):
if node:
yield from traverse(node.left)
yield node
yield from traverse(node.right)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node in tree.inorder():
print(node.data, end=" ") # => 3 4 6 9 17
我们唯一需要的分支是检查根是否为 None——最好避免担心 child 递归调用。如果它们是 None，这个单一分支将在 child stack frame.
中处理该条件
上面的代码 returns generator 比创建列表更 memory-friendly 并且在语法上更简单。
我还会在函数之外继续打印。传入回调是避免生成 side effect 的常用方法，但是使用上面的生成器方法可以通过循环完成相同的结果，让我们将打印保留在调用者中。
如果出于调试目的确实需要打印，我建议使用空格缩进，这样可以将输出变成树状，更容易理解：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node, depth=0):
if node:
yield from traverse(node.left, depth + 1)
yield node, depth
yield from traverse(node.right, depth + 1)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node, depth in tree.inorder():
print(" " * (depth * 2) + str(node.data))
这给出了树的side-view：
3
4
6
9
17
使用缩进技巧可以更轻松地可视化树，这是您的 pre/in/post-order 打印的 cleaned-up 版本，它应该给出遍历的清晰图片：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def print_traversals_pedagogical(self):
preorder = []
inorder = []
postorder = []
def traverse(node, depth=0):
if node:
preorder.append(node.data)
print(" " * depth + f"entering {node.data}")
traverse(node.left, depth + 1)
inorder.append(node.data)
print(" " * depth + f"visiting {node.data}")
traverse(node.right, depth + 1)
postorder.append(node.data)
print(" " * depth + f"exiting {node.data}")
traverse(self.root)
print("\npreorder ", preorder)
print("inorder ", inorder)
print("postorder", postorder)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
tree.print_traversals_pedagogical()
输出：
entering 9
entering 4
entering 3
visiting 3
exiting 3
visiting 4
entering 6
visiting 6
exiting 6
exiting 4
visiting 9
entering 17
visiting 17
exiting 17
exiting 9
preorder [9, 4, 3, 6, 17]
inorder [3, 4, 6, 9, 17]
postorder [3, 6, 4, 17, 9]
现在我们可以将上面的输出与您的代码联系起来并消除一些混淆。
首先，让我们翻译您的输出标签以匹配上面显示的标签：
restart 和 b4 app 做同样的事情所以你应该忽略它以避免混淆。 if node is not None: print("b4 app", node.data) 始终为真——我们在调用者中保证 node 不会是 None.b4 app -> entering（或将新调用推入堆栈）。aft app -> visiting（顺序）。再次保证 if node is not None: 为真，应将其删除。 parent 调用会检查这一点，即使他们没有检查，程序也会在上面使用 node.data.inside right 令人困惑——这是一个有序打印，但仅适用于具有 child 权限的节点。我不确定这会增加什么价值，所以我会忽略它。
请注意，您没有 exiting（弹出调用堆栈 frame/postorder）打印语句。
基于此背景，让我们回答您的问题：
This is the last time where the code calls itself again before it ends (as far as I can see?).
是，该节点即将退出。需要明确的是，函数 调用自身是因为它是递归的，但树中的每个节点只有一次调用。
If this if statement is skipped -- last time the io function is called -- how does the recursion continue?
弹出调用堆栈并从它在 parent 中断的地方继续执行。这不是最后一次调用 io 因为 parent 可以（和它的 parents 或者它的 parents' children）可以（并且做）产生其他呼叫。
So how was the io function called again and why is node=4 the input?
它没有被再次调用——node=4 的调用框架暂停等待它的 children 解决，当控制返回给它时，它从它停止的地方继续。
让我们将我的输出与您的输出联系起来：
visiting 3 # this is your `aft app 3 True [0]`
exiting 3 # you don't have this print for leaving the node
visiting 4 # this is your `aft app 4 False #[2]`
您可以看到我们退出了 node=3 的调用框架。此时，node=4 已完成遍历其所有左后代（只有一个），然后在继续其右 child.
之前按顺序访问其自身的值
尝试在上面的代码中使用不同的树结构，并将打印的 debug/pedagogical 遍历与您的理解进行比较。
我正在尝试了解以下代码的工作原理。代码按应有的方式执行，但我不理解其中的部分内容。
二叉搜索树的中序遍历方法：
def traverse(self):
def io(node):
print("restart") #added to code see whats happening
if node is not None: print("b4 app", node.data) #added to code see whats happening
if node.left: io(node.left)
result.append(node.data)
if node is not None: print("aft app",node.data,node.right is None) #added to code see whats happening
if node.right: #[1] skipped bc node.right is None
print("inside right") #added to code see whats happening
io(node.right)
if self.root is None:
return None
else:
result=[]
io(self.root)
return result
这是二叉搜索树 Node class 的结构：
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left=left
self.right=right
这是遍历 BST 的输出：
restart
b4 app 9
restart
b4 app 4 #[3]
restart
b4 app 3
aft app 3 True # <--- I thought it would end here? [0]
aft app 4 False #[2]
inside right
restart
b4 app 6
aft app 6 True
aft app 9 False
inside right
restart
b4 app 17
aft app 17 True
[3, 4, 6, 9, 17] #<-- ordered list of nodes (this output is correct)
它正在遍历的 BST：
"""
9
/ \
4 17
/ \
3 6
"""
函数到达我指向的点后（见[0]），node.right是None，因此代码中的下一个if语句是跳过（参见 [1]）。这是代码最后一次在结束前再次调用自身（据我所知？）。
如果跳过此 if 语句 -- 最后一次调用 io 函数 -- 递归如何继续？
此外，从输出的下一行可以看出（参见 [2]），它继续 node=4、node.left=3、node.right=6，即node=3 的父级并被提前传递到函数中（参见 [3]）。
那么 io 函数是如何被再次调用的，为什么输入是 node=4？
这段代码写 tree traversal 是一种非常混乱的方式，但它看起来基本上是正确的。此外，输出打印在不寻常的位置并带有误导性标签，因此让我们在继续您的问题之前彻底重写它。
下面是编写中序二叉树遍历的直接方法：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node):
if node:
yield from traverse(node.left)
yield node
yield from traverse(node.right)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node in tree.inorder():
print(node.data, end=" ") # => 3 4 6 9 17
我们唯一需要的分支是检查根是否为 None——最好避免担心 child 递归调用。如果它们是 None，这个单一分支将在 child stack frame.
中处理该条件上面的代码 returns generator 比创建列表更 memory-friendly 并且在语法上更简单。
我还会在函数之外继续打印。传入回调是避免生成 side effect 的常用方法，但是使用上面的生成器方法可以通过循环完成相同的结果，让我们将打印保留在调用者中。
如果出于调试目的确实需要打印，我建议使用空格缩进，这样可以将输出变成树状，更容易理解：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def inorder(self):
def traverse(node, depth=0):
if node:
yield from traverse(node.left, depth + 1)
yield node, depth
yield from traverse(node.right, depth + 1)
return traverse(self.root)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
for node, depth in tree.inorder():
print(" " * (depth * 2) + str(node.data))
这给出了树的side-view：
3
4
6
9
17
使用缩进技巧可以更轻松地可视化树，这是您的 pre/in/post-order 打印的 cleaned-up 版本，它应该给出遍历的清晰图片：
from collections import namedtuple
class Tree:
def __init__(self, root):
self.root = root
def print_traversals_pedagogical(self):
preorder = []
inorder = []
postorder = []
def traverse(node, depth=0):
if node:
preorder.append(node.data)
print(" " * depth + f"entering {node.data}")
traverse(node.left, depth + 1)
inorder.append(node.data)
print(" " * depth + f"visiting {node.data}")
traverse(node.right, depth + 1)
postorder.append(node.data)
print(" " * depth + f"exiting {node.data}")
traverse(self.root)
print("\npreorder ", preorder)
print("inorder ", inorder)
print("postorder", postorder)
if __name__ == "__main__":
Node = namedtuple("Node", "data left right")
"""
9
/ \
4 17
/ \
3 6
"""
tree = Tree(
Node(
9,
Node(
4,
Node(3, None, None),
Node(6, None, None),
),
Node(17, None, None)
)
)
tree.print_traversals_pedagogical()
输出：
entering 9
entering 4
entering 3
visiting 3
exiting 3
visiting 4
entering 6
visiting 6
exiting 6
exiting 4
visiting 9
entering 17
visiting 17
exiting 17
exiting 9
preorder [9, 4, 3, 6, 17]
inorder [3, 4, 6, 9, 17]
postorder [3, 6, 4, 17, 9]
现在我们可以将上面的输出与您的代码联系起来并消除一些混淆。
首先，让我们翻译您的输出标签以匹配上面显示的标签：
restart和b4 app做同样的事情所以你应该忽略它以避免混淆。if node is not None: print("b4 app", node.data)始终为真——我们在调用者中保证node不会是 None.b4 app->entering（或将新调用推入堆栈）。aft app->visiting（顺序）。再次保证if node is not None:为真，应将其删除。 parent 调用会检查这一点，即使他们没有检查，程序也会在上面使用node.data. 的行上崩溃
inside right令人困惑——这是一个有序打印，但仅适用于具有 child 权限的节点。我不确定这会增加什么价值，所以我会忽略它。
请注意，您没有 exiting（弹出调用堆栈 frame/postorder）打印语句。
基于此背景，让我们回答您的问题：
This is the last time where the code calls itself again before it ends (as far as I can see?).
是，该节点即将退出。需要明确的是，函数 调用自身是因为它是递归的，但树中的每个节点只有一次调用。
If this
ifstatement is skipped -- last time theiofunction is called -- how does the recursion continue?
弹出调用堆栈并从它在 parent 中断的地方继续执行。这不是最后一次调用 io 因为 parent 可以（和它的 parents 或者它的 parents' children）可以（并且做）产生其他呼叫。
So how was the
iofunction called again and why isnode=4the input?
它没有被再次调用——node=4 的调用框架暂停等待它的 children 解决，当控制返回给它时，它从它停止的地方继续。
让我们将我的输出与您的输出联系起来：
visiting 3 # this is your `aft app 3 True [0]`
exiting 3 # you don't have this print for leaving the node
visiting 4 # this is your `aft app 4 False #[2]`
您可以看到我们退出了 node=3 的调用框架。此时，node=4 已完成遍历其所有左后代（只有一个），然后在继续其右 child.
尝试在上面的代码中使用不同的树结构，并将打印的 debug/pedagogical 遍历与您的理解进行比较。