深入理解数据结构第三弹——二叉树（3）——二叉树的基本结构与操作

二叉树（1）：深入理解数据结构第一弹——二叉树（1）——堆-CSDN博客

二叉树（2）：深入理解数据结构第二弹——二叉树（2）——堆排序及其时间复杂度-CSDN博客

前言：

在前面我们讲了堆及其应用，帮助我们初步了解了二叉树的一些原理，但那与真正的二叉树仍有不同，今天我们就来正式学习一下二叉树的基本结构及其基本操作

目录

一、什么是二叉树？

二、二叉树的节点结构

三、二叉树的遍历

前序遍历：

中序遍历：

后序遍历：

四、二叉树的基本操作

1、创建二叉树

2、前序、中序、后序

3、求二叉树的节点个数

4、求二叉树叶子节点的个数

5、树的高度

6、二叉树第k层的节点个数

7、二叉树查找值为x的节点

五、完整代码实例

总结

一、什么是二叉树？

在前面的文章中我们已经提到过二叉树的结构及其特点，这里我们不过多赘述，有不理解的可以点文章开头的链接去前面看一下

二、二叉树的节点结构

二叉树有左右子树之分，且二叉树与我们所学的其他数据结构不同的点在于，之前我们所学的都是各类插入或者删除等等，但是二叉树需要做的操作是运用递归遍历，所以二叉树的节点结构与之前几个有很大不同

typedef int TreeDataType;
typedef struct Tree
{
	TreeDataType a;
	struct Tree* left;
	struct Tree* right;
}Tree;

节点结构里面定义有两个递归，是为了方便后面的遍历

三、二叉树的遍历

二叉树的遍历是我们学习二叉树首先要了解的东西，我们都知道二叉树其实就是一串数组，那我们是如何访问他们的呢？这里就牵扯到了遍历顺序的问题。

二叉树的遍历有三种形式：前序、中序和后序

  1. 前序遍历：

    • 特点：按照“根-左-右”的顺序遍历二叉树。
    • 特点：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
    • 应用：常用于复制一棵树、计算表达式的值等。

  2. 中序遍历：

    • 特点：按照“左-根-右”的顺序遍历二叉树。
    • 特点：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
    • 应用：常用于二叉搜索树，可以得到一个递增的有序序列。

  3. 后序遍历：

    • 特点：按照“左-右-根”的顺序遍历二叉树。
    • 特点：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
    • 应用：常用于释放二叉树的内存空间，或者计算表达式的值。

    例如：

四、二叉树的基本操作

我先把主函数给出，接下来就将按照主函数中的这些功能一步一步来实现

int main()
{
	Tree* root = CreatTree();
	//前序
	printf("前序：");
	PrevTree(root);
	printf("\n");
	//中序
	printf("中序：");
	HalfTree(root);
	printf("\n");
	//后序
	printf("后序：");
	PostTree(root);
	printf("\n");
	//节点个数
	int count = BTreeSize(root);
	printf("BTreeSize:%d\n", count);
	//叶子节点个数
	printf("BTreeLeafSize:%d\n", BTreeLeafSize(root));
	//树的高度
	printf("BTreeHigh:%d\n", BTreeHigh(root));
	//二叉树第k层节点个数
	printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3));
	//二叉树查找值为x的节点
	

    return 0;
}

1、创建二叉树

//二叉树
typedef int TreeDataType;
typedef struct Tree
{
	TreeDataType a;
	struct Tree* left;
	struct Tree* right;
}Tree;
//初始化二叉树
Tree* TreeInit(TreeDataType x)
{
	Tree* m = (Tree*)malloc(sizeof(Tree));
	if (m == NULL)
	{
		perror("TreeInit");
		return NULL;
	}
	m->a = x;
	m->left = NULL;
	m->right = NULL;
	return m;
}
//创建一个二叉树
Tree* CreatTree()
{
	Tree* n1 = TreeInit(3);
	Tree* n2 = TreeInit(5);
	Tree* n3 = TreeInit(6);
	Tree* n4 = TreeInit(7);
	Tree* n5 = TreeInit(9);

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;

	return n1;
}

2、前序、中序、后序

前序、中序和后序其实就是数据按照上面图片中的形式进行遍历

//前序
void PrevTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->a);
	PrevTree(root->left);
	PrevTree(root->right);
}
//中序
void HalfTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	HalfTree(root->left);
	printf("%d ", root->a);
	HalfTree(root->right);
}
//后序
void PostTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostTree(root->left);
	PostTree(root->right);
	printf("%d ", root->a);
}

