《大话数据结构》第6章精读:二叉树三种遍历的递归与非递归实现(完整C++代码 + 深度对比)
摘要《大话数据结构》第6章讲树时把二叉树的遍历作为重点。书中主要给出了递归写法但对非递归实现只是点到为止。结合《C Primer Plus》里对指针、动态内存和栈的讲解本文把前序、中序、后序的递归与非递归版本都完整实现了一遍并重点分析了它们在空间复杂度和实现难度上的本质差异。文末附有完整的测试代码和运行结果可直接复制运行。1. 二叉树节点定义采用最经典的二叉链表结构每个节点包含数据域和左右孩子指针#include iostream #include stack #include vector using namespace std; struct BiNode { int data; BiNode *lchild, *rchild; BiNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} };这里用 C 的构造函数初始化列表来初始化成员这也是《C Primer Plus》第10章强调的最佳实践在进入构造函数体之前就完成初始化既高效又避免了未定义行为。左右孩子指针初始化为nullptr明确表示当前没有子节点。2. 递归遍历书中标准写法递归是最自然的表达方式本质是利用系统栈保存“回去的路”。三种递归遍历的代码非常简洁// 前序根 → 左 → 右 void PreOrder(BiNode* T) { if (T nullptr) return; cout T-data ; PreOrder(T-lchild); PreOrder(T-rchild); } // 中序左 → 根 → 右 void InOrder(BiNode* T) { if (T nullptr) return; InOrder(T-lchild); cout T-data ; InOrder(T-rchild); } // 后序左 → 右 → 根 void PostOrder(BiNode* T) { if (T nullptr) return; PostOrder(T-lchild); PostOrder(T-rchild); cout T-data ; }时间复杂度O(n)每个节点恰好访问一次。空间复杂度O(h)h 为树高。最坏情况退化为链表时为 O(n)平衡时为 O(log n)。递归写法虽然优雅但在树非常高时存在栈溢出风险而且无法直接中途停止或做更复杂的控制。因此非递归实现仍然有学习价值。3. 非递归前序遍历前序非递归相对简单只需要一个栈来模拟系统栈的行为void PreOrderNonRecursive(BiNode* T) { if (T nullptr) return; stackBiNode* s; s.push(T); while (!s.empty()) { BiNode* p s.top(); s.pop(); cout p-data ; // 先访问根 // 注意先压右再压左这样出栈时才是左先右后 if (p-rchild) s.push(p-rchild); if (p-lchild) s.push(p-lchild); } }核心思路前序是“根 → 左 → 右”栈是后进先出。为了让左孩子先出栈必须先把右孩子压入栈底再把左孩子压在栈顶。这样每次弹出栈顶时自然先访问左子树再访问右子树。4. 非递归中序遍历最经典中序非递归是理解“用栈模拟递归”的最佳例子void InOrderNonRecursive(BiNode* T) { stackBiNode* s; BiNode* p T; while (p || !s.empty()) { if (p) { s.push(p); // 一路向左走到底 p p-lchild; } else { p s.top(); s.pop(); cout p-data ; // 访问根 p p-rchild; // 转向右子树 } } }这个过程完美对应了递归中“先处理左子树 → 访问根 → 再处理右子树”的执行顺序。指针 p 一直沿着左孩子走把沿途节点全部压栈当 p 为空时说明左子树已经走完此时弹出栈顶节点访问然后把 p 指向其右孩子继续同样的流程。5. 非递归后序遍历难度最高后序需要知道“左子树和右子树都已经访问完毕”才能访问根因此通常需要额外记录上一次访问的节点void PostOrderNonRecursive(BiNode* T) { if (T nullptr) return; stackBiNode* s; BiNode* p T; BiNode* lastVisited nullptr; // 记录上一次访问的节点 while (p || !s.empty()) { if (p) { s.push(p); p p-lchild; // 优先走左边 } else { BiNode* top s.top(); // 如果右孩子存在且还没访问过就转向右孩子 if (top-rchild top-rchild ! lastVisited) { p top-rchild; } else { // 左右都访问完了可以访问自己 cout top-data ; lastVisited top; s.pop(); } } } }关键点后序非递归是三种遍历里实现最容易出错的。核心难点在于正确判断“右子树是否已经处理完毕”。引入lastVisited指针记录上一次被访问的节点当top-rchild lastVisited时说明右子树已经访问过了此时可以安全地访问根节点。6. 深度对比与思考三种遍历方式的多维度对比遍历方式递归实现难度非递归实现难度空间复杂度最坏实际使用频率前序低低O(n)高复制、序列化中序低中O(n)高BST有序输出后序低高O(n)中销毁、表达式树结合《C Primer Plus》的深度思考递归与栈帧递归版本本质上是编译器帮我们维护了一个隐式的栈帧。每次函数调用都会在系统栈上压入返回地址、局部变量等信息。非递归只是把这个栈显式写出来。在《C Primer Plus》第9章讲内存模型时我们了解了栈区和堆区的区别递归深度过大时栈区溢出就是这个原因。后序与析构后序遍历的访问顺序正好对应了“先析构孩子再析构自己”的销毁逻辑。在《C Primer Plus》第10-12章讲类和动态内存时我们强调了一个重要原则如果类中有new出来的子对象析构时必须先释放子对象再释放自己。后序遍历正是这种“自底向上”的销毁顺序因此很多树的销毁函数都用后序。父指针的权衡如果树的节点带有父指针非递归后序遍历可以写得更简洁但会增加空间开销和维护成本。在《C Primer Plus》中反复强调软件工程中没有银弹任何设计都是在时间、空间和复杂度之间做权衡。7. 完整测试代码下面构建一棵示例二叉树分别用六种遍历方式输出结果验证递归与非递归版本的一致性int main() { // 手动构建一棵简单二叉树 // 1 // / \ // 2 3 // / \ // 4 5 BiNode* root new BiNode(1); root-lchild new BiNode(2); root-rchild new BiNode(3); root-lchild-lchild new BiNode(4); root-lchild-rchild new BiNode(5); cout 前序递归: ; PreOrder(root); cout endl; cout 前序非递归: ; PreOrderNonRecursive(root); cout endl; cout 中序递归: ; InOrder(root); cout endl; cout 中序非递归: ; InOrderNonRecursive(root); cout endl; cout 后序递归: ; PostOrder(root); cout endl; cout 后序非递归: ; PostOrderNonRecursive(root); cout endl; return 0; }预期输出结果前序递归: 1 2 4 5 3 前序非递归: 1 2 4 5 3 中序递归: 4 2 5 1 3 中序非递归: 4 2 5 1 3 后序递归: 4 5 2 3 1 后序非递归: 4 5 2 3 1六种遍历输出完全一致验证了递归与非递归版本的正确性。8. 总结二叉树的遍历是数据结构最基础也最重要的操作之一几乎所有的树相关算法都建立在遍历的基础上。本文从递归到非递归、从代码到原理、从实现到对比系统地梳理了三种遍历方式。建议读者亲手敲一遍代码在调试器中观察栈的变化过程才能真正理解其中的精妙之处。

