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

【数据结构】遍历二叉树

news 来源：原创 2025/7/13 0:44:26

遍历二叉树的算法描述（递归定义）

先序遍历

若二叉树为空，则空操作；

否则

（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）先序遍历右子树中序遍历若二叉树为空…...

编程日记 2025/7/13 0:44:26

鸿蒙获取 APP 信息及手机信息

前言：获取 APP 版本信息可以通过 bundleManager.getBundleInfoForSelfSync(bundleFlags) 去获取，获取手机信息可以通过 kit.BasicServicesKit 库去获取，以下是封装好的工具类。 import bundleManager from ohos.bundle.bundleManager; impo…...

编程日记 2025/7/13 0:30:18

OpenWRT下深入了解IPv6——SLAAC

一、SLAAC（无状态地址自动配置） 1.基本原理 SLAAC 是 IPv6 中的一种地址自动配置机制，它允许设备根据网络中的路由器通告信息和自身的 MAC 地址自动生成 IPv6 地址。在 IPv6 网络中，MAC 地址长度为 48 位，而 IPv6 地…...

编程日记 2025/7/9 13:41:40

UE5水文章 UI按钮样式快捷复制黏贴

shift右键拷贝 shift右键黏贴...

编程日记 2025/7/13 0:14:52

迭代器模式的理解和实践

引言在软件开发中，我们经常需要遍历容器对象（如数组、列表、集合等）中的元素。如果每个容器对象都实现自己的遍历算法，那么代码将会变得冗余且难以维护。为了解决这个问题，迭代器模式应运而生。迭代器模式是一种行为型…...

编程日记 2025/7/12 23:14:48

Python __func 与 _func 的区别引起的思考

文章目录 __function_function深入名称修饰机制名称修饰的目的实现原理属性访问控制的高级模式基本模式扩展复杂的转换和验证逻辑带有日志和审计的访问控制如果突然让我说一说 Python中的__function和_function有哪些不同的约定和用途，我好像一下子没法说出很多东…...

编程日记 2025/7/13 0:40:44

python学opencv|读取视频（二）制作gif

【1】引言前述已经完成了图像和视频的读取学习，本次课学习制作gif格式动图。【2】教程实际上想制作gif格式动图是一个顺理成章的操作，完成了图像和视频的处理，那就自然而然会对gif的处理也产生兴趣。不过在opencv官网、matplotlib官网…...

编程日记 2025/7/13 0:23:28

Redmi AX3000 (RA81) 路由器恢复原厂固件

最近给Redmi AX3000 (RA81) 刷了OpenWrt固件，但是存在各种小问题，因此决定刷回原厂固件。刷机之前保证能够访问路由器ssh，否则请百度救砖教程。准备工具 Redmi AX3000 (RA81) 原厂分区文件 [github下载地址 / csdn下载地址]小米路由器修复…...

编程日记 2025/7/13 0:28:17

【调试工具】USB 转 UART 适配器（USB 转 TTL）

「USB 转 TTL 转换器」是错误的叫法，正确的叫法应该为「USB 转 UART 适配器」。 Device connection 注意端口的交叉连接，Device1_TX<---->Device2_RX USB-to-UART adapter GND 记得接地。使用： 当 TX,RX 需要电平为 0-3.3V 时&am…...

编程日记 2025/7/12 0:04:22

【YOLO部署Android安卓手机APP】YOLOv11部署到安卓实时目标检测识别——以火焰烟雾目标检测识别举例（可自定义更换其他目标）

前言：本项目基于YOLOv11部署到手机APP实现对火焰烟雾的检测识别，当然，以此你可以按照本项目开发步骤扩展更换为其他目标进行检测，例如更换为车牌、手势、人脸面部活动、人脸表情、火焰烟雾、行人、口罩、行为、水果、植物、农作物等等部署手机APP进行检测。本文为详细设计/…...

编程日记 2025/7/13 0:05:47

Python 中的 slots 属性有什么作用？

