Python二叉树traverseinorder中序遍历打印值的运行原理疑问

问题相关代码 #

class node:
    def __init__(self,val):
        self.data = val 
        self.left = None 
        self.right = None 
        
class Tree:
    def create(self,data):
        return node(data) 
        
    def insert(self,node,data):
        if node is None:
            return self.create(data)
        if data < node.data:
            node.left = self.insert(node.left, data) 
        else:
            node.right = self.insert(node.right, data)
        return node
        
    def search(self,node,data):
        if data == node.data or node is None:
            return node
        if node.data < data:
            return self.search(node.right, data)
        else:
            return self.search(node.left, data)
        
    def traverseinorder(self,root):
        if root is not None:
            print(root.data)
            self.traverseinorder(root.left)
            self.traverseinorder(root.right)
        
def main():
    root = None
    tree = Tree()
    root = tree.insert(root, 10)
    print(root)
    tree.insert(root, 20)
    tree.insert(root, 30)
    tree.insert(root, 40)
    tree.insert(root, 70)
    tree.insert(root, 60)
    tree.insert(root, 80)

    print("Traverse Inorder")
    tree.traverseinorder(root)

问题解答 #

这个逻辑本质是递归调用的正常执行流程，理解起来非常简单：

• 你写的traverseinorder方法本身就内置了print操作，它的功能不是「返回要打印的内容给外部处理」，而是「只要传入的节点不为空，就先打印当前节点值，再递归处理左子树、再递归处理右子树」。
• 你在方法内部写self.traverseinorder(root.left)的时候，本质就是触发一次该方法的完整执行流程，只要root.left不为空，这次调用内部的print就会自动执行，完全不需要你在调用位置额外加print。

可以用一段更简单的代码类比理解：

def count_down(n):
    if n <= 0:
        return
    print(n)
    count_down(n-1)

count_down(3)

运行这段代码会依次打印3、2、1，你也没有在count_down(n-1)外面加print，但每次调用count_down都会触发内部的打印逻辑，和你树遍历的逻辑完全一致。

对应到你这段代码的执行流程，第一层你传入的根节点是10：

1. 根节点10不为空，打印10，接着处理10的左节点（为空直接跳过），再处理10的右节点20
2. 节点20不为空，打印20，接着处理20的左节点（为空跳过），再处理20的右节点30
3. 以此类推，直到所有节点都被处理完成，所有节点的打印操作自然就全部触发了。

内容的提问来源于stack exchange，提问作者shaila