python - 了解 BST 遍历的打印输出

问题描述

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

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

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：

在函数到达我指向的点（参见[0]）之后，node.rightis None，因此if代码中的下一条语句被跳过（参见[1]）。这是代码在结束之前再次调用自身的最后一次（据我所知？）。

如果这条if语句被跳过——最后一次io调用函数——递归如何继续？

此外，从输出中的下一行可以看出（请参阅[2]），它以node=4, node.left=3,继续node.right=6，它是node=3的父级，并在早期被传递到函数中（请参阅[3]）。

那么io函数是如何再次调用的，为什么是node=4输入呢？

标签： pythonrecursionbinary-search-treetree-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

我们需要的唯一分支是检查根是否为无——最好避免担心子递归调用。如果它们为无，则此单个分支将在子堆栈框架中处理该条件。

上面的代码返回了一个生成器，它比创建列表更便于内存使用，并且在语法上更简单。

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

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

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

这给出了树的侧视图：

使用这种缩进技巧可以更轻松地可视化树，这是您的前/中/后打印的清理版本，它应该可以清楚地显示遍历：

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已经完成了遍历它所有的左后代（只有一个），然后在继续它的右孩子之前访问了它自己的值。

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

python - 了解 BST 遍历的打印输出

问题描述

解决方案

推荐阅读