相关新闻

SpringBoot+Vue3疫情管理系统开发实战

SpringBoot+Vue3疫情管理系统开发实战

1. 项目概述 疫情管理系统是当前公共卫生领域的重要信息化工具,基于Java SpringBootVue3MyBatis技术栈构建的前后端分离系统,能够实现疫情数据的实时采集、统计分析和可视化展示。这个技术组合在2023年开发者社区调研中占比达到37.8%,成为企业…

2026/8/9 8:24:52 阅读更多 →
SD WebUI内存释放终极指南:彻底解决显存泄露问题

SD WebUI内存释放终极指南:彻底解决显存泄露问题

SD WebUI内存释放终极指南:彻底解决显存泄露问题 【免费下载链接】sd-webui-memory-release An Extension for Automatic1111 Webui that releases the memory each generation 项目地址: https://gitcode.com/gh_mirrors/sd/sd-webui-memory-release SD Web…

2026/8/9 8:24:52 阅读更多 →
AI音乐检测实战:从原理到部署,基于Treblo开源项目的完整指南

AI音乐检测实战:从原理到部署,基于Treblo开源项目的完整指南

最近在AI音乐生成领域,一个名为Treblo的开源项目引起了不小的关注。它发布了一款AI音乐检测器,并声称说唱歌手Fenix Flexin的新歌“极可能”由其背后的AI模型生成。这不仅仅是一个娱乐新闻,更是一个强烈的技术信号:AI生成音乐的质…

