Python二叉搜索树中序遍历traverse_in_order函数执行逻辑疑问

相关代码与运行结果 #

def traverse(self):
    if self.root !=None:
        print('*****Traversing*****')
        print('self.root is', self.root.data)
        print('self.root.Left is', self.root.leftchild.data)
        print('self.root.Right  is', self.root.rightchild.data)
        self.traverse_in_order(self.root)
        
def traverse_in_order(self,node):
    
    if node.leftchild!=None:  #there is leftchild
        print('node.leftchild is',node.leftchild.data )
        self.traverse_in_order(node.leftchild)       #go till end of leftnode
    print('')
    print('print node ', node.data)
    print('')
    if node.rightchild!=None:
        print('Node.RIght',node.rightchild.data)
        self.traverse_in_order(node.rightchild)
bst=BST()
bst.insert(32)
bst.insert(10)
bst.insert(1)
bst.insert(19)
bst.insert(46)

bst.traverse()

运行输出：

*****Traversing*****
   self.root is 32
   self.root.Left is 10
   self.root.Right  is 46
   node.leftchild is 10
   node.leftchild is 1
   -------------print node  1
   -------------print node  10
   Node.RIght 19
   print node  19
   print node  32
   Node.RIght 46
   print node  46

逻辑说明 #

你实现的traverse_in_order是标准中序遍历，执行规则固定为「遍历左子树 → 处理当前节点 → 遍历右子树」，你疑惑的执行顺序本质是递归调用的返回机制：每一层递归函数执行完成后，都会回到上一层调用该函数的位置，继续执行上一层剩余的代码。

你插入的节点最终形成的BST结构为：

• 根节点：32
  • 左子节点：10
    • 左子节点：1（叶子节点，无左右孩子）
    • 右子节点：19（叶子节点，无左右孩子）
  • 右子节点：46（叶子节点，无左右孩子）

完整的traverse_in_order调用流程如下：

1. 初始调用traverse_in_order(32)，检测到左子节点10存在，先执行traverse_in_order(10)
2. 进入traverse_in_order(10)，检测到左子节点1存在，先执行traverse_in_order(1)
3. 进入traverse_in_order(1)，检测到无左子节点，跳过左子树递归；执行当前节点打印逻辑，输出1；检测到无右子节点，跳过右子树递归，该函数执行结束，回到上一层调用位置（也就是traverse_in_order(10)里调用左子树递归的下一行代码）
4. 回到traverse_in_order(10)后，左子树递归已经全部执行完成，接下来执行当前节点打印逻辑，输出10；检测到右子节点19存在，执行traverse_in_order(19)
5. 进入traverse_in_order(19)，无左子节点，直接打印19；无右子节点，函数执行结束回到traverse_in_order(10)，traverse_in_order(10)所有逻辑执行完成，回到上一层traverse_in_order(32)
6. 回到traverse_in_order(32)后，左子树递归全部执行完成，执行当前节点打印逻辑，输出32；检测到右子节点46存在，执行traverse_in_order(46)
7. 进入traverse_in_order(46)，无左子节点，直接打印46；无右子节点，函数执行结束，整个遍历流程完成。

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