【数据结构】二叉树的模拟实现

前言:前面我们学习了堆的模拟实现，今天我们来进一步学习二叉树，当然了内容肯定是越来越难的，各位我们一起努力！

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！
在这里插入图片描述

什么是树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。光看文字可能大家理解不了，我们看下图。在这里插入图片描述

树的相关概念

  1. 节点的度：一个节点含有的子树的个数称为该节点的度。 如上图：A的为3。
  2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：F、G、H、I…等节点为叶节点。
  3. 非终端节点或分支节点：度不为0的节点； 如上图：B、C、D…等节点为分支节点.
  4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。 如上图：A是B的父节点。
  5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。 如上图：B是A的孩子节点。
  6. 兄弟节点：具有相同父节点的节点互称为兄弟节点。 如上图：B、C是兄弟节点。
  7. 树的度：一棵树中，最大的节点的度称为树的度。 如上图：树的度为5。
  8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
  9. 树的高度或深度：树中节点的最大层次。如上图：树的高度为4。
  10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟。如上图：G、G互为兄弟节点 。
  11. 节点的祖先：从根到该节点所经分支上的所有节点。如上图：A是所有节点的祖先。
  12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
  13. 森林：由m（m>0）棵互不相交的树的集合称为森林。

什么是二叉树

二叉树是一种常见的树型数据结构，由若干个节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树有以下特点(如图所示)：

  1. 每个节点最多有两个子节点，且子节点的位置是固定的。
  2. 左子节点在父节点的左边，右子节点在父节点的右边。
  3. 二叉树的子树也是二叉树。
  4. 二叉树的每个节点都有一个值，可以是任意类型的数据。
    在这里插入图片描述

讲完了二叉树的基本性质，我们开始模拟实现二叉树吧!

二叉树的基本功能

  1. 前序遍历–根、左、右 – 深度优先遍历
  2. 计算树节点。
  3. 中序遍历–左、根、右
  4. 计算叶子节点
  5. 树的高度
  6. 求第k层结点的个数
  7. 二叉树查找值为x的结点
  8. 通过前序遍历的数组构建二叉树。
  9. 销毁二叉树
  10. 层序遍历 – 广度优先遍历
  11. 判断二叉树是否是完全二叉树

二叉树的初始化(手搓二叉树)

思路导读：由于通过数组创建二叉树比较难，我们先放在博客的后面在去讲解，但是我们又需要二叉树怎么办，那就手搓一个。
代码演示:

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}TreeNode;TreeNode* BuyNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}TreeNode* CreateTree()//创建二叉树
{TreeNode* node1 = BuyNode(1);TreeNode* node2 = BuyNode(30);TreeNode* node3 = BuyNode(2);TreeNode* node4 = BuyNode(71);TreeNode* node5 = BuyNode(99);TreeNode* node6 = BuyNode(11);TreeNode* node7 = BuyNode(21);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->right = node7;node3->left = node6;return node1;
}

创建好后的树的结构如下图所示
在这里插入图片描述

二叉树的前序遍历

思路导读:二叉树的前序遍历指先遍历二叉树的根，左子树，在遍历右子树。我们可以先画个图来模拟一下它遍历的顺序如下图：
在这里插入图片描述
既然图都画出来了，我们肯定思路都大致清晰了，那用什么方式去遍历呢？循环还是什么？今天我们要讲的方式是递归解决二叉树的遍历，这种是目前比较简单的方式。
代码实现：对于刚刚接触二叉树的友友们可能还不能理解这个递归的方式，没事可以看下图的递归展开图帮助你进一步理解