运行结果：

3、求二叉树的节点个数

//二叉树节点个数
int BTreeSize(Tree* root)
{
	//分治的思想
	if (root == NULL)
	{
		return 0;
	}
	return BTreeSize(root->left) + BTreeSize(root->right)+1 ;
}

用到了递归的思想，下面的内容都要用递归来解决，如果递归学的不太好建议画图来看这些过程如何进行的

运行结果：

4、求二叉树叶子节点的个数

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

运行结果：

5、树的高度

//求二叉树高度
int BTreeHigh(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHigh = BTreeHigh(root->left);
	int rightHigh = BTreeHigh(root->right);

	return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}

运行结果：

6、二叉树第k层的节点个数

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

运行结果：

7、二叉树查找值为x的节点

//二叉树查找值为x的节点
Tree* BTreeFind(Tree* root,int x)
{
	if (root == NULL)
		return NULL;
	if (root->a == x)
		return root;
	Tree* ret1 = BTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	Tree* ret2 = BTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
}

五、完整代码实例

//二叉树
typedef int TreeDataType;
typedef struct Tree
{
	TreeDataType a;
	struct Tree* left;
	struct Tree* right;
}Tree;
//初始化二叉树
Tree* TreeInit(TreeDataType x)
{
	Tree* m = (Tree*)malloc(sizeof(Tree));
	if (m == NULL)
	{
		perror("TreeInit");
		return NULL;
	}
	m->a = x;
	m->left = NULL;
	m->right = NULL;
	return m;
}
//创建一个二叉树
Tree* CreatTree()
{
	Tree* n1 = TreeInit(3);
	Tree* n2 = TreeInit(5);
	Tree* n3 = TreeInit(6);
	Tree* n4 = TreeInit(7);
	Tree* n5 = TreeInit(9);

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;

	return n1;
}
//前序
void PrevTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->a);
	PrevTree(root->left);
	PrevTree(root->right);
}
//中序
void HalfTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	HalfTree(root->left);
	printf("%d ", root->a);
	HalfTree(root->right);
}
//后序
void PostTree(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostTree(root->left);
	PostTree(root->right);
	printf("%d ", root->a);
}
//二叉树节点个数
int BTreeSize(Tree* root)
{
	//分治的思想
	if (root == NULL)
	{
		return 0;
	}
	return BTreeSize(root->left) + BTreeSize(root->right)+1 ;
}
//二叉树叶子节点个数
int BTreeLeafSize(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
//求二叉树高度
int BTreeHigh(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHigh = BTreeHigh(root->left);
	int rightHigh = BTreeHigh(root->right);

	return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}
//二叉树第k层节点个数
int BTreeLevelKSize(Tree* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
//二叉树查找值为x的节点
Tree* BTreeFind(Tree* root,int x)
{
	if (root == NULL)
		return NULL;
	if (root->a == x)
		return root;
	Tree* ret1 = BTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	Tree* ret2 = BTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
}
int main()
{
	Tree* root = CreatTree();
	//前序
	printf("前序：");
	PrevTree(root);
	printf("\n");
	//中序
	printf("中序：");
	HalfTree(root);
	printf("\n");
	//后序
	printf("后序：");
	PostTree(root);
	printf("\n");
	//节点个数
	int count = BTreeSize(root);
	printf("BTreeSize:%d\n", count);
	//叶子节点个数
	printf("BTreeLeafSize:%d\n", BTreeLeafSize(root));
	//树的高度
	printf("BTreeHigh:%d\n", BTreeHigh(root));
	//二叉树第k层节点个数
	printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3));
	//二叉树查找值为x的节点
	

    return 0;
}

运行结果：

总结

总而言之，二叉树其实是对我们运用递归来遍历数据的考察，由于篇幅原因，这里我们只对二叉树的结构进行了大致的讲解，有不理解的地方欢迎与我私信或者在评论区中指出

创作不易，还请各位大佬点个小小的赞！！！

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

前端学习之DOM编程案例：全选反选案例

前端学习之DOM编程案例：全选反选案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>全选反选</title> </head> <body><input type"checkbox" id"all">全选<ul><li><…
阅读更多...
File，IO流，递归详解

File，IO流，递归详解

