数据结构 ——— 层序遍历链式二叉树
目录
链式二叉树示意图编辑
何为层序遍历
手搓一个链式二叉树
实现层序遍历链式二叉树
链式二叉树示意图
何为层序遍历
和前中后序遍历不同,前中后序遍历链式二叉树需要利用递归才能遍历
而层序遍历是非递归的形式,如上图:层序遍历的结果:1,2,4,3,5,6
手搓一个链式二叉树
代码演示(以上图为例):
// 数据类型
typedef int BTDataType;// 二叉树节点的结构
typedef struct BinaryTreeNode
{BTDataType data; //每个节点的数据struct BinaryTreeNode* left; //指向左子树的指针struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;// 申请新节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));// 判断是否申请成功if (newnode == NULL){perror("malloc fail");return NULL;}// 初始化newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* CreatBinaryTree()
{BTNode* n1 = BuyNode(1);assert(n1);BTNode* n2 = BuyNode(2);assert(n2);BTNode* n3 = BuyNode(3);assert(n3);BTNode* n4 = BuyNode(4);assert(n4);BTNode* n5 = BuyNode(5);assert(n5);BTNode* n6 = BuyNode(6);assert(n6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}
实现层序遍历链式二叉树
实现思路:
利用队列的先进先出的性质,实现层序遍历链式二叉树
如上图所示:先将 1 节点入队列,再将 1 节点出队列,在 1 节点出队列的时候,把 2、4 节点带入队列,2 节点再出队列,2 节点出队列的时候,把 3 节点带入队列,然后就是 4 节点出队列,同样出队列的时候,将 5、6 节点带入队列,最后再依次出队列,所有数据出完队列后,根据出队列的顺序,就是层序遍历的顺序
实现前要先构建一个简易队列以及队列的基本函数:
// 数据类型
typedef BTNode* QDataType;// 链式队列每个节点的结构
typedef struct QueueNode
{struct QueueNode* next; //指向下一个节点的指针QDataType data; //当前节点的数据
}QNode;// 链式队列的结构
typedef struct Queue
{QNode* phead; //指向队头节点的指针QNode* ptail; //指向队尾节点的指针int size; //队列的总数据个数
}Queue;// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}// 数据入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 申请新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));// 判断是否申请成功if (newnode == NULL){perror("malloc fail");return;}// 初始化新节点newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) //当队列中没有数据的情况{// 双重判断,更加保险assert(pq->ptail == NULL);// 头尾都指向新节点即可pq->phead = newnode;pq->ptail = newnode;}else //当队列已有数据的情况{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 数据出队列
void QueuePop(Queue* pq)
{assert(pq);// 当队列中没有数据的情况if (pq->phead == NULL){perror(pq->phead);return;}if (pq->phead->next == NULL) //当队列中只有一个数据的情况{free(pq->phead);pq->phead = NULL;pq->ptail = NULL;}else //当队列中有多个数据的情况{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}// 访问队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);// 当队列中没有数据的情况if (pq->phead == NULL){perror(pq->phead);return -1;}return pq->phead->data;
}// 判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return (pq->phead == NULL) && (pq->ptail == NULL);
}// 释放队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
在定义队列数据时,需要定义链式二叉树节点的指针,这样才能找到二叉树节点的左右子树
代码实现:
void LevelOrder(BTNode* root)
{// 定义队列Queue q;// 初始化队列QueueInit(&q);// 先将二叉树的根节点的指针入队列if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){// 访问队头数据BTNode* front = QueueFront(&q);printf("%d ", front->data);// 队头数据出队列QueuePop(&q);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");
}
代码解析:
当队列为空时,链式二叉树的层序遍历就实现了
但最开始队列没有数据,所以要先将指向根节点的指针存放入队列
且存放节点指针是为了方便查找左右子树
然后在利用 while 循环,只要队列不为空,就循环下去
先访问队头的数据,队头的数据就是链式二叉树节点的指针
所以使用 BTNode* front 来接收,再利用 printf 函数打印指针所指向节点中的数据
再把队头数据出队列,并且把出队列那个节点的左右子树存放入队列
注意为空时就不要放入队列,所以每次放入队列前要判断是否为空
直到队列为空时,也就是不满足 while 循环时,层序遍历就实现了
此代码的关键是利用 BTNode* front 接收每次要出队列的节点指针,这样就方便查找当前节点的左右子树,并且利用 BTNode* front 接收从而替代了递归逻辑
代码验证:
相关文章:
数据结构 ——— 层序遍历链式二叉树
目录 链式二叉树示意图编辑 何为层序遍历 手搓一个链式二叉树 实现层序遍历链式二叉树 链式二叉树示意图 何为层序遍历 和前中后序遍历不同,前中后序遍历链式二叉树需要利用递归才能遍历 而层序遍历是非递归的形式,如上图:层序遍历的…...
使用 Prompt API 与您的对象聊天
tl;dr:GET、PUT、PROMPT。现在,可以使用新的 PromptObject API 仅使用自然语言对存储在 MinIO 上的对象进行总结、交谈和提问。在本文中,我们将探讨这个新 API 的一些用例以及代码示例。 赋予动机: 对象存储和 S3 API 的无处不在…...
SpringBoot整合Mybatis-Plus实践汇总
相关依赖 MyBatis-Plus涉及的依赖主要是Mybatis-start、和分页插件的依赖,不考虑使用额外分页插件的前提下,只需要mybatis-plus-boot-starter一个依赖即可与SpringBoot集成: <!--Mybatis-plugs--><dependency><groupId>co…...
基于Spring Boot的在线性格测试系统设计与实现(源码+定制+开发)智能性格测试与用户个性分析平台、在线心理测评系统的开发、性格测试与个性数据管理系统
博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台…...
Python实现人脸识别算法并封装为类库
引言 人脸识别技术在现代社会中应用广泛,从安全监控到智能门锁,再到社交媒体中的照片标记功能,都离不开这项技术。本文将详细介绍如何使用Python实现基本的人脸识别算法,并将其封装为一个类库,以便在多个项目中复用。…...
uniapp小程序分享使用canvas自定义绘制 vue3
使用混入结合canvas做小程序的分享 在混入里面定义一个全局共享的分享样式,在遇到特殊页面需要单独处理 utils/share.js import { ref } from vue; export default {onShow() {// 创建时设置统一页面的默认值uni.$mpShare {title: 分享的标题,path: /pages/home/…...
SpringCloud核心组件(四)
文章目录 NacosNacos 配置中心1.起源2.基本概念ProfileData IDGroup 3.基础配置a. bootstrap.ymlb. application.ymlc. nacos 中的配置 DataIDd.测试读取配置中心配置内容 4.配置隔离a.命名空间b.DataIDc.bootstrap.ymld.service 隔离 5.配置拆分a.配置拆分策略b.DataID 配置c.…...
如何把本地docker 镜像下载用到centos系统中呢?
如果需要将镜像下载到本地或在 CentOS 系统上使用该镜像,你可以按照以下步骤操作: 1. 拉取镜像 如果想将镜像从 Docker Hub 或其他镜像仓库下载到本地,可以使用 docker pull 命令。 如果使用的是本地构建的镜像(如 isc:v1.0.0&…...
Godot的开发框架应当是什么样子的?
目录 前言 全局协程还是实例协程? 存档! 全局管理类? UI框架? Godot中的异步(多线程)加载 Godot中的ScriptableObject 游戏流程思考 结语 前言 这是一篇杂谈,主要内容是对我…...
GitHub新手入门 - 从创建仓库到协作管理
GitHub新手入门 - 从创建仓库到协作管理 GitHub 是开发者的社交平台,同时也是代码托管的强大工具。无论是个人项目、开源协作,还是团队开发,GitHub 都能让你轻松管理代码、版本控制和团队协作。今天,我们将从基础开始,…...
作业25 深度搜索3
作业: #include <iostream> using namespace std; bool b[100][100]{0}; char map[100][100]{0}; int dx[4]{0,1,0,-1}; int dy[4]{1,0,-1,0}; int n,m; int sx,sy,ex,ey; int mink2147483647; void dfs(int,int,int); int main(){cin>>n>>m;for(…...
ubuntu20.04 colmap 安装2024.11最新
很多教程都很落后了,需要下载压缩包解压编译的很麻烦 现在就只需要apt install就可以了 apt更新 sudo apt update && sudo apt-get upgrade安装依赖 #安装依赖 sudo apt-get install git cmake ninja-build build-essential libboost-program-options-de…...
WebRTC视频 03 - 视频采集类 VideoCaptureDS 上篇
WebRTC视频 01 - 视频采集整体架构 WebRTC视频 02 - 视频采集类 VideoCaptureModule [WebRTC视频 03 - 视频采集类 VideoCaptureDS 上篇](本文) WebRTC视频 04 - 视频采集类 VideoCaptureDS 中篇 WebRTC视频 05 - 视频采集类 VideoCaptureDS 下篇 一、前…...
python os.path.basename(获取路径中的文件名部分) 详解
os.path.basename 是 Python 的 os 模块中的一个函数,用于获取路径中的文件名部分。它会去掉路径中的目录部分,只返回最后的文件名或目录名。 以下是 os.path.basename 的详细解释和使用示例: 语法 os.path.basename(path) 参数 path&…...
《FreeRTOS任务基础知识以及任务创建相关函数》
目录 1.FreeRTOS多任务系统与传统单片机单任务系统的区别 2.FreeRTOS中的任务(Task)介绍 2.1 任务特性 2.2 FreeRTOS中的任务状态 2.3 FreeRTOS中的任务优先级 2.4 在任务函数中退出 2.5 任务控制块和任务堆栈 2.5.1 任务控制块 2.5.2 任务堆栈…...
036集——查询CAD图元属性字段信息:窗体显示(CAD—C#二次开发入门)
提取CAD图元所有属性字段,通过窗体显示,效果如下:(curve改为entity) 代码如下: public void 属性查询() {List<Curve> ents Z.db.SelectEntities<Curve>();if (ents is null ||ents.Cou…...
Swift从0开始学习 函数和闭包 day2
一、函数 1.1函数定义 使用 func 来声明一个函数,使用名字和参数来调用函数。使用 -> 来指定函数返回值的类型。 示例:拼接字符串 //有参数和返回值的函数 func append1(name : String, description : String) -> String {return "\(name)…...
内网、公网(外网)划分
内网、公网(外网)划分 声明! 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下,如涉及侵权马上删除文章 笔记只是方便各位师傅的学习和探讨,文章所提到的网站以及内容,只做学习交流,其…...
【linux】centos7 换阿里云源
相关文章 【linux】CentOS 的软件源(Repository)学习-CSDN博客 查看yum配置文件 yum的配置文件通常位于/etc/yum.repos.d/目录下。你可以使用以下命令查看这些文件: ls /etc/yum.repos.d/ # 或者 ll /etc/yum.repos.d/备份当前的yum配置文…...
用OMS进行 OceanBase 租户间数据迁移的测评
基本概念 OceanBase迁移服务(,简称OMS),可以让用户在同构或异构 RDBMS 与OceanBase 数据库之间进行数据交互,支持数据的在线迁移,以及实时增量同步的复制功能。 OMS 提供了可视化的集中管控平台ÿ…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