void PrevOrder(TreeNode* root)//前序遍历--根、左、右 -- 深度优先遍历
{if (root == NULL){return NULL;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

在这里插入图片描述
运行结果:在这里插入图片描述

二叉树的中序遍历

思路导读：二叉树的中序遍历指先遍历左子树，再遍历根，最后遍历右子树。这个就不为大家再画递归展开图了，看代码！
代码演示：

void InOrder(TreeNode* root)//中序遍历--左、根、右
{if (root == NULL){return NULL;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

运行结果：在这里插入图片描述

计算树节点

思路导读:我们要想计算树节点的个数，我们只需要将其左子树，右子树，还有根的值全部算出有多少即可，我们只需通过像前序遍历的思想来计算。如果不懂的话可以看下面的递归展开图(博主就画了前几步)。在这里插入图片描述
代码实现:

int TreeSize(TreeNode* root)//计算树节点
{if (root == NULL){return 0;}return TreeSize(root->right) + TreeSize(root->left) + 1;}

计算叶子节点

思路导读:我们可以通过遍历该树的左子树和右子树，如果左子树和右子树同时为NULL我们就让它返回1，以此类推，我们可以通过像前面一样的方式遍历二叉树达到计算叶子节点的效果(部分递归展开图)。
在这里插入图片描述
代码实现:

int TreeLeafSize(TreeNode* root)//计算叶子节点
{if (root == NULL){return 0;}if((root->left)== NULL &&(root->right) == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

计算树的高度

思路导读:计算树的高度我们可以通过比较它的左子树和右子树找出其树高度中较大的那个然后加上一即可算出来这个树的高度，怎么比较呢？那我们就可以通过利用fmax这个函数来比较其找到最大值。
(部分递归展开图如下)在这里插入图片描述
代码实现:

int TreeHight(TreeNode* root)//树给高度
{if (root == NULL){return 0;}//fmax函数，它是C语言（C99）中的一个内置函数，用于比较两个浮点数的大小并返回较大值。return fmax(TreeHight(root->left), TreeHight(root->right)) + 1;
}

求第k层节点的个数

思路导读:要想求第k层节点的个数我们需要将该层中左子树和右子树的位置分别记录下来，然后将其相加就是该层的个数。那么另一个问题来了，我们如何找到是这一层呢？我们可以通过每让它往下走一层时，就让k-1,依次递归，当k完全等于1的时候说明已经到了这一层，再返回1即可。（递归展开图如下）
在这里插入图片描述
代码实现:

int TreeLevelK(TreeNode* root, int k)//求第k层结点的个数
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;

二叉树查找值为x的节点

思路导读:我们通过前面写了这么多的二叉树的接口，这里我们可以想到，我们先查左子树中是否有相同的，然后我们再去查看右子树中是否有相同的，如果左子树找到了就将该值返回即可。(部分递归展开图如下)
在这里插入图片描述
代码实现:

TreeNode* TreeFind(TreeNode* root, BTDataType x)//二叉树查找值为x的结点
{if (root == NULL){return NULL;}if (root->data == x){return root;} TreeNode* cur = TreeFind(root->left,x);//先找左子树,通过指针记录，防止找到了接着往下走if (cur){return cur;}TreeNode* cur1 = TreeFind(root->right, x);//再找右子树,同理指针记录if (cur1){return cur1;}return NULL;
}

通过前序遍历的数组构建二叉树

我们先假定传来的数组为:char arr[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };
该’#'代表NULL，因此我们先画出其前序遍历的展开图(如下)：
在这里插入图片描述
然后我们只需要像前序遍历一样，将其按照根、左子树、右子树一样依次开辟结点赋值，此时我们要注意的是一定要使用指针，防止在递归的过程中其值不会变化。
代码实现如下:

TreeNode* TreeCreate2(char* a, int* pi)//通过前序遍历的数组构建二叉树
{if (*(a + *pi) =='#'){(*pi)++;return NULL ;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->data = *(a + (*pi)++);root->left = TreeCreate2(a, pi);root->right = TreeCreate2(a, pi);return root;
}

运行结果:
在这里插入图片描述

二叉树的销毁

思路导读:二叉树的销毁可以像二叉树的后序遍历一样先左子树、右子树
代码实现:

void DestoryTree(TreeNode* root)//销毁
{if (root == NULL){return NULL;}DestoryTree(root->left);DestoryTree(root->right);free(root);}

层序遍历 – 广度优先遍历

思路导读:我们知道二叉树的一个特性，每一个节点都有俩个子节点，因此我们在可以充分的利用这个特性来实现我们层序遍历，我们可以模拟实现一个队列，让二叉树的根先存进去队列，然后打印其数据，就打印了第一层的数据，此时我们要打印第二层的数据，我们只需要将根的左子树和右子树在分别存入队列，在第二次循环中在依次打印即可实现层序遍历了。记住一定在队列中存的是二叉树根的地址而不是值（如下图所示）在这里插入图片描述
代码实现:

void levelorder(TreeNode* root)//层序遍历 -- 广度优先遍历
{QNode q1;QueueInit(&q1);// TreeHight(root);if (root){//QueuePush(Queue * pq, QDataType x)QueuePush(&q1, root);}int level = 1;while (!QueueEmpty(&q1)){while (level--){TreeNode* front = QueueFront(&q1);//将头元素地址保存在二叉树中QueuePop(&q1);printf("%c ", front->data);if (front->left){QueuePush(&q1, front->left);}if (front->right){QueuePush(&q1, front->right);}}level = QueueSize(&q1);printf("\n");}QueueDestroy(&q1);

测试函数:

void Test1()
{TreeNode* root = CreateTree1();char arr[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };int i = 0;levelorder(TreeCreate2(arr, &i));
}

运行结果:在这里插入图片描述

判断是否是完全二叉树

思路导读:我们可以像前面一样，让它们依次层次入队列，如果在入队列的过程中就碰到了NULL，就说明其不是完全二叉树，然后再将最后一层中队列的元素依次出队列，如果出队列的途中也碰到了NULL也就说明其不是完全二叉树。如果都没碰到则是完全二叉树。
在这里插入图片描述
代码实现：

bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

🫵🫵🫵 祝各位接下来好运连连 💞

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/222112.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

大创项目推荐 深度学习 机器视觉 人脸识别系统 - opencv python

大创项目推荐 深度学习 机器视觉 人脸识别系统 - opencv python

文章目录 0 前言1 机器学习-人脸识别过程人脸检测人脸对其人脸特征向量化人脸识别 2 深度学习-人脸识别过程人脸检测人脸识别Metric Larning 3 最后 0 前言 🔥 优质竞赛项目系列，今天要分享的是 🚩 深度学习 机器视觉 人脸识别系统 该项目…
阅读更多...
LabVIEW开发自动驾驶的双目测距系统

LabVIEW开发自动驾驶的双目测距系统

LabVIEW开发自动驾驶的双目测距系统 随着车辆驾驶技术的不断发展，自动驾驶技术正日益成为现实。从L2级别的辅助驾驶技术到L3级别的受条件约束的自动驾驶技术，车辆安全性和智能化水平正在不断提升。在这个过程中，车辆主动安全预警系统发挥着关…
阅读更多...
CloudCanal x Debezium 打造实时数据流动新范式

CloudCanal x Debezium 打造实时数据流动新范式

简述 Debezium 是一个开源的数据订阅工具，主要功能为捕获数据库变更事件发送到 Kafka。 CloudCanal 近期实现了从 Kafka 消费 Debezium 格式数据，将其 同步到 StarRocks、Doris、Elasticsearch、MongoDB、ClickHouse 等 12 种数据库和数仓，…
阅读更多...
simulink代码生成（一）——环境搭建

simulink代码生成（一）——环境搭建

一、安装C2000的嵌入式环境； 点击matlab附加功能， 然后搜索C2000，安装嵌入式硬件支持包；点击安装即可；（目前还不知道破解版的怎么操作，目前我用的是正版的这样，完全破解的可能操作…
阅读更多...
华为数通方向HCIP-DataCom H12-831题库(多选题：201-220）

华为数通方向HCIP-DataCom H12-831题库(多选题：201-220）

第201题 在多集群RR组网中，每个集群中部署了一台RR设备及其客户机，各集群的RR与为非客户机关系，并建立IBGP全连接。以下关于BGP路由反射器发布路由规则的描述，正确的有哪些? A、若某RR从EBGP对等体学到的路由，此RR会传递给其他集群的RR B、若某RR从非客户机IBGP对等体学…
阅读更多...
Axure之中继器的使用（交互动作reperter属性Item属性）

Axure之中继器的使用（交互动作reperter属性Item属性）

目录 一.中继器的基本使用 二.中继器的动作（增删改查） 2.1 新增 2.2 删除 2.3 更新行 2.4 效果展示 2.5 模糊查询 三.reperter属性 在Axure中，中继器（Repeater）是一种功能强大的组件，用于创建重复…
阅读更多...
C# 使用MSTest进行单元测试

C# 使用MSTest进行单元测试

目录 写在前面 代码实现 执行结果 写在前面 MSTest是微软官方提供的.NET平台下的单元测试框架；可使用DataRow属性来指定数据，驱动测试用例所用到的值，连续对每个数据化进行运行测试，也可以使用DynamicData 属性来指定数据&…
阅读更多...
Flink系列之：Savepoints

Flink系列之：Savepoints

Flink系列之：Savepoints 一、Savepoints二、分配算子ID三、Savepoint 状态四、算子五、触发Savepoint六、Savepoint 格式七、触发 Savepoint八、使用 YARN 触发 Savepoint九、使用 Savepoint 停止作业十、从 Savepoint 恢复十一、跳过无法映射的状态恢复十二、Resto…
阅读更多...
IEEE TASLP | 联合语音识别与口音识别的解耦交互多任务学习网络

IEEE TASLP | 联合语音识别与口音识别的解耦交互多任务学习网络

尽管联合语音识别（ASR）和口音识别（AR）训练已被证明对处理多口音场景有效，但当前的多任务ASR-AR方法忽视了任务之间的粒度差异。细粒度单元（如音素、声韵母）可用于捕获与发音相关的口音特征&…
阅读更多...
ruoyi若依前后端分离版部署centos7服务器(全)

ruoyi若依前后端分离版部署centos7服务器(全)

目录 VMware虚拟机 centos7 安装环境如下 一、msql 5.7 二、nginx1.23.3 三、java8 四、redis 3.2.1 五、部署若依前端 六、部署若依后端 前言 虚拟机的桥接与nat模式 : 重点 重点！！！ 无线不可以用桥接模式 ，而你用了nat模式会…
阅读更多...
安全狗云原生安全-云甲·云原生容器安全管理系统

安全狗云原生安全-云甲·云原生容器安全管理系统

随着云计算的快速发展，容器技术逐渐成为主流。然而，随着容器的普及，安全问题也日益突出。为了解决这一问题，安全狗推出了云原生容器安全管理系统——云甲。 云甲是安全狗云原生安全的重要组成部分，它采用了先进的云原生…
阅读更多...
版本化数据库管理工具Flyway介绍和Spring Boot集成使用

版本化数据库管理工具Flyway介绍和Spring Boot集成使用

文章目录 核心功能如何使用 Flyway最佳实践Spring Boot使用 Flyway 是一个版本化数据库管理工具，用于跟踪、管理和应用数据库的变化。它非常适合在团队开发环境中使用，其中多个人员可能会在数据库结构进行更改。Flyway 通过版本控制可以帮助你确保所有人…
阅读更多...
Redis-Day3实战篇-商户查询缓存(缓存的添加和更新, 缓存穿透/雪崩/击穿, 缓存工具封装)

Redis-Day3实战篇-商户查询缓存(缓存的添加和更新, 缓存穿透/雪崩/击穿, 缓存工具封装)

Redis-Day3实战篇-商户查询缓存 什么是缓存添加Redis缓存业务流程项目实现练习 - 给店铺类型查询业务添加缓存 缓存更新策略最佳实践方案案例 - 给查询商铺的缓存添加超时剔除和主动更新 缓存穿透/雪崩/击穿缓存穿透概述项目实现 - 商铺查询缓存 缓存雪崩缓存击穿概述互斥锁逻辑…
阅读更多...
SpringCloudGateway网关处拦截并修改请求

SpringCloudGateway网关处拦截并修改请求

SpringCloudGateway网关处拦截并修改请求 需求背景 老系统没有引入Token的概念，之前的租户Id拼接在请求上，有的是以Get，Param传参形式；有的是以Post，Body传参的。需要在网关层拦截请求并进行请求修改后转发到对应服务。…
阅读更多...
使用pytest+selenium+allure实现web页面自动化测试

使用pytest+selenium+allure实现web页面自动化测试

测试文件 base 基本方法data 测试数据page web页面相关操作image 测试截图log 日志文件report 测试报告文件temp 临时文件tool 文件读取，发邮件文件TestCases 测试用例 在page下的__init__.py文件下配置 import os import time from selenium.webdriver.common.by…
阅读更多...
10 Vue3中v-html指令的用法

10 Vue3中v-html指令的用法

概述 v-html主要是用来渲染富文本内容，比如评论信息，新闻信息，文章信息等。 v-html是一个特别不安全的指令，因为它会将文本以HTML的显示进行渲染，一旦文本里面包含一些恶意的js代码，可能会导致整个网页发…
阅读更多...
12、Qt：用QProcess类启动外部程序：简单使用

12、Qt：用QProcess类启动外部程序：简单使用

一、说明 简单使用：在一个函数中，使用QProcess类的临时对象调用可执行文件exe，只有这个exe执行完了，这个函数才往下执行，一次性打印出exe所有输出信息；复杂使用：创建QProcess类的全局对象&…
阅读更多...
Python---TCP 客户端程序开发

Python---TCP 客户端程序开发

1. 开发 TCP 客户端程序开发步骤回顾 创建客户端套接字对象和服务端套接字建立连接发送数据接收数据关闭客户端套接字 2. socket 类的介绍 导入 socket 模块 import socket 创建客户端 socket 对象 socket.socket(AddressFamily, Type) 参数说明: AddressFamily 表示IP地…
阅读更多...
重塑数字生产力体系，生成式AI将开启云计算未来新十年？

重塑数字生产力体系，生成式AI将开启云计算未来新十年？

科技云报道原创。 今天我们正身处一个历史的洪流，一个巨变的十字路口。生成式AI让人工智能技术完全破圈，带来了机器学习被大规模采用的历史转折点。 它掀起的新一轮科技革命，远超出我们今天的想象，这意味着一个巨大的历史机遇正…
阅读更多...
医院影像科PACS系统源码，医学影像系统，支持MPR、CPR、MIP、SSD、VR、VE三维图像处理

医院影像科PACS系统源码，医学影像系统，支持MPR、CPR、MIP、SSD、VR、VE三维图像处理

PACS系统是医院影像科室中应用的一种系统，主要用于获取、传输、存档和处理医学影像。它通过各种接口，如模拟、DICOM和网络，以数字化的方式将各种医学影像，如核磁共振、CT扫描、超声波等保存起来，并在需要时能够快速调取…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023