File类 介绍 java.io.File类是Java语言提供了用来描述文件和目录(文件夹)的 构造 方法 注意&#xff1a; 构造方法中通常用的是第一个方法文件和目录可以通过File封装成对象File封装的对象仅仅是一个路径名&#xff0c;它是可以存在的&#xff0c;也可以不存在 绝对路径…
阅读更多...
linux 安装JDK

linux 安装JDK

一、安装jdk mkdir -p /export/servers # 软件安装的目录 0 . 使用rpm -qa | grep java 查看是否已经安装了jdk 使用: rpm -e --nodeps 软件的名称 将jdk进行卸载 执行完成后, 查看是否全部删除: 需要解压jdk的压缩包 tar -zxvf jdk-8u144-linux-x64.tar.gz -C /export/s…
阅读更多...
Tcl学习笔记(二)——表达式、字符串

Tcl学习笔记(二)——表达式、字符串

目录 1. 表达式 算数操作符 关系操作符 逻辑操作符 按位操作符 选择操作符 数学函数 字符串操作 2. 字符串 字符串长度、大小写转换、裁剪、重复 字符串类型 字符的获取 字符串的添加、删除、替换 字符串的比较 字符串的简单搜索 字符串的匹配 格式化…
阅读更多...
计算机网络 实验指导 实验9

计算机网络 实验指导 实验9

实验9 三层交换机综合实验 1.实验拓扑图 名称相连的接口IP地址网关PC1F0/3172.1.1.2/28172.1.1.1/28PC2F0/4172.1.1.18/28172.1.1.17/28PC3F0/5172.1.1.34/28172.1.1.33/28PC4F0/3172.1.1.3/28172.1.1.1/28PC5F0/4172.1.1.19/28172.1.1.17/28PC6F0/5172.1.1.35/28172.1.1.33/2…
阅读更多...
学习天机04（优惠劵）

学习天机04（优惠劵）

1.使用Redis和Mq优化领取优惠卷的高并发操作 实现思路&#xff1a; 因为领取优惠券的操作&#xff0c;涉及到操作db的操作很多&#xff0c;比如说查询优惠卷&#xff0c;统计已经领取的数量&#xff0c;更新已经发放的数量和新增用户券。所以了防止在高并发的情况下对我们的数…
阅读更多...
如何查询大数据信用报告？查询时需要注意的事项有哪些？

如何查询大数据信用报告？查询时需要注意的事项有哪些？

在数字化时代&#xff0c;大数据信用评分对于需要资金周转的个人或企业来说至关重要。许多机构在贷款审批过程中使用大数据信用评分作为风险控制的重要手段。因此&#xff0c;了解自己的大数据信用状况成为了常规操作。本文将详细介绍如何查询大数据信用报告以及查询时需要注意…
阅读更多...
物联网实战--入门篇之(十一)安卓QT--前端开发

物联网实战--入门篇之(十一)安卓QT--前端开发

目录 一、设计思路 二、QML文件结构 三、顶部框 四、中心圆圈 五、泡泡 六、开关栏 七、调速栏 八、安卓编译 一、设计思路 还是再贴一下米家APP的截图&#xff0c;再根据我们之前第九篇的分析&#xff0c;大概可以得出设计思路了。首先一个根页面当底版&#xff0c;然…
阅读更多...
SpringBoot属性配置的多种方式

SpringBoot属性配置的多种方式

✅作者简介：大家好，我是Leo，热爱Java后端开发者，一个想要与大家共同进步的男人😉😉🍎个人主页：Leo的博客💞当前专栏： 循序渐进学SpringBoot ✨特色专栏： MySQL学习 🥭本文内容：SpringBoot属性配置的多种方式 📚个人知识库： Leo知识库，欢迎大家访问 目录 …
阅读更多...
突破编程_前端_SVG（概述）

突破编程_前端_SVG（概述）

1 什么是 SVG SVG&#xff0c;全称可缩放矢量图形&#xff08;Scalable Vector Graphics&#xff09;&#xff0c;是一种基于 XML&#xff08;可扩展标记语言&#xff09;的矢量图像格式。这种图像格式的主要特点是它描述的是矢量图形&#xff0c;而不是基于像素的位图图像。因…
阅读更多...
接口和抽象类的综合案例

接口和抽象类的综合案例

题目要求&#xff1a; 代码框架&#xff1a; 代码实现&#xff1a; person类&#xff1a; package www.jsu.com;public class Person {private String name;private int age;public Person() {}public Person(String name, int age) {this.name name;this.age age;}public …
阅读更多...
【第十二篇】使用BurpSuite实现CSRF（实战案例）

