当前位置:

首页 > 编程开发 > C++二叉树后序遍历实现方法

C++二叉树后序遍历实现方法

答案是:C++中二叉树后序遍历有递归和迭代两种方法,顺序为左→右→根,递归简洁但可能栈溢出,迭代用栈模拟,适合深树。

本文目录

    答案是:C++中二叉树后序遍历有递归和迭代两种方法,顺序为左→右→根,递归简洁但可能栈溢出,迭代用栈模拟,适合深树。

    c++中如何实现后序遍历_c++二叉树后序遍历方法

    在C++中实现二叉树的后序遍历,主要有两种方法:递归和迭代。后序遍历的顺序是“左子树 → 右子树 → 根节点”,适合用于释放树节点或计算表达式树等场景。

    定义二叉树节点结构

    在开始前,先定义一个基本的二叉树节点结构:

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

    方法一:递归实现

    递归是最直观的方式,按照“左→右→根”的顺序访问节点。

    
    void postorderTraversalRecursive(TreeNode* root) {
        if (root == nullptr) return;
    
    postorderTraversalRecursive(root->left);  // 遍历左子树
    postorderTraversalRecursive(root->right); // 遍历右子树
    std::cout << root->val << " ";            // 访问根节点

    }

    优点是代码简洁易懂,缺点是在树很深时可能引发栈溢出。

    方法二:迭代实现(使用栈)

    迭代法用显式栈模拟递归过程。关键点是判断节点是否已经处理过右子树。

    一种常见做法是使用一个指针记录上一个访问的节点,避免重复进入右子树:

    void postorderTraversalIterative(TreeNode* root) {
        if (root == nullptr) return;
    
    std::stack stack;
    TreeNode* lastVisited = nullptr;
    TreeNode* current = root;
    
    while (current != nullptr || !stack.empty()) {
        if (current != nullptr) {
            stack.push(current);
            current = current->left;  // 一直向左走
        } else {
            TreeNode* peekNode = stack.top();
            // 如果右子树存在且未被访问过,进入右子树
            if (peekNode->right != nullptr && lastVisited != peekNode->right) {
                current = peekNode->right;
            } else {
                std::cout << peekNode->val << " ";
                lastVisited = stack.top();
                stack.pop();
            }
        }
    }

    }

    这种方法空间复杂度为O(h),h为树的高度,适合深度较大的树。

    测试示例

    你可以这样测试上述代码:

    int main() {
        TreeNode* root = new TreeNode(1);
        root->right = new TreeNode(2);
        root->right->left = new TreeNode(3);
    
    std::cout << "后序遍历结果: ";
    postorderTraversalRecursive(root); // 输出: 3 2 1
    std::cout << std::endl;
    
    return 0;

    }

    基本上就这些。递归写起来快,迭代更安全。根据实际需求选择合适的方法即可。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    WorkBuddy怎么用API接口?有开发文档吗
    WorkBuddy怎么用API接口?有开发文档吗

    WorkBuddy 目前没有面向普通用户的公开 REST API 接口文档,扩展与集成走四条官方路径:接入 MCP 服务扩展工具能力、用连接器打通外部应用(支持公共/个人授权)、编写技能(Skill)与专家包定制工作流、在开放平台发布 Buddy 应用。另支持接入 OpenAI 兼容的自定义模型。本文含 4 张真实界面截图并如实说明现状。

    Google Workspace MCP OAuth 2.0迁移节点已过,旧客户端、普通REST与服务账户分别适用什么规则
    Google Workspace MCP OAuth 2.0迁移节点已过,旧客户端、普通REST与服务账户分别适用什么规则

    解释Google Workspace MCP 11月11日与12日的agentic OAuth客户端迁移节点,区分普通REST应用、混合客户端、预览资格、用户权限和服务账户、Apps Script边界。

    OpenAI Agents SDK v0.24.0-alpha.8升级前为何要备份状态?
    OpenAI Agents SDK v0.24.0-alpha.8升级前为何要备份状态?

    OpenAI Agents SDK v0.24.0-alpha.8预览版新增执行前审批、自有模型客户端、Realtime与预算检查点恢复,说明alpha.7回退、Linux运行及工具认证边界。

    Claude Trading Skills六项诊断修复覆盖哪些密钥泄漏路径?
    Claude Trading Skills六项诊断修复覆盖哪些密钥泄漏路径?

    Claude Trading Skills六项技能已修复API密钥异常日志泄漏路径;not_verified保留完整安全审核缺口,离线回归通过不等于实盘验收或全面认证。

    Microsoft C++ Language Server内置MSBuild提取器后,自动化范围和使用资格怎样理解
    Microsoft C++ Language Server内置MSBuild提取器后,自动化范围和使用资格怎样理解

    解释Microsoft C++ Language Server预览版的MSBuild编译数据库自动提取,区分CMake、自定义构建、有效Copilot订阅和CLI能力,避免把测试预发布版本当最低稳定版。

    LibreOffice宏怎么用?Python脚本能调用吗
    LibreOffice宏怎么用?Python脚本能调用吗

    LibreOffice可通过“工具→宏”创建和运行Basic宏,也支持由Python脚本提供程序运行Python宏。两种方式都可以使用UNO接口操作文档;Excel VBA只有有限兼容支持,不能把所有Excel宏直接复制过来当作LibreOffice原生宏执行。

    GitHub企业Copilot席位API开放应用调用后,读取和席位变更有什么区别
    GitHub企业Copilot席位API开放应用调用后,读取和席位变更有什么区别

    说明Enterprise GitHub Apps的Copilot席位管理权限,提供第一页只读GET示例,区分total_seats、授权明细、遥测活动和待取消计费条件。

    GitHub网页仪表盘默认视图、单行标题和六项列表分别改变什么
    GitHub网页仪表盘默认视图、单行标题和六项列表分别改变什么

    解释GitHub网页仪表盘Feed或Home默认视图、六项列表、自定义选择保留和Agent sessions隐藏条件,区分布局、数据与权限。

    LangChain Python 1.4.10、JS core 1.3.7与langchain 1.6.4为什么要区分拒答和失败
    LangChain Python 1.4.10、JS core 1.3.7与langchain 1.6.4为什么要区分拒答和失败

    核对LangChain三种包版本,解释refusal内容块、ModelRefusalError与中间件传递,提供自定义错误分支示例并区分Python消息流和追踪修复。

    Anthropic Python/Ruby 2.8.0、TS 1.8.0、Go 2.9.0、Java 3.8.0参数校验应如何理解
    Anthropic Python/Ruby 2.8.0、TS 1.8.0、Go 2.9.0、Java 3.8.0参数校验应如何理解

    区分Anthropic各语言SDK及TypeScript云适配包版本,解释Claude Tag字段、Bedrock/Vertex分号差异、非法路径参数和只读Python版本核对。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。