__slots__ 是Python类中的一种特殊属性，它允许你显式地声明一个类的实例可以拥有的属性。这不仅有助于节省内存，还能提高属性访问的速度，并且防止动态添加不属于设计的属性。在大型项目或者对性能敏感的应用程序中，正确使用 _…...

编程日记 2025/7/13 0:41:23

【H2O2|全栈】Node.js与MySQL连接

目录前言开篇语准备工作初始配置创建连接池操作数据库封装方法结束语前言开篇语本节讲解如何使用Node.js实现与MySQL数据库的连接，并将该过程进行函数封装。与基础部分的语法相比，ES6的语法进行了一些更加严谨的约束和优化&#…...

编程日记 2025/7/13 0:24:48

【大数据技术基础】课程第3章 Hadoop的安装和使用大数据基础编程、实验和案例教程（第2版）

第3章 Hadoop的安装和使用 3.1 Hadoop简介 Hadoop是Apache软件基金会旗下的一个开源分布式计算平台，为用户提供了系统底层细节透明的分布式基础架构。Hadoop是基于Java语言开发的，具有很好的跨平台特性，并且可以部署在廉价的计算机集群中。H…...

编程日记 2025/7/13 0:17:37

DDR4与DDR3服务器内存的关键区别有哪些？

内存作为服务器性能的关键组件之一，已经经历了从DDR3到DDR4的过渡。DDR4内存相较于DDR3在多个方面有所提升，包括速度、带宽、功耗以及数据传输效率等。然而，尽管DDR4内存在性能上占有优势，DDR3内存依然在一些特定场景中得到了广泛…...

编程日记 2025/7/13 0:34:41

OceanBase 的探索与实践

作者：来自 vivo 互联网数据库团队- Xu Shaohui 本文总结了目前我们遇到的痛点问题并通过 OceanBase 的技术方案解决了这些痛点问题，完整的描述了 OceanBase 的实施落地，通过迁移到 OceanBase 实践案例中遇到的问题与解决方案让大家能更好的了…...

编程日记 2025/7/13 0:10:21

2024年安全员-A证证模拟考试题库及安全员-A证理论考试试题

2024年安全员-A证模拟考试题库及理论考试试题（一） 单选题根据《建筑施工企业主要负责人、项目负责人和专职安全生产管理人员安全生产管理规定》，项目负责人每月带班生产时间不得少于本月施工时间的（ ）。 A. 60% B. …...

编程日记 2025/7/13 0:31:43

安装Docker并使用WSL

引言 Windows Subsystem for Linux (WSL) 是一个在Windows上运行Linux二进制可执行文件（ELF格式）的兼容层。它允许开发者直接在Windows上运行Linux环境，而无需使用虚拟机。Docker是一个开源的应用容器引擎，它允许开发者打包应用以…...

编程日记 2025/7/8 19:56:55

【TCP 网络通信（发送端 + 接收端）实例 —— Python】

TCP 网络通信（发送端接收端）实例 —— Python 1. 引言2. 创建 TCP 服务器（接收端）2.1 代码示例：TCP 服务器2.2 代码解释： 3. 创建 TCP 客户端（发送端）3.1 代码示例：TCP…...

编程日记 2025/7/13 0:27:42

PostgreSQL和Oracle的sql差异 1.rownum （1）Oracle分页查询使用rownum，PostgreSQL使用limit offset ORACLEPOSTGRESQLselect * from (select rownum r,e.* from emp e where rownum <5) t where r>0;select * from emp limit 5 offset…...

编程日记 2025/7/12 21:55:22

阻塞队列详解

阻塞队列介绍队列是限定在一端进行插入，另一端进行删除的特殊线性表。先进先出(FIFO)线性表。允许出队的一端称为队头，允许入队的一端称为队尾。数据结构演示网站： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html Q…...

编程日记 2025/7/13 0:37:55

kali安装谷歌输入法

