【数据结构】遍历二叉树
- 遍历二叉树的算法描述(递归定义)
先序遍历
若二叉树为空,则空操作;
否则
(1)访问根节点
(2)先序遍历左子树
(3)先序遍历右子树
中序遍历
若二叉树为空,则空操作;
否则
(1)中序遍历左子树
(2)访问根节点
(3)中序遍历右子树
后序遍历
若二叉树为空,则空操作;
否则
(1)后序遍历左子树
(2)后序遍历右子树
(3)访问根节点
- 根据遍历序列确定二叉树
- 若二叉树中各结点的值均不同,则二叉树的先序、中序、后序序列都是唯一的
- 由二叉树的先序序列和中序序列,或由后序序列和中序序列可以唯一确定一棵二叉树
由先序序列和中序序列确定二叉树:
先序序列先访问的是根节点,由此确定二叉树的根节点和左右子树,然后重复此过程可递归的找到所有的左右子树和根节点
由后序序列和中序序列确定二叉树:
后续遍历最后访问的是根节点,其余同理
- 遍历算法实现
递归实现
先序遍历
Status PreOrderTraverse(BiTree T){if(t==NULL)return OK;else{printf("%d", T->data);//访问根节点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}
}
中序遍历
Status InOrderTraverse(BiTree T){if(t==NULL)return OK;else{InOrderTraverse(T->lchild);//递归遍历左子树printf("%d", T->data);//访问根节点InOrderTraverse(T->rchild);//递归遍历右子树}
}
后序遍历
Status PostOrderTraverse(BiTree T){if(t==NULL)return OK;else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTraverse(T->rchild);//递归遍历右子树printf("%d", T->data);//访问根节点}
}
非递归实现
Status InOderTravese(BiTree T){BiTree p,q;InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,q);printf("%c", q->data);p=q->rchild;}}return OK;
}
- 二叉树的层次遍历
对于一棵二叉树,从根节点开始,按从上到下,从左到右的顺序访问每个结点
设计思路:使用一个队列
1.将根节点进队
2.队不为空时,出队结点p,访问它
1.若它右左孩子,将左孩子进队
2.若它有右孩子,将右孩子进队
使用循环队列
typedef struct{BTNode data[MaxSize];int front,rear; //队头和队尾指针
}SqQueue;//循环队列
void LevelOrder(BTNode *b){BTNode *p;SqQueue *qu;InitQueue(qu); //初始化队列enQueue(qu, b); //根节点进队while(!QueueEmpty(qu)){deQueue(qu, p); //出队结点pprintf("%c", p->data); //访问结点pif(p->lchild!=NULL) //左孩子不为空则进队enQueue(qu, p->lchild);if(p->rchild!=NULL) //右孩子不为空则进队enQueue(qu, p->rchild);}
}
- 二叉树的建立
按先序遍历序列建立二叉树的二叉链表
// 构造二叉树(前序遍历,'#'表示空节点)
Status CreateBiTree(BiTree &T){cin>>ch;if(ch=="#")T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch; //生成根节点CreateBiTree(T->lchild); //构造左子树CreateBiTree(T->rchild); //构造右子树}return OK;
}
- 复制二叉树
算法描述
如果是空树,递归结束;
否则,申请新结点空间,复制根节点
递归复制左子树
递归复制右子树
int Copy(BiTree T, BiTree &NewT){if(T==NULL){ //如果是空树,返回0NewT = NULL;return 0;}else{NewT=new BiTree;NewT->data=T->data;Copy(T->lchild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
}
- 计算二叉树的深度
算法思路
如果是空树,则深度为0
否则,递归计算左子树的深度m,递归计算右子树的深度n,二叉树深度为max(m,n)+1
int Depth(BiTree T){if(T==NULL)return 0;else{m=Depth(T->lchild);n=Depth(T->rchild);return m>n?m+1:n+1;}
}
- 计算二叉树结点总数
算法描述
如果是空树,则结点个数为0
否则,结点个数为左子树的结点个数+右子树的结点个数再+1
int NodeCount(BiTree T){if(T==NULL)return 0;elsereturn NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
- 计算叶子结点数
算法描述
如果是空树,则叶子结点个数为0
否则,叶子结点个数为左子树的叶子结点个数+右子树的叶子结点个数
int LeafCount(BiTree T){if(T==NULL)return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;elsereturn LeafCount(T->lchild)+LeafCount(T->rchild);
}
相关文章:
【数据结构】遍历二叉树
遍历二叉树的算法描述(递归定义) 先序遍历 若二叉树为空,则空操作; 否则 (1)访问根节点 (2)先序遍历左子树 (3)先序遍历右子树 中序遍历 若二叉树为空…...
嵌入式蓝桥杯学习7 产生PWM
Cubemx配置 打开cubemx,前面的配置看上文,这里主要配置定时器产生PWM波。 以PA1的TIM2-CH2通道为例进行演示。 1.在Timers中打开TIM2,将Channel2配置为PWM Generation CH2。 2.将Clock Source 选择为Internal Clock。 3.配置Paramater Settings中的参…...
档案学实物
档案工作 档案工作的性质 服务性 文化性 管理性 政治性 科学性 档案工作的地位 档案工作的效益 社会性,隐蔽性,滞后性 档案工作的发展规律 档案收集 档案收集工作的内容意义 档案收集工作的具体要求 档案室的档案收集工作 档案馆的档案收集工作 档案…...
数据清洗代码:缺失值,异常值,离群值Matlab处理
目录 基本介绍程序设计参考资料基本介绍 一、过程概述 本过程适用于处理SCADA系统采集到的数据,以及具有类似需求的数据集。处理步骤包括缺失值处理、异常值处理和离群值处理,旨在提升数据质量,增强数据的相关性,同时保持数据的原始特征和随机性。 二、缺失值处理 对于SC…...
Windows设备go环境安装配置
一、下载go安装包 官网链接:All releases - The Go Programming Language (google.cn) 安装过程比较简单,这里不再赘述,可参考这位博主的文章。本文重点在环境配置。golang环境详细安装、配置_golang安装-CSDN博客 二、环境变量配置 1.添…...
导体、半导体和绝缘体
半导体可以根据不同的组合去改变电阻,所以可以用来制作芯片。...
shell 6 if条件判断与for循环结构 (泷羽sec)
声明 学习视频来自B站UP主 泷羽sec,如涉及侵泷羽sec权马上删除文章。 笔记只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 这节课旨在扩大自己在网络安全方面的知识面,了解网络安全领域的见闻,了…...
MetaGPT 安装
1. 创建环境 conda create -n metagpt python3.10 && conda activate metagpt2. 可编辑方式安装 git clone --depth 1 https://github.com/geekan/MetaGPT.git cd MetaGPT pip install -e .3. 配置 metagpt --init-config运行命令,在C盘位置C:\Users\325…...
论文阅读:Single-cell transcriptomics of 20 mouse organs creates a Tabula Muris
The Tabula Muris Consortium., Overall coordination., Logistical coordination. et al. Single-cell transcriptomics of 20 mouse organs creates a Tabula Muris. Nature 562, 367–372 (2018). 论文地址:https://doi.org/10.1038/s41586-018-0590-4 代码地址…...
图生3d 图生全景 学习笔记
目录 instantsplat Aluciddreamer ZoeDepth 会自动下载模型: 图生全景图SD-T2I-360PanoImage: instantsplat Sparse-view SfM-free Gaussian Splatting in Seconds 稀疏视图无SfM高斯喷洒 GitHub - NVlabs/InstantSplat: InstantSplat: Sparse-vi…...
分库分表—4.数据迁移系统文档
大纲 1.数据库设计 2.枚举类 3.接⼝设计 4.定时任务设计 (1)定时核对校验数据的定时任务 (2)数据量统计定时任务 (3)增量数据落地定时任务 (4)失败重试定时任务 5.技术亮点 (1)滚动拉取方案 (2)巧妙的统计滚动进度方案 (3)防止增量同步数据丢失和高效写入方案 (4)…...
HAMR技术进入云存储市场!
2024年12月3日,Seagate宣布其Mozaic 3系列HAMR(热辅助磁记录)硬盘获得了来自一家领先云服务提供商(可能AWS、Azure或Google Cloud其中之一)以及其他高容量硬盘客户的资格认证。 Seagate的Mozaic 3技术通过引入热辅助磁…...
Vulnhub---kioptirx5 超详细wp
个人博客 WuTongSec 欢迎大佬指点 打点 nmap 192.168.128.0/24 -sP 找ip nmap 192.168.128.137 --min-rate 10000 -p- 简单全端口扫描 nmap 192.168.128.137 -sC -sV -O -sT 详细 脚本 版本 系统 扫描 dirsearch -u http://192.168.128.137 目录扫描 PORT S…...
单片机状态机实现多个按键同时检测单击、多击、长按等操作
1.背景 在之前有个项目需要一个或多个按键检测:单击、双击、长按等操作 于是写了一份基于状态机的按键检测,分享一下思路 2.实现效果 单击翻转绿灯电平 双击翻转红灯电平 长按反转红绿灯电平 实现状态机检测按键单击,双击,长…...
oracle之用户的相关操作
(1)创建用户(sys用户下操作) 简单创建用户如下: CREATE USER username IDENTIFIED BY password; 如果需要自定义更多的信息,如用户使用的表空间等,可以使用如下: CREATE USER mall IDENTIFIED BY 12345…...
黑马redis
Redis的多IO线程只是用来处理网络请求的,对于读写操作命令Redis仍然使用单线程来处理 Redisson分布式锁实现15问 文章目录 主线程和IO线程是如何协作的Unix网络编程中的五种IO模型Linux世界一切皆文件生产上限制keys *、flushdb、flushall等危险命令keys * 遍历查询100W数据花…...
HCIA-Access V2.5_1_2 PON技术的特点、优势与典型应用
PON接入技术优势 它的接入方式有两种,点到点光接入和点到多点光接入。 点到点 PON口的资源被一个用户独占,该用户可以享受到更好的带宽体验,同时故障好排查,出现问题,重点检测这一条链路以及终端用户,同…...
css部分
前面我们学习了HTML,但是HTML仅仅只是做数据的显示,页面的样式比较简陋,用户体验度不高,所以需要通过CSS来完成对页面的修饰,CSS就是页面的装饰者,给页面化妆,让它更好看。 1 层叠样式表&#…...
【TCP 网络通信(发送端 + 接收端)实例 —— Python】
TCP 网络通信(发送端 接收端)实例 —— Python 1. 引言2. 创建 TCP 服务器(接收端)2.1 代码示例:TCP 服务器2.2 代码解释: 3. 创建 TCP 客户端(发送端)3.1 代码示例:TCP…...
LSTM+改进的itransformer时间序列预测模型代码
代码在最后 本次设计了一个LSTM基于差分多头注意力机制的改进的iTransformer时间序列预测模型结合了LSTM(长短期记忆网络)和改进版的iTransformer(差分多头注意力机制),具备以下优势: 时序特征建模能力&am…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
