了解BST遍历的打印输出 [英] Understanding printed output for a BST traversal
问题描述
我试图了解以下代码的工作方式.该代码将按应有的方式执行，但我不理解其中的一部分.
这是按顺序遍历二叉搜索树的一种方法:
def遍历(自己):def io(节点):print("restart")#添加到代码中以查看发生了什么如果节点不是None:将print("b4 app"，node.data)#添加到代码中以查看发生了什么如果node.left:io(node.left)result.append(node.data)如果node不为None:print("aft app"，node.data，node.right为None)#添加到代码中以查看发生了什么如果node.right:#[1]跳过了bc node.right为Noneprint("inside right")#添加到代码以查看发生了什么io(node.right)如果self.root为None:不返回别的:结果= []io(self.root)返回结果 这是二进制搜索树的 Node 类的结构:
class节点:def __init __(self，data，left = None，right = None):self.data =数据self.left =左self.right =正确 以下是遍历BST的输出:
重启b4应用9重新开始b4应用4#[3]重新开始b4应用3船尾应用程序3 True#< ---我以为它会在这里结束?[0]船尾应用程序4错误#[2]右内重新开始b4应用6船尾应用程序6 True船尾应用程序9错误右内重新开始b4应用程序17船尾应用程序17 True[3、4、6、9、17]#<-节点的有序列表(此输出正确) 正在遍历的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 ?
这段代码是编写树遍历，但从根本上看是正确的.此外，输出结果会打印在不寻常的位置并带有误导性标签，因此在继续提问之前，让我们将其重写得很整洁.
这是编写有序二叉树遍历的一种直接方法:
从集合中 导入namedtuple类树:def __init __(self，root):self.root =根def顺序(自己):def遍历(节点):如果节点:遍历的收益(node.left)屈服节点遍历的收益(node.right)返回遍历(self.root)如果__name__ =="__main__":节点= namedtuple(节点"，数据从左到右")"9/\4 17/\3 6"树=树(节点(9，节点(4，节点(3，无，无)，节点(6，无，无)，)，节点(17，无，无)))对于tree.inorder()中的节点:print(node.data，end =")#=>3 4 6 9 17 我们唯一需要的分支是检查根是否为None-最好避免担心子递归调用.如果它们为None，则该单个分支将在子堆栈框架中处理该条件.
上面的代码返回 generator 与创建列表相比，内存友好，并且在语法上更简单.
我还将在功能之外进行打印.传递回调是避免产生副作用的常见方法，但使用相同结果上方的生成器方法是通过循环完成的，使我们可以将打印内容保留在调用方中.
如果您确实需要出于调试目的而打印，我建议使用空格缩进，该缩进可使输出成树形，并且易于遵循:
从集合中 导入namedtuple类树:def __init __(self，root):self.root =根def顺序(自己):def遍历(节点，深度= 0):如果节点:遍历的收益(node.left，深度+1)屈服节点深度遍历的收益(node.right，深度+1)返回遍历(self.root)如果__name__ =="__main__":节点= namedtuple(节点"，数据从左到右")"9/\4 17/\3 6"树=树(节点(9，节点(4，节点(3，无，无)，节点(6，无，无)，)，节点(17，无，无)))对于节点，在tree.inorder()中的深度:print(" *(深度* 2)+ str(node.data)) 这给出了树的侧视图:
346917 借助这种缩进技巧，可以更轻松地可视化树，这是您的订购前/订购中/订购后打印的清理版本，应该可以清楚地看到遍历:
从集合中 导入namedtuple类树:def __init __(self，root):self.root =根def print_traversals_pedagogical(self):预购= []顺序= []邮购= []def遍历(节点，深度= 0):如果节点:preorder.append(node.data)print("* * depth + f"输入{node.data})遍历(node.left，depth + 1)inorder.append(node.data)打印(访问{node.data}"的"*深度+ f")遍历(node.right，depth + 1)postorder.append(node.data)打印("*深度+ f"(退出{node.data}"))遍历(self.root)打印("\ npreorder"，预购)打印("inorder"，inorder)打印("postorder"，postorder)如果__name__ =="__main__":节点= namedtuple(节点"，数据从左到右")"9/\4 17/\3 6"树=树(节点(9，节点(4，节点(3，无，无)，节点(6，无，无)，)，节点(17，无，无)))tree.print_traversals_pedagogical() 输出:
输入9进入4进入3来访3退出3来访4进入6来访6退出6退出4来访9进入17来访17退出17退出9预购[9，4，3，6，17]顺序[3、4、6、9、17]后期订购[3、6、4、17、9] 现在，我们可以将上面的输出与您的代码连接起来，并消除一些混乱.
首先，让我们翻译输出标签以匹配上面显示的标签:
-
重新启动与b4应用具有相同的作用，因此您应该忽略它，以免造成混淆.if节点不是None:print("b4 app"，node.data)始终为true –我们保证在调用方中node不会为None. -
b4应用->输入(或将新的调用推入堆栈). -
后部应用程序->访问(顺序).再一次，如果节点不为None，则保证node.data的上一行崩溃. -
inside right令人困惑-它是有序打印，但仅适用于具有正确子节点的节点.我不确定这会增加什么价值，所以我会忽略它.
请注意，您没有 exiting (弹出呼叫堆栈帧/后置订单)打印语句.
在这种情况下，让我们回答您的问题:
这是代码在结束之前最后一次再次调用自身(据我所知?).
是的，此节点即将退出.需要明确的是， function 之所以调用自身，是因为它是递归的，但是树中每个节点只有一个调用.
如果跳过此
if语句-上一次调用io函数-递归如何继续?
弹出调用堆栈，执行从上次在父进程中中断的地方继续执行.这不是上次调用 io 的原因，因为父母可以(及其父母或父母的子女)可以(并且确实)产生其他呼叫.
那么如何再次调用
io函数?为什么输入node = 4?
它没有再次被调用- node = 4 的调用框架已暂停，等待其子级解析，并且当控制权返回给它时，它从中断处继续执行.>
让我们将我的输出与您的输出相关联:
来访3#这是您的船尾应用程序3 True [0]"退出3#您没有离开节点的此打印造访4#这是您的`aft app 4错误#[2]` 您可以看到我们退出了 node = 3 的调用框.到那时， node = 4 已经遍历了所有左后代(只有一个)，然后在继续其右子级之前访问了它自己的值顺序.
尝试在上面的代码中使用不同的树结构，并将打印的调试/教学遍历与您的理解进行比较.
I'm trying to understand how the below code works. The code executes as it should but I don't understand parts of it.
It's a method for an in-order traversal of a binary search tree:
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
Here is the structure of the Node class for the Binary Search Tree:
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left=left
self.right=right
Here's the output traversing a 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)
The BST it's traversing:
"""
9
/ \
4 17
/ \
3 6
"""
After the function gets to the point that I pointed to (see [0]), node.right is None, therefore the next if statement in the code is skipped (see [1]). 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?
Also, as can be seen by the next line in the output (see [2]), it continues with node=4, node.left=3, node.right=6, which is node=3's parent and was passed into the function early (see [3]).
So how was the io function called again and why is node=4 the input?
This code is a very confusing way to write a tree traversal but it looks fundamentally correct. Additionally, the output is printed in unusual locations and with misleading labels, so let's rewrite this cleanly before moving on to your questions.
Here's a straightforward way to write an inorder binary 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
The only branch we need is to check whether the root is None--it's best to avoid worrying about the child recursive calls. If they're None, this single branch will handle that condition in the child stack frame.
The above code returns a generator which is more memory-friendly than creating a list and is syntactically simpler.
I'd also keep printing outside of the function. Passing in a callback is a common way to avoid producing a side effect, but using the generator approach above the same outcome is accomplished with a loop, letting us keep the print in the caller.
If you do need to print for debugging purposes, I recommend using whitespace indentation which makes the output into a tree and much easier to follow:
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))
This gives a side-view of the tree:
3
4
6
9
17
With this indentation trick to make it easier to visualize the tree, here's a cleaned-up version of your pre/in/post-order printing which should give a clear picture of the traversal:
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()
Output:
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]
Now we can connect the above output with your code and clear up some of the confusion.
First of all, let's translate your output labels to match the ones shown above:
restartdoes the same thing asb4 appso you should ignore it to avoid confusion. Theif node is not None: print("b4 app", node.data)is always true--we guarantee in the caller thatnodewill not be None.b4 app->entering(or pushing a new call onto the stack).aft app->visiting(inorder). Once again,if node is not None:is guaranteed true and should be removed. The parent call checks this and even if they didn't, the program would crash on the line above which usesnode.data.inside rightis confusing--it's an inorder print but only for nodes that have a right child. I'm not sure what value this adds so I'd ignore it.
Note that you have no exiting (popping a call stack frame/postorder) print statement.
With this context, let's answer your questions:
This is the last time where the code calls itself again before it ends (as far as I can see?).
Yes, this node is about to be exited. To be clear, the function calls itself because it's recursive, but there's only exactly one call per node in the tree.
If this
ifstatement is skipped -- last time theiofunction is called -- how does the recursion continue?
The call stack pops and execution continues where it left off in the parent. It's not the last time io was called because the parent can (and its parents or its parents' children) can (and do) spawn other calls.
So how was the
iofunction called again and why isnode=4the input?
It wasn't called again--the call frame for node=4 was paused waiting for its children to resolve and when control returned to it, it continued where it left off.
Let's relate my output to your output:
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]`
You can see we exited the call frame for node=3. At that point, node=4 had completed traversing all of its left descendants (there is only one) and then visited its own value inorder before continuing with its right child.
Try playing with different tree structures in the above code and compare the printed debug/pedagogical traversal to your understanding.
这篇关于了解BST遍历的打印输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