临时隐匿你IP地址 ifconfig 查询kali现在所用ip ifconfig eth0 所需要修改的ip/掩码24 修改临时ip格式命令安装中文输入法命令临时隐匿你IP地址 ifconfig 查询kali现在所用ip ifconfig eth0 所需要修改的ip/掩码24 修改临时ip格式命令安装中文输入法命令 apt-get in…...

编程日记 2025/7/13 0:00:26

C语言：编译与链接

本篇博客给大家带来的是代码从运行到生成可执行文件的流程和原理 🐟🐟文章专栏：C语言 🚀🚀若有问题评论区下讨论，我会及时回答 ❤❤欢迎大家点赞、收藏、分享你们的支持就是我创造的动力今日思想&#xf…...

编程日记 2025/7/13 0:33:11

VTK编程指南＜五＞：VTK中的坐标系统、空间变换及VTK矩阵详解

1、坐标系统计算机图形学里常用的坐标系统主要有 4 种，分别是 Model 坐标系统、World 坐标系统、View坐标系统和 Display坐标系统(这些名词在不同的书里的中文表述均有所差别，所以直接使用英文名词表示)，此外还有两种表示坐标点的方式&#…...

编程日记 2025/7/13 0:00:26

Linux centos7 下载MySQL5.7仓库的命令

wget 是一个非常强大的命令行工具，用于从网络上下载文件。它是 Linux 和其他 Unix-like 系统中常用的工具之一。wget 命令的各个参数有着不同的含义，下面是您提供的命令 wget -i -c http://dev.mysql.com/get/mysql57-community-release-el7-10.onarch.r…...

编程日记 2025/7/9 13:40:20

Java Serializable 序列化

Java的Serializable接口是Java序列化机制的核心，它允许一个对象的状态被转换为字节流，从而可以方便地进行存储或传输。序列化后的对象可以被写到数据库、存储到文件系统，或者通过网络传输。要在 Java 中使一个类可序列化，你需要…...

编程日记 2025/7/10 16:18:57

【QNX+Android虚拟化方案】136 - QNX 侧 Coredump 文件解析

【QNX+Android虚拟化方案】136 - QNX 侧 Coredump 文件解析 1. 初始化 QNX 开发环境2. 使用 gdb 解析 Coredump3. 查看 backtrace：bt4. 查看所有线程信息5. 打印线程19的回溯信息6. 打印所有线程的回溯信息7. gdb info 相关的指令8. 查看使用了哪些共享库9. 查看出错的行号及地…...

编程日记 2025/7/12 23:14:38

ORB-SLAM2 ---- 词袋模型BOW

文章目录一、回环检测的重要性二、回环检测的方法三、词袋模型四、词典五、实例展示1. 计算评分2. 找出有相同单词的关键帧3. 用词袋进行快速匹配六、总结一、回环检测的重要性在前面的学习我们知道，噪声的影响是不可消除的，而上一帧的误差不可避免的…...

编程日记 2025/7/13 0:02:04

win11无法检测到其他显示器-NVIDIA

https://www.nvidia.cn/software/nvidia-app/ https://cn.download.nvidia.cn/nvapp/client/11.0.1.163/NVIDIA_app_v11.0.1.163.exe 下载安装后，检测驱动、更新驱动。...

编程日记 2025/7/13 0:05:47

基于Java+Swing+Mysql的网络聊天室

博主介绍： 大家好，本人精通Java、Python、C#、C、C编程语言，同时也熟练掌握微信小程序、Php和Android等技术，能够为大家提供全方位的技术支持和交流。我有丰富的成品Java、Python、C#毕设项目经验，能够为学生提供各类…...

编程日记 2025/7/11 18:15:13

docker安装Elasticsearch

公网即可拉取镜像，这个镜像是可以拉得到的，版本号根据自己需要的来 docker pull docker.elastic.co/elasticsearch/elasticsearch:7.17.15运行命令，xxxxxxxxxxxxxxxxxxxxxxxx_password 为自己的密码 docker run -d --name elasticsearch \-…...

编程日记 2025/7/13 0:32:29

