当前位置: 首页 > news >正文

二叉树的遍历(前序、中序、后序)| C语言

目录

0.写在前面

1.前序遍历

步骤详解

代码实现

2.中序遍历

步骤详解

代码实现 

3.后序遍历

步骤详解

代码实现


0.写在前面

认识二叉树结构最简单的方式就是遍历二叉树。所谓遍历二叉树就是按照某种特定的规则,对二叉树的每一个节点进行访问,且每个节点只访问一次。

二叉树遍历的规则一般有四种:前序遍历、中序遍历、后序遍历和层序遍历。其中,前三种较为简单且实现方式大同小异。

        1.前序遍历:先访问根节点,再遍历左右子树;

        2.中序遍历:先遍历左子树,再访问根节点,再遍历右子树;

        3.后序遍历:先遍历左子树,再遍历右子树,再访问根节点。

简单记忆:前(根,左,右)、中(左,根,右)、后(左,右,根)。

在遍历二叉树之前,首先得拥有一棵二叉树。因为目前还没有学习如何构建二叉树,所以此处我们用最原始的办法——申请N个节点,将它们手动拼接为二叉树。

typedef int BTDataType;//二叉树节点的结构
typedef struct BTNode
{BTDataType data;struct BTNode* left;struct BTNode* right;
}BTNode;//定义一个申请新节点的函数
BTNode* BuyBTNode(BTDataType data)
{BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;}int main()
{//手动申请节点加连接BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return 0;
}

1.前序遍历

前序遍历:先访问根节点,再访问左子树,再访问右子树;

void PrevOrder (BTNode* root)

为了更好的理解前序遍历的规则,接下来展示一下详细步骤。

步骤详解

1.先访问根节点 (data = 1),再访问左子树; 

2.再访问左子树的根节点(data =  2),再访问左子树的左子树;

3.依旧先访问根节点(data = 3),此时 n3 节点的左右子树都为 NULL ,则不再往下递归,回到上一层;接着访问上一层的右子树;

4.因为 n2 节点的右子树为 NULL,所以继续返回上一层;访问上一层的右子树;

5.访问右子树的根节点(data = 4),再访问右子树的左子树;先左子树的根节点(data = 5),n5 节点的左右子树都为 NULL,返回上一层访问右子树(data = 6),同样 n6 节点的左右子树都为 NULL,返回上一层。

至此每个节点都访问完毕,总体的访问顺序是这样的:

按照访问顺序打印的结果应该是(空节点用 NULL 表示):

1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 

代码实现

按照前序遍历的逻辑,前序遍历的实现肯定是离不开递归。

void PrevOrder(BTNode* root)
{if (root == NULL){ printf("NULL ");//空节点用 NULL 表示return; }printf("%d ", root->data);//前序在前PrevOrder(root->left);PrevOrder(root->right);
}

(凑合着看,有点丑陋hhhhh) 

运行程序,看结果是否与之前推理的结果一致:

int main()
{//手动申请节点加连接BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;PrevOrder(n1);return 0;
}
//推理结果
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 

2.中序遍历

前中后序三种遍历大同小异,实现代码也几乎相同。

void InOrder(BTNode* root)

步骤详解

代码实现 

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PrevOrder(root->left);printf("%d ", root->data);//中序在中PrevOrder(root->right);
}
//推理结果
NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

3.后序遍历

步骤详解

参考1、2。

代码实现

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);//后序在后
}

相关文章:

二叉树的遍历(前序、中序、后序)| C语言

目录 0.写在前面 1.前序遍历 步骤详解 代码实现 2.中序遍历 步骤详解 代码实现 3.后序遍历 步骤详解 代码实现 0.写在前面 认识二叉树结构最简单的方式就是遍历二叉树。所谓遍历二叉树就是按照某种特定的规则,对二叉树的每一个节点进行访问,…...

【建议收藏】深入浅出Yolo目标检测算法(含Python实现源码)

深入浅出Yolo目标检测算法(含Python实现源码) 文章目录深入浅出Yolo目标检测算法(含Python实现源码)1. One-stage & Two-stage2. Yolo详解2.1 Yolo命名2.2 端到端输入输出2.3 Yolo中的标定框2.4 Yolo网络结构2.5 Yolo的算法流…...

Vue常见的事件修饰符

前言 vue一共给我们准备了6个事件修饰符,前三个比较常用,后三个少见,这里着重讲下前三个 1.prevent:阻止默认事件(常用) 2. stop:阻止事件冒泡(常用) 3. once:事件只触发一次(常用) 4.captrue:使用事件的捕捉模式(不常用) 5.self:只有event…...

【卷积神经网络】激活函数 | Tanh / Sigmoid / ReLU / Leaky ReLU / ELU / SiLU / GeLU

文章目录一、Tanh二、Sigmoid三、ReLU四、Leaky ReLU五、ELU六、SiLU七、Mish本文主要介绍卷积神经网络中常用的激活函数及其各自的优缺点 最简单的激活函数被称为线性激活,其中没有应用任何转换。 一个仅由线性激活函数组成的网络很容易训练,但不能学习…...

刷题记录:牛客NC24048[USACO 2017 Jan P]Promotion Counting 求子树的逆序对个数

