从中序遍历看递归：函数到底是怎样入栈和出栈的？

学习二叉树时，很多人第一次看到递归遍历代码，都会觉得它像“自己调用自己”，看起来很短，执行过程却不容易想明白。

例如下面这段中序遍历代码：

void inorder(Node* root)
{
    if (!root) return;

    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

代码只有几行，但里面包含了递归、函数调用栈、入栈、出栈、暂停与恢复执行等多个重要概念。

这篇文章就通过一棵简单的二叉树，把整个执行过程拆开来看。

一、什么是中序遍历？

二叉树常见遍历方式有三种：

• 前序遍历：根节点 → 左子树 → 右子树

• 中序遍历：左子树 → 根节点 → 右子树

• 后序遍历：左子树 → 右子树 → 根节点

本文中的代码属于中序遍历：

左子树 -> 根节点 -> 右子树

假设有这样一棵二叉树：

        1
       / \
      2   3
     / \
    4   5

如果从根节点 1 开始进行中序遍历，输出结果应该是：

4 2 5 1 3

为什么是这个顺序？关键就在递归调用的入栈与出栈过程。

二、先理解每一行代码的作用

完整代码如下：

void inorder(Node* root)
{
    if (!root) return;

    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

第一句：

if (!root) return;

表示当前节点为空时，直接结束本次函数调用。

二叉树的叶子节点左右孩子通常都是空指针，因此递归最终一定会走到这里，然后返回。

第二句：

inorder(root->left);

先递归处理左子树。

第三句：

cout << root->val << " ";

左子树全部处理完成后，输出当前节点。

第四句：

inorder(root->right);

最后递归处理右子树。

因此，中序遍历的核心顺序始终是：

先左，再根，后右

三、递归调用时，函数是怎样入栈的？

可以把“调用栈”理解成一摞书。

每调用一次函数，就相当于在最上面放一本书，这叫做“入栈”。

函数执行结束后，最上面的书被拿走，这叫做“出栈”。

递归函数每调用一次自己，都会产生一层新的函数调用记录。每一层都会保存当前节点、执行位置等信息。

从根节点 1 开始调用：

inorder(1);

程序首先执行：

inorder(root->left);

节点 1 的左孩子是 2，于是继续调用：

inorder(2);

节点 2 的左孩子是 4，继续调用：

inorder(4);

节点 4 的左孩子为空，继续调用：

inorder(NULL);

此时调用栈大致如下：

inorder(1)
inorder(2)
inorder(4)
inorder(NULL)

最上面是当前正在执行的函数。

四、遇到空节点后，为什么会返回？

进入：

inorder(NULL);

后，参数 root 为空，因此满足：

if (!root) return;

函数立刻结束。

这一次调用完成后，inorder(NULL) 出栈，程序回到上一层，也就是节点 4 对应的函数调用中。

注意：程序不会从头重新执行节点 4 的函数，而是从刚才暂停的位置继续。

节点 4 的代码原本是：

inorder(root->left);
cout << root->val << " ";
inorder(root->right);

左子树已经处理完成，因此接下来执行：

cout << root->val << " ";

输出：

4

随后执行：

inorder(root->right);

节点 4 的右孩子也是空节点，因此再次调用：

inorder(NULL);

立即返回。

至此，节点 4 的左右子树都处理完了，节点 4 对应的函数调用结束，出栈。

调用栈变成：

inorder(1)
inorder(2)

五、程序如何回到节点 2？

节点 4 处理完成后，程序回到节点 2 的函数调用中。

节点 2 的左子树已经完成，因此继续执行：

cout << root->val << " ";

输出：

2

接着处理节点 2 的右子树：

inorder(root->right);

节点 2 的右孩子是 5，于是调用：

inorder(5);

节点 5 左右孩子都为空，执行过程和节点 4 类似：

先访问左空节点
输出 5
再访问右空节点

因此继续输出：

5

节点 5 出栈，节点 2 也出栈。

调用栈只剩下：

inorder(1)

六、回到根节点 1

节点 1 的左子树已经全部处理完成，接下来执行：

cout << root->val << " ";

输出：

1

然后处理右子树：

inorder(root->right);

节点 1 的右孩子是 3，于是调用：

inorder(3);

节点 3 左右孩子为空，最终输出：

3

所有函数调用结束，调用栈清空。

最终输出结果：

4 2 5 1 3

七、完整调用过程

整个递归过程可以写成下面这样：

inorder(1)
    inorder(2)
        inorder(4)
            inorder(NULL)   返回
        输出 4
            inorder(NULL)   返回
    输出 2
        inorder(5)
            inorder(NULL)   返回
        输出 5
            inorder(NULL)   返回
输出 1
    inorder(3)
        inorder(NULL)       返回
    输出 3
        inorder(NULL)       返回

从执行顺序看，程序总是先不断向左深入。

当走到空节点时开始返回，再依次输出节点，然后处理右子树。

这正是中序遍历“左、根、右”的来源。

八、递归最重要的三个规律

理解递归时，可以记住下面三句话：

调用函数时，当前函数暂停，新函数入栈。
子函数执行结束后，子函数出栈。
父函数从暂停的位置继续执行。

例如：

inorder(root->left);
cout << root->val << " ";

调用左子树函数时，当前函数会暂停。

左子树全部处理完成后，程序自动回到这里，继续执行：

cout << root->val << " ";

因此，递归并不是“函数乱跳”，而是依靠调用栈，一层一层保存现场，再一层一层返回。

九、递归代码为什么看起来短，却能完成复杂任务？

因为每一层函数只负责一件事：

处理当前节点

对于当前节点，只需要完成三步：

处理左子树
输出当前节点
处理右子树

至于左子树和右子树内部有多少节点，不需要单独关心，递归会自动完成。

这也是递归最有价值的地方：把一个复杂问题拆成许多个结构相同的小问题。

二叉树、目录遍历、全排列、迷宫搜索、分治排序等问题，都经常使用这种思想。

十、总结

中序遍历的代码虽然只有几行，但背后依赖的是函数调用栈。

void inorder(Node* root)
{
    if (!root) return;

    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

执行时遵循下面的规律：

先不断进入左子树
遇到空节点后开始返回
返回时输出当前节点
再进入右子树

对于示例二叉树：

        1
       / \
      2   3
     / \
    4   5

中序遍历结果为：

4 2 5 1 3

真正理解递归，不是只记住“函数调用自己”，而是要理解：每次调用都会入栈，执行结束后再出栈，父函数会从暂停的位置继续执行。