了解 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 resultNode以下是二叉搜索树的类结构：class Node:    def __init__(self, data, left=None, right=None):        self.data = data        self.left=left        self.right=right这是遍历 BST 的输出：restartb4 app 9restartb4 app 4 #[3]restartb4 app 3 aft app 3 True # <--- I thought it would end here? [0]aft app 4 False #[2]inside rightrestartb4 app 6aft app 6 Trueaft app 9 Falseinside rightrestartb4 app 17aft 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 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——最好避免担心子递归调用。如果它们为“无”，则该单个分支将在子堆栈帧中处理该情况。

上面的代码返回一个生成器，它比创建列表更内存友好，并且语法更简单。

我还会继续在函数之外进行打印。传递回调是避免产生副作用的常见方法，但是使用上面的生成器方法可以通过循环完成相同的结果，让我们将打印保留在调用者中。

如果您确实需要出于调试目的进行打印，我建议使用空格缩进，这使得输出成为树并且更容易理解：

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))

这给出了树的侧视图：

    3

  4

    6

9

  17

通过这种缩进技巧，可以更轻松地可视化树，这是前/中/后顺序打印的清理版本，它应该给出遍历的清晰图片：

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:保证是真实的并且应该被删除。父调用会检查这一点，即使他们没有这样做，程序也会在上面使用 的行上崩溃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 node

visiting 4      # this is your `aft app 4 False #[2]`

您可以看到我们退出了 的调用框架node=3。此时，node=4已完成遍历其所有左子孙（只有一个），然后按顺序访问其自己的值，然后继续处理其右子孙。

尝试在上面的代码中使用不同的树结构，并将打印的调试/教学遍历与您的理解进行比较。