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

【数据结构】二叉树 链式结构的相关问题

 本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。

目录

1.前置说明

2.二叉树的遍历

2.1 前序、中序以及后序遍历

2.2 层次遍历

3.节点个数相关函数实现

3.1 二叉树节点个数

3.2 二叉树叶子节点个数

3.3 二叉树第k层节点个数

3.4 在二叉树中查找值为x的节点

4.二叉树基础oj练习

5.二叉树的创建和销毁

5.1 通过前序遍历构建二叉树

5.2 销毁二叉树

5.3 判断二叉树是否为完全二叉树


1.前置说明

在学习链式二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。

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 = newnode->right = NULL;return newnode;
}// 构建二叉树
BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->Left = node2;node1->Right = node4;node2->Left = node3;node4->Right = node5;node4->Left = node6;return node1;
}

注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式后面详解重点讲解。

再看二叉树基本操作前,再回顾下二叉树的概念二叉树是:

  1. 空树
  2. 非空:根节点,根节点的左子树、根节点的右子树组成的。

创建的二叉树图解: 

从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

2.二叉树的遍历

2.1 前序、中序以及后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
 

 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

  1. 前序遍历(Preorder Traversal亦称先序遍历)――访问根结点的操作发生在遍历其左右子树之前。
  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);

三个函数实现起来非常相似,只是访问数据的顺序不同。

具体实现:

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root==NULL){printf("# ");return;}printf("%c ",root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("#");return;}BinaryTreePrevOrder(root->left);printf("%c ", root->data);BinaryTreePrevOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("#");return;}BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);printf("%c ", root->data);
}

下面主要分析前序递归遍历,中序与后序图解类似,大家可自己动手绘制。

前序遍历递归图解:

 

前序遍历结果:1 2 3 4 5 6

中序遍历结果:3 2 1 5 4 6

后序遍历结果:3 2 5 6 4 1
 

2.2 层次遍历

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

 那么我们怎么实现呢?

这里需要使用队列,让根节点先入堆,再出队,出队时让左右子树入堆,空树不进队,按照这个方式可以实现二叉树的层次遍历。

具体实现:这里队列相关函数要自己实现,C++就方便多了,以后会讲。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{//创建一个队列Queue q;//初始化队列QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}

3.节点个数相关函数实现

3.1 二叉树节点个数

=左子树的节点数+右子树的节点数+根节点数。根节点数为1。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

3.2 二叉树叶子节点个数

=左子树的叶子节点数+右子树的叶子节点数。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->right == NULL && root->left == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3.3 二叉树第k层节点个数

=左子树的K-1层节点数+右子树的K-1层节点数。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

3.4 在二叉树中查找值为x的节点

=根节点不是,就在左子树和右子树中寻找

//在二叉树中查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left, x);BTNode* right = BinaryTreeFind(root->right, x);return left == NULL ? right : left;
}

4.二叉树基础oj练习

  1. 单值二叉树。OJ链接
  2. 检查两颗树是否相同。OJ链接
  3. 对称二叉树。OJ链接
  4. 二叉树的前序遍历。OJ链接
  5. 二叉树中序遍历。OJ链接
  6. 二叉树的后序遍历。OJ链接
  7. 另一颗树的子树。OJ链接

5.二叉树的创建和销毁

二叉树的构建及遍历。OJ链接

5.1 通过前序遍历构建二叉树

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树,'#'代表空。

代码实现:

//开辟树节点空间
BTNode* BuyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
//构建树
BTNode* CreatTree(char* arr,int*i)
{if(arr[*i] =='#'){(*i)++;return NULL;}BTNode* node = BuyNode(arr[*i]);(*i)++;node->left = CreatTree(arr,i);node->right = CreatTree(arr,i);return node;
}int main() 
{char arr[] = "ABD##E#H##CF##G##";int i = 0;//传递下标的地址,这样就可以通过地址修改下标。BTNode* tree = CreatTree(arr, &i);return 0;
}