Elasticsearch入门之HTTP高级查询操作

前言上一篇博客我们学习了es的一些基础操作如下： 创建索引（创建表 create table）查看索引（查看表show tables）查看单个索引（查看单个表show create table）删除索引（删除表&#x…...

编程日记 2025/7/8 19:17:51

前端知识1html

VScode一些快捷键 Ctrl/——注释 !——生成html框架元素 *n——生成n个标签直接书写html的名字回车生成对应的标签常见标签 span： <span style"color: red;">hello</span> <span>demo</span> span实现： 标题…...

编程日记 2025/7/12 23:53:27

《黑神话：悟空》闪退，提示D3D12崩溃，游戏崩溃无法启动是什么原因？要怎么解决？

《黑神话：悟空》闪退、D3D12崩溃及游戏无法启动：原因、解决方案与预防措施作为一名软件开发从业者，我深知电脑游戏运行时可能遇到的各种问题，尤其是像《黑神话：悟空》这样的高品质游戏，其对硬件和系统配置…...

编程日记 2025/7/8 15:29:11

[GESP202312 五级] 烹饪问题

题目传送门 B3930 [GESP202312 五级] 烹饪问题题目描述有 N N N 种食材，编号从 0 0 0 至 N − 1 N-1 N−1，其中第 i i i 种食材的美味度为 a i a_i ai。不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味…...

编程日记 2025/7/7 11:23:43

[代码随想录10]栈和队列

前言栈和队列在STL中扮演的什么角色呢？我们知道STL的六大组件是：容器，适配器，算法，迭代器，空间配置器，仿函数，而我们今天要学的栈和队列就是属于适配器里面的，为什么栈和…...

编程日记 2025/7/10 8:22:26

TesseractOCR-GUI：基于WPF/C#构建TesseractOCR简单易用的用户界面

前言前篇文章使用Tesseract进行图片文字识别介绍了如何安装TesseractOCR与TesseractOCR的命令行使用。但在日常使用过程中，命令行使用还是不太方便的，因此今天介绍一下如何使用WPF/C#构建TesseractOCR简单易用的用户界面。普通用户使用参照上一篇教…...

编程日记 2025/7/8 1:56:51

Java、JavaWeb、数据库-图书管理系统

这一章主要是把上一章写在网页里的java 代码从网页中分离出来，放在专门的servlet类中。每一个servlet类对应一个数据库的表。规范性问题： 1、dao包存放有关数据库的信息：BaseDao包就放数据库加载驱动和增删改和关闭资源；而其他…...

编程日记 2025/7/10 17:01:18

轻量化特征融合 | YOLOv8 引入一种基于增强层间特征相关性的轻量级特征融合网络 | 北理工新作

本改进已同步到Magic框架摘要—无人机图像中的小目标检测由于分辨率低和背景融合等因素具有挑战性，导致特征信息有限。多尺度特征融合可以通过捕获不同尺度的信息来增强检测，但传统策略效果不佳。简单的连接或加法操作无法充分利用多尺度融合的优势，导致特征之间的相关性不…...

编程日记 2025/7/8 18:35:16

U盘文件乱码：原因、恢复、预防与总结

U盘文件乱码现象解析 U盘作为我们日常生活中常用的便携式存储设备，时常会遭遇文件乱码的问题。这种乱码现象通常表现为文件名变成一堆无意义的字符，文件内容无法正常查看，甚至文件根本无法被打开。当我们在电脑上插入U盘，准备查看…...

编程日记 2025/7/10 8:07:55

OpenStack介绍

OpenStack概述 OpenStack是一个开源的云计算管理平台软件，主要用于构建和管理云计算环境。它允许企业或组织通过数据中心的物理服务器创建和管理虚拟机、存储资源和网络等云计算服务。其核心组件包括计算（Nova）、网络（Neutron）、存储（Cinder、Swift）等。这些组件相互协作…...

编程日记 2025/7/8 5:05:43

OpenGL编译用户着色器shader