传送门:牛客 题目描述 奶牛们又一次试图创建一家创业公司,还是没有从过去的经验中吸取教训–牛是可怕的管理者! 为了方便,把奶牛从 1∼n1\sim n1∼n 编号,把公司组织成一棵树,1 号奶牛作为总裁(这棵树的根…...

MpAndroidChart3最强实践攻略

本篇主要总结下Android非常火爆的一个三方库MpAndroidChart的使用。可能在大多数情况下,我们很少会在Android端去开发图表。但如果说去做一些金融财经类、工厂类、大数据类等的app,那么绝对会用到MpAndroidChart。 一、前言 2018年,那年的我…...

Spring笔记(9):事务管理ACID

一、事务管理 一个数据库事务是一个被视为单一的工作单元操作序列。 事务管理有四个原则,被成为ACID: Atomicity 原子性—— 事务作为独立单元进行操作,整个序列是一体的,操作全都成功或失败。Consistency 一致性—— 引用完整…...

io流 知识点+代码实例

需求 : 如何实现读写文件内部的内容?流 : 数据以先入先出的方式进行流动相当于管道,作用用来传输数据数据源-->流-->目的地流的分类 :流向分 : 以程序为中心输入流输出流操作单元 :字节流 : 万能流字符流 : 只能操作纯文本文件功能分 :节点流 : 真实实现读写的功能流(包…...

【MySQL】P8 多表查询(2) - 连接查询 联合查询

连接查询以及联合查询多表查询概述连接查询内连接隐式内连接显式内连接外连接左外连接右外连接自连接联合查询多表查询概述 建表语句见上一篇博文:https://blog.csdn.net/weixin_43098506/article/details/129402302 e.g.e.g.e.g. select * from emp, dept where e…...

QML动画(Animator)

在Qt5.2之后,引入Animator动画元素。这种方式可以直接所用于Qt Quick的场景图形系统,这使得基于Animator元素的动画及时在ui界面线程阻塞的情况下仍然能通过图形系统的渲染线程来工作,比传统的基于对象和属性的Animation元素能带来更好的用户…...

Git 分支操作【解决分支冲突问题】

1. 什么是分支 在版本控制过程中,同时推进多个任务,为每个任务,我们就可以创建每个任务的单独分支。使用分支意味着程序员可以把自己的工作从开发主线上分离开来,开发自己分支的时候,不会影响主线分支的运行。对于初学…...

盘点全球10大女性技术先驱

盘点全球10大女性技术先驱 人们普遍认为技术是男性主导的领域,但事实,技术或编程与性别无关,几乎任何人都可以成为技术大神。已经有很多案例证明女性同样可以在技术领域施展才能。在女神节来临之际,我为大家盘点一下为编程做出卓越…...

C++之dynamic_cast

C之dynamic_cast前言dynamic_castNote:示例:前言 dynamic_cast运算符牵扯到的面向对象的多态性跟程序运行时的状态,所以不能完全的使用传统的转换方式来替代。因此是最常用,最不可缺少的一个运算符,与static_cast一样,dynamic_cas…...

JavaScript 箭头函数、函数参数

箭头函数: 箭头函数是一种更加简洁的函数书写方式箭头函数本身没有作用域(无this)箭头函数的this指向上一层,上下文决定其this基本语法:参数 > 函数体 a. 基本用法 let fn v > v; //等价于 let fn function(…...

JavaScript_Object.keys() Object.values()

目录 一、Object.keys() 二、Object.values() 一、Object.keys() Object.keys( ) 的 用法 : 作用 &#xff1a;遍历对象 { } 返回结果&#xff1a;返回 对象中 每一项 的 key 值 返回值 : 是一个 *** [ 数 组 ] *** 例子 ( 1 ) : <script>// 1. 定义一个对象var obj …...

扬帆优配|高送转+高分红+高增长潜力股揭秘

高送转且高分红的高增加股票&#xff0c;有望跑赢大盘。 此前七连阴的泽宇智能&#xff0c;今日早盘大幅高开。到上午收盘&#xff0c;该股飙涨9.3%&#xff0c;位居涨幅榜前列。音讯面上&#xff0c;3月7日晚间&#xff0c;泽宇智能发表2022年年报&#xff0c;年报显现&#x…...

基于transformer的多帧自监督深度估计 Multi-Frame Self-Supervised Depth with Transformers

Multi-Frame Self-Supervised Depth with Transformers基于transformer的多帧自监督深度估计0 Abstract 多帧深度估计除了学习基于外观的特征外&#xff0c;也通过特征匹配利用图像之间的几何关系来改善单帧估计。我们采用深度离散的核极抽样来选择匹配像素&#xff0c;并通过一…...

设计模式: 单例模式

目录单例模式应用场景实现步骤涉及知识点设计与实现单例模式 通过单例模式的方法创建的类在当前进程中只有一个实例&#xff1b; 应用场景 配置管理 日志记录 线程池 连接池 内存池 对象池 消息队列 实现步骤 将类的构造方法定义为私有方法 定义一个私有的静态实例 提供一…...

idea编辑XML文件出现:Tag name expected报错

说明 Tag name expected解释其实就是&#xff1a;需要标记名称&#xff0c;也就是符号不能直接使用的意思 XML (eXtensible Markup Language) 是一种标记语言&#xff0c;用于存储和传输数据。在 XML 中&#xff0c;有些字符被视为特殊字符&#xff0c;这些字符在 XML 中具有…...

第十三届蓝桥杯省赛C++ A组 爬树的甲壳虫(简单概率DP)

题目如下&#xff1a; 思路 or 题解&#xff1a; 概率DP 状态定义&#xff1a; dp[i]dp[i]dp[i] 表示从树根到第 iii 层的期望 状态转移&#xff1a; dp[i](dp[i−1]1)∗11−pdp[i] (dp[i - 1] 1) * \frac{1}{1-p}dp[i](dp[i−1]1)∗1−p1​ 这个式子的意思是&#xff1a;…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...