为了账号安全,请及时绑定邮箱和手机立即绑定

了解 BST 遍历的打印输出

了解 BST 遍历的打印输出

一只甜甜圈 2023-08-22 10:47:40
我试图理解下面的代码是如何工作的。代码按其应有的方式执行,但我不理解其中的部分内容。这是一种二叉搜索树的中序遍历方法: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输入呢?
查看完整描述

1 回答

?
交互式爱情

TA贡献1712条经验 获得超3个赞

这段代码是一种非常令人困惑的树遍历编写方式,但它看起来基本上是正确的。此外,输出打印在不寻常的位置,并带有误导性标签,因此在继续讨论您的问题之前,让我们干净地重写一下。

这是编写中序二叉树遍历的简单方法:

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已完成遍历其所有左子孙(只有一个),然后按顺序访问其自己的值,然后继续处理其右子孙。


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


查看完整回答
反对 回复 2023-08-22
  • 1 回答
  • 0 关注
  • 3859 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信