shader相信很多朋友们都听说过，shader就是运行再GPU上的程序。虽然是这么说，但是我们发现，很多IDE开发工具比如说visual studio 没有办法直接去运行shader代码。这是因为，许多编译器不会自动将shader文件编译成可执行的代码然后发…...

编程日记 2025/7/8 22:06:02

C++ 已经知道，中序和后序，推算前序的方法。

已经知道，中序和后序，推算前序的方法。 #include<iostream> using namespace std; string ldr_str,lrd_str;//中序遍历和后序遍历 void build(int l1,int r1,int l2,int r2){if(l1>r1) return ;//边界条件,说明已经没有元素了cout<<lrd_s…...

编程日记 2025/7/11 19:49:20

unity打包到安卓帧率降低

这个问题遇到过很多次了我的做法就是直接设置Application.targetFrameRate60 参考...

编程日记 2025/7/6 15:46:26

计算机网络复习——概念强化作业

物理层负责网络通信的二进制传输用于将MAC地址解析为IP地址的协议为RARP。一个交换机接收到一帧,其目的地址在它的MAC地址表中查不到,交换机应该向除了来的端口外的所有其它端口转发。关于ICMP协议,下面的论述中正确的是ICMP可传送IP通信过程中出现的错误信息。在B类网络…...

编程日记 2025/7/12 22:06:21

DO、DTO、VO都是干什么的？

DO、DTO、VO 是三个常见的Java 对象，它们都是用来承载数据的，但是在不同的场景下有着不同的用途. 1.DO(Domain Object):领域对象，也称为实体对象。D0 通常用于数据库表的映射，DO中包含了实体的属性以及对实体的操作方法。DO 对应…...

编程日记 2025/7/4 22:07:12

深入探索 Node.js：构建强大的后端应用

亲爱的小伙伴们😘，在求知的漫漫旅途中，若你对深度学习的奥秘、JAVA 、PYTHON与SAP 的奇妙世界，亦或是读研论文的撰写攻略有所探寻🧐，那不妨给我一个小小的关注吧🥰。我会精心筹备，在…...

编程日记 2025/7/8 7:43:18

【Agent】构建智能诗歌创作系统：基于多 Agent 的协同创作实现

在探索大语言模型的创意应用过程中，我们开发了一个基于多 Agent 的智能诗歌创作系统。本文将介绍如何通过多个专业化的 Agent 协同工作，实现根据地点和天气信息自动创作诗歌的功能。 GitHub Code 项目地址核心架构设计 1. Agent 基类设计 from pydan…...

编程日记 2025/7/9 16:25:22

【Git】：远程操作

目录新建远程仓库克隆远程仓库向远程仓库推送拉取远程仓库配置 Git 忽略特殊文件给命令配置别名我们可以自己搭建⼀台运行 Git 的服务器，不过现阶段，为了学 Git 先搭个服务器绝对是小题大作。好在这个世界上有个叫 GitHub 的神奇的网站&#xff0…...

编程日记 2025/7/10 18:36:19

服务器数据恢复—LINUX下各文件系统删除/格式化的数据恢复可行性分析

Linux操作系统是世界上流行的操作系统之一，被广泛用于服务器、个人电脑、移动设备和嵌入式系统。Linux系统下数据被误删除或者误格式化的问题非常普遍。下面北亚企安数据恢复工程师简单聊一下基于linux的文件系统（EXT2/EXT3/EXT4/Reiserfs/Xfs&#xff0…...

编程日记 2025/7/9 23:26:36

基于python django的药材数据可视化系统的设计与实现，可对各类药材数据做一个统计分析可视化

研究背景随着中医药文化的不断传承与发展，传统中药材的市场需求逐渐增加。然而，随着药材种类繁多、来源复杂、品质参差不齐，如何高效地管理、分析与展示中药材的相关数据，成为现代中药产业面临的重要课题。传统的药材数据管理方…...

编程日记 2025/7/9 10:35:39

相关文章：