5.2 销毁二叉树

这里是后序思想,先释放左右子树,最后释放根节点。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right)); free(*root);*root = NULL;
}

5.3 判断二叉树是否为完全二叉树

这里也是通过队列进行判断,之前层次遍历空树不进队,而这里空树进队,当出队时遇到空时,停止出队,判断队列中是否有非空,如果有就不是完全二叉树

代码实现:

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front != NULL){QueuePop(&q);QueuePush(&q, front->left);QueuePush(&q, front->right);}else{//遇到空就跳出break;}}//检查后面节点有没有非空//有非空就不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL) return 0;//不是}return 1;//是
}

本篇结束!

相关文章:

【数据结构】二叉树 链式结构的相关问题

本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3…...

【无标题】云原生在工业互联网的落地及好处!

什么是工业互联网? 工业互联网(Industrial Internet)是新一代信息通信技术与工业经济深度融合的新型基础设施、应用模式和工业生态,通过对人、机、物、系统等的全面连接,构建起覆盖全产业链、全价值链的全新制造和服务…...

人工智能在心电信号分类中的应用

目录 1 引言 2 传统机器学习中的特征提取与选择 3 深度学习中的特征提取与选择...

【Linux 网络】网络层协议之IP协议

IP协议 IP协议所处的位置网络层要解决的问题IP协议格式分片与组装网段划分特殊的IP地址IP地址的数量限制私网IP地址和公网IP地址路由 IP协议所处的位置 IP指网际互连协议,Internet Protocol的缩写,是TCP/IP体系中的网络层协议。 网络层要解决的问题 网络…...

.meta 文件

.meta 文件的作用简单来说是建立 Unity 与资源之间的“桥梁”。 在游戏中引用一个游戏资源,Unity 并不是直接按照文件的路径或者名称,而是使用一个独一无二的 GUID 来指向工程里该资源文件。 这个 GUID 就是存储在 Unity 工程为每一个资源和文件…...

CRITICAL_SECTION 用法

#include <stdio.h> #include <windows.h> typedef RTL_CRITICAL_SECTION CRITICAL_SECTION; CRITICAL_SECTION g_cs; //声明关键段 // 共享资源 char g_cArray[10]; unsigned int g_Count 0; DWORD WINAPI ThreadProc10(LPVOID pParam) { // 进入临界区 …...

汇川运动控制产品故障排查

针对汇川伺服产品&#xff08;IS600/IS620&#xff09;的基本检测和一些出现频率较高的故障进行检测判断方法&#xff0c;适用于服务人员在现场排查/判断机器故障时&#xff0c;准确定位问题。 一、简单故障排查 注1&#xff1a;接线错误&#xff1a;1、UVW相序是否正确&#…...

【Groups】50 Matplotlib Visualizations, Python实现,源码可复现

详情请参考博客: Top 50 matplotlib Visualizations 因编译更新问题&#xff0c;本文将稍作更改&#xff0c;以便能够顺利运行。 1 Dendrogram 树状图根据给定的距离度量将相似的点组合在一起&#xff0c;并根据点的相似性将它们组织成树状的链接。 新建文件Dendrogram.py: …...

windows安装kafka配置SASL-PLAIN安全认证

目录 1.Windows安装zookeeper&#xff1a; 1.1下载zookeeper 1.2 解压之后如图二 1.3创建日志文件 1.4复制 “zoo_sample.cfg” 文件 1.5更改 “zoo.cfg” 配置 1.6新建zk_server_jaas.conf 1.7修改zkEnv.cmd 1.8导入相关jar 1.9以上配置就配好啦&#xff0c;接下来启…...

【Linux】五种IO模型

文章目录 1. IO基本概念2. 五种IO模型2.1 五个钓鱼的例子2.2 五种IO模型2.2.1 阻塞IO2.2.2 非阻塞IO2.2.3 信号驱动IO2.2.4 IO多路转接2.2.5 异步IO 1. IO基本概念 认识IO IO就是输入和输出&#xff0c;在冯诺依曼体系结构中&#xff0c;将数据从输入设备拷贝到内存就叫输入&am…...