2026/8/9 8:24:52 阅读更多 →

最新新闻

Flova多宫格视频生成实战:从AI图生视频到FFmpeg合成全流程

Flova多宫格视频生成实战:从AI图生视频到FFmpeg合成全流程

在AI内容创作领域,你是否曾幻想过能一键生成风格独特的视频内容,让创意不再受限于技术门槛?近期,一个名为“Flova”的工具及其“多宫格生视频Skill”功能在开发者社区和创意工作者中引发了广泛讨论。它能够将单张或多张图片&#…

2026/8/10 8:01:56 阅读更多 →
ROS2机器人开发从入门到实战:环境搭建、核心概念与仿真导航全流程

ROS2机器人开发从入门到实战:环境搭建、核心概念与仿真导航全流程

最近在整理机器人开发的学习路线时,发现很多同学对ROS2既充满兴趣又感到无从下手。网上的资料要么版本老旧,要么过于零散,不成体系。特别是对于零基础的开发者,从环境搭建到第一个可运行的机器人程序,中间往往卡在无数…

2026/8/10 8:01:56 阅读更多 →
Antigravity CLI 命令行工具:AI辅助编程与自动化任务实战指南

Antigravity CLI 命令行工具:AI辅助编程与自动化任务实战指南

这次我们来看一个名为 Antigravity CLI 的命令行工具。从名称和网络热词来看,它很可能与代码生成、AI辅助编程或某种开发环境增强工具有关。对于开发者而言,一个高效的 CLI 工具能极大提升日常编码、调试和系统管理的效率。本文将深入探讨 Antigravity C…

2026/8/10 8:01:56 阅读更多 →
Unity Hub安装包验证失败:从日志分析到网络代理配置的完整排错指南

Unity Hub安装包验证失败:从日志分析到网络代理配置的完整排错指南

1. 项目概述:当Unity Hub拒绝安装包时,我们该做什么? 如果你正在尝试安装或更新Unity编辑器,却卡在了“安装包验证失败”这个令人沮丧的提示上,那么你来对地方了。这几乎是每一位Unity开发者,尤其是在特定网…

2026/8/10 8:01:56 阅读更多 →
揭秘游戏高光集锦自动化生产:从算法推送到技术实现

揭秘游戏高光集锦自动化生产:从算法推送到技术实现

这次我们来看一个关于游戏精彩操作集锦的“大数据推送”现象。当你刷到类似“大数据把你推给我,就是为了让你看这波逆天4杀!”这样的标题时,背后其实是一套完整的内容生产、算法推荐和用户触达机制。这篇文章不聊具体的游戏操作,而…

2026/8/10 8:01:56 阅读更多 →
VMware虚拟机安装与配置全攻略:从环境检查到创建首个虚拟机

VMware虚拟机安装与配置全攻略:从环境检查到创建首个虚拟机

1. 先搞清楚你要用虚拟机做什么,再决定怎么装 VMware Workstation Pro 这类虚拟机软件,核心价值在于让你在一台物理电脑里,同时运行多个独立的操作系统。它不是玩具,而是开发、测试、运维甚至日常学习的刚需工具。很多人一上来就找…

