c++如何实现二叉树的前中后序遍历_c++ 递归与非递归算法实现【教程】

递归更常用因前中后序天然递归定义，代码简洁不易错；非递归需手动模拟栈，逻辑复杂易混淆，仅在栈溢出风险时选用。

为什么递归写法比非递归更常用

因为前中后序遍历的天然结构就是递归定义的：访问根节点、递归遍历左子树、递归遍历右子树——只是三者顺序不同。递归写法直接映射逻辑，代码简洁且不易出错。root->val、root->left、root->right 三个成员访问就构成全部骨架。

非递归本质是手动模拟系统栈行为，需额外维护 std::stack 或 std::vector，且各序遍历的入栈/出栈时机和访问节奏完全不同，容易混淆。比如中序非递归必须“一路向左压栈到底再弹出”，而后序则需记录“右子树是否已访问过”——这通常要引入辅助标记或双栈。

• 递归版本只需关注访问顺序，无需管理状态
• 非递归中序相对清晰，但前序和后序的 while 循环条件和分支判断极易写反
• 递归在树深度过大时可能栈溢出（如百万级节点链状树），此时才需考虑非递归或迭代器式遍历

前中后序递归实现的关键区别在哪

区别只在三行语句的排列顺序，其余完全一致。假设节点结构为：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

以 std::vector 收集结果为例：

立即学习“C++免费学习笔记（深入）”；

• 前序：先访问 root->val，再递归左、右 → res.push_back(root->val); dfs(root->left); dfs(root->right);
• 中序：先递归左，再访问 root->val，最后递归右 → dfs(root->left); res.push_back(root->val); dfs(root->right);
• 后序：先递归左、右，最后访问 root->val → dfs(root->left); dfs(root->right); res.push_back(root->val);

所有版本共用同一入口函数，仅内部顺序不同。传参用引用 std::vector& res 避免拷贝，且不需返回值。

非递归中序遍历怎么写才不容易错

核心思路是“左链压栈 + 弹出即访问 + 转向右子树”。它是最接近直觉的非递归遍历，也是其他两种的基础变体。

Picit AI

免费AI图片编辑器、滤镜与设计工具

下载

关键步骤如下：

• 用 std::stack 存待处理节点
• 从 root 开始，循环执行：while (cur != nullptr) { stack.push(cur); cur = cur->left; } —— 把整条最左链压入
• 弹出栈顶（即当前最左未访问节点），res.push_back(node->val)
• 将 cur 设为该节点的 right，继续下一轮左链压栈

完整示例：

std::vector inorderTraversal(TreeNode* root) {
    std::vector res;
    std::stack stk;
    TreeNode* cur = root;
    while (cur != nullptr || !stk.empty()) {
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

注意：循环条件是 cur != nullptr || !stk.empty()，缺一不可；内层 while 压栈后必须把 cur 置为 nullptr，否则会无限循环。

后序非递归为什么最麻烦

因为后序要求“左右子树都访问完才能访问根”，而栈是 LIFO，天然适合先处理根再处理子树。强行用单栈需区分“刚入栈”和“左右已处理完”两种状态。

常见解法有两种，但都有代价：

• 双栈法：第一栈按“根→右→左”压入，第二栈接收弹出节点 → 最终第二栈弹出顺序即为后序。空间开销翻倍，且逻辑绕
• 标记法：栈中存 std::pair，bool 表示右子树是否已访问。每次弹出若标记为 false，重新压回并设标记为 true，再压入右子节点；若为 true 才真正访问。代码冗长，分支多

实际工程中，除非明确禁止递归或内存受限，否则直接用递归后序更可靠。它的边界处理干净：if (!root) return; 一行即可拦截空指针，而非递归版本每处 ->left 和 ->right 都得加空检查。