Python二叉搜索树递归打印元素的原理详解（新手向）

先贴出你提到的递归打印方法的典型实现（和你代码逻辑一致）：

def _print_tree_recursive(self, node):
    # 空节点直接返回，终止递归
    if node is None:
        return
    # 先递归遍历左子树
    self._print_tree_recursive(node.left)
    # 打印当前节点的值
    print(node.value)
    # 再递归遍历右子树
    self._print_tree_recursive(node.right)

结合你说的树结构（根节点值为1，左子节点值为-1，且-1的左右子节点都是空），咱们一步一步拆解递归的执行过程，核心是理解函数调用栈的工作机制——每调用一次递归函数，系统就会把当前函数的执行状态（比如执行到哪一行、参数是什么）压入栈中，等这个递归调用完成后，再从栈里取出之前的状态，继续往下执行。

具体执行步骤 #

1. 初始调用：从根节点开始，调用_print_tree_recursive(节点1)，此时调用栈里压入这个函数的执行状态，栈内容：[ _print_tree_recursive(1) ]
2. 进入节点1的函数：先执行self._print_tree_recursive(node.left)，也就是调用_print_tree_recursive(节点-1)，把这个新的函数状态压入栈，栈内容：[ _print_tree_recursive(1), _print_tree_recursive(-1) ]
3. 进入节点-1的函数：
   • 先执行self._print_tree_recursive(node.left)，也就是调用_print_tree_recursive(None)，压入栈后，这个函数直接触发if node is None的条件，立刻返回，栈弹出这个空节点的调用，回到_print_tree_recursive(-1)的执行状态
   • 接下来执行print(node.value)，打印出-1
   • 然后执行self._print_tree_recursive(node.right)，再次调用_print_tree_recursive(None)，同样直接返回，栈弹出这个调用，此时_print_tree_recursive(-1)的所有代码都执行完了，栈弹出这个函数状态，回到_print_tree_recursive(1)的执行状态
4. 回到根节点1的函数：
   • 刚才执行完左子树的递归调用，现在继续往下走，执行print(node.value)，打印出1
   • 接下来执行self._print_tree_recursive(node.right)，如果根节点1有右子节点，就会重复上面的递归流程，遍历右子树的所有节点

为什么能回溯？ #

简单说就是调用栈的“后进先出”特性：每次深入递归时，新的函数调用会“叠”在栈顶，只有当栈顶的函数执行完（比如遇到空节点返回，或者当前节点的左右子树都遍历完），才会弹出栈顶，回到上一层函数继续执行剩下的代码。

你困惑的“从-1节点回到根节点1”，本质就是_print_tree_recursive(-1)执行完毕后，从调用栈里被弹出，系统自动恢复到_print_tree_recursive(1)之前执行到左子树调用的位置，继续处理根节点的打印和右子树遍历。

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