了解 BST 遍历的打印输出

Question

我试图理解下面的代码是如何工作的。代码按其应有的方式执行，但我不理解其中的部分内容。

这是一种二叉搜索树的中序遍历方法：

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 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输入呢？

Answer 1

这段代码是一种非常令人困惑的树遍历编写方式，但它看起来基本上是正确的。此外，输出打印在不寻常的位置，并带有误导性标签，因此在继续讨论您的问题之前，让我们干净地重写一下。这是编写中序二叉树遍历的简单方法：from collections import namedtupleclass 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——最好避免担心子递归调用。如果它们为“无”，则该单个分支将在子堆栈帧中处理该情况。上面的代码返回一个生成器，它比创建列表更内存友好，并且语法更简单。我还会继续在函数之外进行打印。传递回调是避免产生副作用的常见方法，但是使用上面的生成器方法可以通过循环完成相同的结果，让我们将打印保留在调用者中。如果您确实需要出于调试目的进行打印，我建议使用空格缩进，这使得输出成为树并且更容易理解：from collections import namedtupleclass 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))这给出了树的侧视图：    3  4    69  17通过这种缩进技巧，可以更轻松地可视化树，这是前/中/后顺序打印的清理版本，它应该给出遍历的清晰图片：from collections import namedtupleclass 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 4visiting 9    entering 17    visiting 17    exiting 17exiting 9preorder  [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:保证是真实的并且应该被删除。父调用会检查这一点，即使他们没有这样做，程序也会在上面使用 的行上崩溃node.data。inside right令人困惑——这是一个有序打印，但仅适用于具有右子节点的节点。我不确定这会增加什么价值，所以我会忽略它。请注意，您没有exiting（弹出调用堆栈帧/后序）打印语句。结合这个背景，我们来回答一下你的问题：这是代码在结束之前最后一次调用自身（据我所知？）。是的，这个节点即将退出。需要明确的是，该函数会调用自身，因为它是递归的，但树中的每个节点只有一次调用。if如果跳过该语句（上次io调用该函数时），递归将如何继续？调用堆栈弹出，并从父级中停止的地方继续执行。这不是最后一次io被调用，因为父级可以（及其父级或其父级的子级）可以（并且确实）产生其他调用。那么io函数又是如何被调用的，为什么是node=4输入呢？它没有被再次调用—— 的调用框架node=4被暂停，等待其子级解决，当控制权返回到它时，它从中断处继续。让我们将我的输出与您的输出联系起来：    visiting 3  # this is your `aft app 3 True [0]`    exiting 3   # you don't have this print for leaving the nodevisiting 4      # this is your `aft app 4 False #[2]`您可以看到我们退出了 的调用框架node=3。此时，node=4已完成遍历其所有左子孙（只有一个），然后按顺序访问其自己的值，然后继续处理其右子孙。尝试在上面的代码中使用不同的树结构，并将打印的调试/教学遍历与您的理解进行比较。