【第十二篇】使用BurpSuite实现CSRF（实战案例）

CSRF存在前提：简单的身份验证只能保证请求是发自某个用户的浏览器，却不能保证请求本身是用户自愿发出的 业务场景：新增、删除、收藏、编辑、保存使用Burp发现CSRF漏洞的过程如下。 1、如图，存在修改邮箱的功能点如下： 2、修改邮箱的流量包，此时邮箱已被修改： 思路：是…
阅读更多...
Labview如何0基础自学快速入门？(纯干货帖)

Labview如何0基础自学快速入门？(纯干货帖)

大家好&#xff0c;首先声明&#xff1a;本文纯干货&#xff0c;单纯为了帮助大家快速入门。有用的话大家点赞评论加关注即可。谢谢大家 题主是从一个毫无编程基础的Labview小白到现在能独立承担软件开发项目的工程师&#xff0c;作为瑞文的老玩家&#xff0c;题主觉得&#xf…
阅读更多...
Git场景运用

Git场景运用

git 脚本在开发中应用场景-CSDN博客 Git基础 Git基本运作流程 ​​​​​​​ (1) workspace->index->Repository ​ 本地写代码在workspace&#xff0c;add暂存到index&#xff0c;commit提交到本地Repository。多项目成员&#xff0c;每员对应本地仓库&#xff0c;各自…
阅读更多...
uniapp-设置UrlSchemes从外部浏览器H5打开app

uniapp-设置UrlSchemes从外部浏览器H5打开app

需求&#xff1a;外部浏览器H5页面&#xff0c;跳转到uniapp开发的原生app内部。 1、uniapp内部的配置&#xff1a; &#xff08;1&#xff09;打开manifest->App常用其他设置&#xff0c;如下&#xff0c;按照提示输入您要设置的urlSchemes&#xff1a; &#xff08;2&am…
阅读更多...
pom.xml文件中的标签认识

pom.xml文件中的标签认识

周末不卷&#xff0c;研究下pom.xml里的内容。 一般一个pom.xml文件外面一个project包着以下的标签&#xff1a; groupId artifactId repositories properties dependencies build plugins 下面分别来说说这几个标签的含义&#xff1a; 1、groupId&#xff1a;表示项目组的id…
阅读更多...
MSOLSpray：一款针对微软在线账号（AzureO365）的密码喷射与安全测试工具

MSOLSpray：一款针对微软在线账号（AzureO365）的密码喷射与安全测试工具

关于MSOLSpray MSOLSpray是一款针对微软在线账号&#xff08;Azure/O365&#xff09;的密码喷射与安全测试工具&#xff0c;在该工具的帮助下&#xff0c;广大研究人员可以直接对目标账户执行安全检测。支持检测的内容包括目标账号凭证是否有效、账号是否启用了MFA、租户账号是…
阅读更多...
vivado 系统内逻辑设计调试流程

vivado 系统内逻辑设计调试流程

系统内逻辑设计调试流程 Vivado 工具提供了诸多功能 &#xff0c; 用于在真实硬件器件中调试系统内设计。系统内调试流程包含 3 个不同阶段 &#xff1a; 1. 探测阶段 &#xff1a; 确定设计中要探测的信号和探测的方法。 2. 实现阶段 &#xff1a; 完成设计实现 &…
阅读更多...
Java学习笔记24（面向对象编程（高级））

Java学习笔记24（面向对象编程（高级））

1.面向对象编程(高级) 1.1 类变量和类方法 1.类变量 ​ *类变量也叫静态变量/静态属性&#xff0c;是该类的所有对象共享的变量&#xff0c;任何一个该类的对象去访问它时&#xff0c;取到的都是相同的值&#xff0c;同样任何一个该类的对象去修改它时&#xff0c;修改的也是…
阅读更多...
31.2k star, 免费开源的白板绘图工具 tldraw

31.2k star, 免费开源的白板绘图工具 tldraw

31.2k star, 免费开源的白板绘图工具 tldraw 分类 开源分享 项目名: tldraw -- 无限画布白板 Github 开源地址&#xff1a; https://github.com/tldraw/tldraw 在线测试地址&#xff1a; tldraw 文档地址&#xff1a; tldraw SDK tldraw 是一款开源免费的无限画布白板&…
阅读更多...
最新文章

Copyright @ 2022~2023