2026/8/10 8:00:56 阅读更多 →

日新闻

GraphQL-CSS API全解析:useGqlCSS、GqlCSS组件与getStyles实用指南

GraphQL-CSS API全解析:useGqlCSS、GqlCSS组件与getStyles实用指南

GraphQL-CSS API全解析:useGqlCSS、GqlCSS组件与getStyles实用指南 【免费下载链接】graphql-css A blazing fast CSS-in-GQL™ library. 项目地址: https://gitcode.com/gh_mirrors/gr/graphql-css GraphQL-CSS是一个基于GraphQL的CSS-in-GQL™库&#xff0…

2026/8/10 0:00:02 阅读更多 →
告别语言障碍:KISS Translator 双语翻译插件终极指南

告别语言障碍:KISS Translator 双语翻译插件终极指南

告别语言障碍:KISS Translator 双语翻译插件终极指南 【免费下载链接】kiss-translator A simple, open source bilingual translation extension & Greasemonkey script (一个简约、开源的 双语对照翻译扩展 & 油猴脚本) 项目地址: https://gitcode.com/…

2026/8/10 0:00:02 阅读更多 →
BepInEx配置管理器:游戏插件配置的终极可视化解决方案

BepInEx配置管理器:游戏插件配置的终极可视化解决方案

BepInEx配置管理器:游戏插件配置的终极可视化解决方案 【免费下载链接】BepInEx.ConfigurationManager Plugin configuration manager for BepInEx 项目地址: https://gitcode.com/gh_mirrors/be/BepInEx.ConfigurationManager 你是否曾经因为游戏插件的复杂…

2026/8/10 0:00:02 阅读更多 →

周新闻

5分钟告别提取码焦虑:baidupankey如何智能破解百度网盘资源锁

5分钟告别提取码焦虑:baidupankey如何智能破解百度网盘资源锁

5分钟告别提取码焦虑:baidupankey如何智能破解百度网盘资源锁 【免费下载链接】baidupankey 在线查询网盘提取码(维护中 rm repo) 项目地址: https://gitcode.com/gh_mirrors/ba/baidupankey 你是否曾经在深夜寻找一份重要资料&#x…

2026/8/10 1:05:29 阅读更多 →
如何快速生成中国车牌图片:Python开源工具完整指南

如何快速生成中国车牌图片:Python开源工具完整指南

如何快速生成中国车牌图片:Python开源工具完整指南 【免费下载链接】chinese_license_plate_generator 中国车牌生成器 项目地址: https://gitcode.com/gh_mirrors/ch/chinese_license_plate_generator 中国车牌生成器是一个基于Python的开源项目&#xff0c…

2026/8/10 1:05:29 阅读更多 →
收藏!小白程序员轻松入门大模型,从Harness工程开始实践

收藏!小白程序员轻松入门大模型,从Harness工程开始实践

文章强调学习大模型不应只关注模型本身,而应重视模型外的系统搭建,即Harness。提出AgentModelHarness的实用公式,详细介绍Harness的四个层次:持久化层、执行层、控制层和观察与验证层。文章还探讨了上下文工程、工具设计、AGENTS.…

2026/8/10 1:05:29 阅读更多 →

月新闻

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS 还在为百度网盘macOS版的龟速下…

2026/8/9 17:05:02 阅读更多 →
终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 还在为网易云音乐下载的NCM格式文件无法在其他播放器播放而烦恼吗?ncmdump解密工具帮你轻松解决这个困…

2026/8/10 1:05:29 阅读更多 →
HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

AgentCard 智能体卡片:为英语学习 App 打造桌面级学习助手适用平台:HarmonyOS 7.0 (API 26 Beta)一、引言 HarmonyOS 7.0(API 26 Beta)新增了 AgentCard 智能体卡片能力,这是继 HMAF(鸿蒙智能体框架&#x…

2026/8/9 17:05:02 阅读更多 →