SCT82A30DHKR_5.5V-100V Vin同步降压控制器

SCT82A30是一款100V电压模式控制同步降压控制器&#xff0c;具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比&#xff0c;实现从48V输入到低压轨的直接降压转换&#xff0c;降低了系统复杂性和解决方案成本。如果需要&#xff0c;在低至6V的输入电压下降期间&am…...

备忘录模式(C++)

定义 在不破坏封装性的前提下&#xff0c;捕获一-个对象的内部状态&#xff0c;并在该对象之外保存这个状态。这样以后就可以将该对象恢复到原先保存的状态。 应用场景 ➢在软件构建过程中&#xff0c;某些对象的状态在转换过程中&#xff0c;可能由于某种需要&#xff0c;要…...

二叉排序树(二叉查找树)

二叉排序树&#xff08;二叉查找树&#xff09;的性质&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有结点的值均小于它的根结点的值。若它的右子树不为空&#xff0c;则右子树上所有结点的值均大于它的根将诶点的值。它的左、右子树也分别为二叉排序树。 对二叉…...

Python简单应用VII

题目 编程实现下述各题。 1.使用异常处理结构捕获多种可能的异常&#xff0c;如列表下标索引越界异常(IndexError)、试 图访问一个系统对象没有的属性所发生的异常(AttributeError)、读一个文件但该文件不存在。 2. 新建并打开文件stud1.txt&#xff0c;如果文件已存在就提示“…...

mysql--InnoDB存储引擎--架构和事务

MySQL进阶篇 文章目录 架构1、逻辑结构InnoDB 逻辑存储单元主层级关系图&#xff1a;1、表空间2、段3、区4、页5、行总结&#xff1a; 2、架构2、1 内存架构2、2 磁盘架构 3、事务3、1事务基础&#xff08;1&#xff09;事务&#xff08;2&#xff09;特性 架构 1、逻辑结构 I…...

0基础学习VR全景平台篇 第79篇:全景相机-泰科易如何直播推流

泰科易科技是中国的一家研发全景相机的高科技公司&#xff0c;前不久&#xff0c;在2020世界VR产业大会上发布了新一代5G VR直播影像采集终端--360starlight。以其出色的夜景成像效果和一“部”到位的直播方案重新定义了VR慢直播相机&#xff0c;对行业具有高度借鉴意义。 本文…...

代码调试4:实现退化模型的训练

代码调试:实现退化模型的训练 作者:安静到无声 个人主页 目录 代码调试:实现退化模型的训练问题1:如何在coco原始编码的基础上修改原始的文件?**方法1**:修改生成的文件**方法2**:直接修改源文件`instances_train2014.json`和`instances_val2014.json`问题2:构建退化后…...

8.7工作总结

一、我们想自定义一个titileBar出现如下这种情况&#xff0c;发现他原来的titileBar还未隐藏。 后来我尝试修改主题使得他没有主题noActionBar发现也不行&#xff0c;后来我参考原先我看过的项目使用了如下代码 this.getActionBar().hide();发现会报这个错误java.lang.NullPoi…...

数据库的约束 详解

一、约束的概述 1.概念:约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。 2&#xff0e;目的:保证数据库中数据的正确、有效性和完整性。 3.分类: 约束描述关键字非空约束限制该字段的数据不能为nullNOT NULL唯一约束保证该字段的所有数据都是唯一、不…...

Tomcat 编程式启动 JMX 监控

通过这篇文章&#xff0c;我们可以了解到&#xff0c;利用 JMX 技术可以方便获取 Tomcat 监控情况。但是我们采用自研的框架而非大家常见的 SpringBoot&#xff0c;于是就不能方便地通过设置配置开启 Tomcat 的 JMX&#xff0c;——尽管我们也是基于 Tomcat 的 Web 容器&#x…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...