初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）

引言

本篇博客是初阶数据结构树的收尾，将会讲掉基本二叉树链式结构的具体内容和实现，包括二叉树的构建，前序遍历，中序遍历，后序遍历和层序遍历，计算二叉树结点个数，第k层结点个数，二叉树叶子结点个数，以及判断一个二叉树是否为完全二叉树。话不多说，开始我们今天的内容。

二叉树链式结构

在之前的博客中，已经讲到了关于链式二叉树相关定义的内容。

这里我们可以来看一看关于二叉树结点的定义：

typedef char BTDataType;//定义存储数据类型

typedef struct BinaryTreeNode
{
	BTDataType _data; //存储数据
	struct BinaryTreeNode* _left; //指向左孩子（左子树）
	struct BinaryTreeNode* _right; //指向右孩子（右子树）
}BTNode;

二叉树：

1. 空树

2. 非空树：由根结点，根节点的左子树，根节点的右子树组成。

从概念上可以看出，二叉树是递归定义的，后面对二叉树的构建和遍历操作都是围绕递归的思路展开。

二叉树的遍历方式及实现

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

按照不同的遍历规则，二叉树的遍历方式有四种：前序遍历，中序遍历，后序遍历和层序遍历

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

这三种遍历方式大同小异，层序遍历放到后面单独再讲。

下面仔细讲下前序遍历，弄懂前序遍历，中序和后序也就没什么难度了。

1.前序遍历

前序遍历：访问根结点的操作发生在遍历其左右子树之前。

前序遍历图解：

对于上面这棵二叉树：

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

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

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

层序遍历结果：1 2 4 3 N 5 6 N N N N N N

代码实现：

打印结点操作在遍历左右子树之前。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left); //递归到左子树
	BinaryTreePrevOrder(root->_right); //递归到右子树
}

2.中序遍历

中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）。

代码实现：
与前序很相似，不过打印结点操作在遍历完左子树之后。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	BinaryTreeInOrder(root->_left); //遍历左子树
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right); //遍历右子树
}

3.后续遍历

后序遍历：访问根结点的操作发生在遍历其左右子树之后。

代码实现：

与前序遍历相似，不过打印结点操作在遍历完左右子树之后。

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)return; //遇到NULL结点返回
	BinaryTreePostOrder(root->_left); //遍历左子树
	BinaryTreePostOrder(root->_right); //遍历右子树
	printf("%c ", root->_data);
}

4.层序遍历

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

二叉树层序遍历的实现，需要借助之前讲过的一个数据结构——队列。

在使用队列之前，需要知道队列中存放的是什么内容，对于二叉树的结点来说，存放的应该是指向二叉树结点的指针：

// 链式结构：表示队列 
typedef BTNode* QDataType;
//队列的一个结点
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;//队列元素个数
}Queue;

看一下实现代码，这里直接复用队列的内容：

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail:");
		exit(1);
	}
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_front == NULL) {
		q->_front = newnode;
		q->_rear = newnode;
	}
	else {
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front);
	if (q->size == 1) {
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else {
		QNode* pnext = q->_front->_next;
		free(q->_front);
		q->_front = pnext;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	if (q->_front == NULL)return;
	if (q->size == 1) {
		free(q->_front);
	}
	else {
		while (q->_front) {
			QNode* pnext = q->_front->_next;
			free(q->_front);
			q->_front = pnext;
		}
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu; //创建一个队列
	QueueInit(&qu); //初始化队列
	if (root)QueuePush(&qu, root); //判断树是否为空树
	while (!QueueEmpty(&qu)) { //结束条件：队列为空
		BTNode* front = QueueFront(&qu); //取出队列中首元素
		QueuePop(&qu); //删除队首元素
		printf("%c ", front->_data); //打印遍历到的结点数据
        //将下一层结点放入队列中
		if (front->_left)QueuePush(&qu, front->_left);
		if (front->_right)QueuePush(&qu, front->_right);
	}
	printf("\n");
	QueueDestroy(&qu);//销毁队列
}

层序遍历规则：

  1. 根节点的指针入队列。
  2. 队列非空，队列中首元素出队，将队列下一层元素带入队尾（如果元素为NULL则不入队）。
  3. 如果队列为空，循环停止，遍历结束。

关于结点数和查找

计算二叉树结点个数

把二叉树递归遍历一遍就可以得到结点个数，每层结点递归时都加一。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)return 0;
    //return中遍历了整个二叉树，很像递归方式求斐波那契数
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

计算叶子结点个数

也是需要遍历一遍二叉树，但是需要满足叶子结点条件（左右孩子都为NULL）的时候才会return 1计数。

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

计算二叉树第k层结点个数

底层逻辑依然是遍历二叉树，这里计算第k层结点个数的关键点是通过控制每层递归传入的k值判断当前结点所在层数。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)return 0;
	else if (k == 1)return 1;//当k==1时说明此处遍历的结点已经是第k层
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

二叉树查找值为x的结点

查找的逻辑依然是遍历二叉树。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)return NULL;
	else if (root->_data == x)return root;
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)return ret1; //如果左子树找到（不为NULL），直接返回，否则返回右子树
	return BinaryTreeFind(root->_right, x);
}

二叉树的创建和销毁

二叉树的创建（前序遍历）

此处讲的二叉树创建，是以一个所给的前序遍历数组为基础（如："ABD##E#H##CF##G##"）创建的。其实创建过程的本质还是递归结构。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert(*pi <= n);
	if (a[*pi] == '#') {
		(*pi)++;
		return NULL;
	}
    //开辟结点空间
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) { //判断空间是否开辟成功
		perror("malloc fail:");
		exit(1);
	}
	root->_data = a[(*pi)++];
    //递归构建左右子树
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

二叉树的销毁

二叉树的销毁更适合基于后序遍历，从下往上依次销毁。这里并不是说前序和中序遍历无法实现销毁这一过程，只是用这两种结构实现会将问题复杂化——前中序遍历在销毁根节点后很难在找到左右孩子结点继续进行递归销毁，而后续遍历却可以规避这个问题：因为在删除根节点之前左右子树及其结点已被释放无需递归删除。

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

上述代码传递二级指针是为了方便根节点指针置空，传一级指针在函数外部置空也是一种可行的解决方式。

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

判断一个二叉树是否为完全二叉树，可以使用之前讲到的层序遍历的思想。

完全二叉树：除了最后一层，其他每一层结点都是完全填满的，且最后一层所有结点都集中在左侧。层序遍历的过程中，如果遇到了一个结点，其无左子树而有右子树，那么这棵树肯定不是完全二叉树；另外，如果遇到了一个结点并非左右子结点都有，那么所有接下来遍历到的结点都必须是叶子节点。

我们可以在原有的层序遍历代码上修改：
这里就不再粘贴一遍队列的代码了

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	QueueInit(&qu);
	if (root)QueuePush(&qu, root);
	while (!QueueEmpty(&qu)) {
		BTNode* front = QueueFront(&qu);
		QueuePop(&qu);
		if (front == NULL)break;//如果队列中出现空结点跳出循环，进行下一步判断
        //通过push将下一层结点带入队列
		QueuePush(&qu, front->_left);
		QueuePush(&qu, front->_right);
	}
	while (!QueueEmpty(&qu)) {
		BTNode* front = QueueFront(&qu);
		QueuePop(&qu);
        //如果出现非空结点则证明不是完全二叉树
		if (front) {
			QueueDestroy(&qu);
			return false;
		}
	}
	QueueDestroy(&qu);
    //如果正常跳出循环则证明为完全二叉树
	return true;
}

上述代码的主要判断逻辑是，当队列中出现一个空结点时，判断此时队列中剩余结点是否都为空：如果队列中剩余结点都为空则证明是完全二叉树；如果存在非空结点则证明不是完全二叉树。

具体代码演示

这里来测试一下之前所写的二叉树的接口函数：

int main()
{
	char arr[] = "ABD##E#H##CF##G##";
	int i = 0;
	BTNode* treeroot = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]), &i);
	printf("结点个数：%d\n", BinaryTreeSize(treeroot));
	printf("叶子结点个数：%d\n", BinaryTreeLeafSize(treeroot));
	int k;
    printf("输入计算第几层的结点个数：");
	scanf("%d", &k);
	printf("第k层结点个数： % d\n", BinaryTreeLevelKSize(treeroot, k));
	BTNode* node = BinaryTreeFind(treeroot, 'C');
	printf("%c\n", node->_data);
	printf("二叉树前序遍历：");
	BinaryTreePrevOrder(treeroot);
	printf("\n");
	printf("二叉树中序遍历：");
	BinaryTreeInOrder(treeroot);
	printf("\n");
	printf("二叉树后序遍历：");
	BinaryTreePostOrder(treeroot);
	printf("\n");
	printf("二叉树层序遍历：");
	BinaryTreeLevelOrder(treeroot);
	printf("是否为完全二叉树：%d",BinaryTreeComplete(treeroot));
	BinaryTreeDestory(&treeroot);
	return 0;
}

下面是所创建树的结构： 

 

下面是运行结果： 

结语

关于二叉树链式结构的内容到这里就结束了。本篇博客围绕二叉树的遍历，结点个数计算以及数值查找等内容展开。关于二叉树更多有趣的内容还远远不止这些，不过再次深入时就会以C++的方式来给大家呈现，如果对后续内容感兴趣的话，还请大家多多关注博主，感谢大家的支持。

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

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

相关文章

为什么高铁提前三分钟停止检票？

为什么高铁提前三分钟停止检票？

为什么高铁提前三分钟停止检票&#xff1f; 高铁&#xff0c;作为现代交通方式的代表&#xff0c;以其高速、便捷、舒适的特点受到了广大乘客的青睐。然而&#xff0c;在乘坐高铁的过程中&#xff0c;乘客们可能会遇到一个问题&#xff1a;为什么高铁会提前三分钟停止检票呢&a…
阅读更多...
Vue.js+SpringBoot开发服装店库存管理系统

Vue.js+SpringBoot开发服装店库存管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 角色管理模块2.3 服装档案模块2.4 服装入库模块2.5 服装出库模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 角色表3.2.2 服装档案表3.2.3 服装入库表3.2.4 服装出库表 四、系统展示五、核心代码5.…
阅读更多...
Redis 又双叒叕改开源协议了，微软提前推出高性能替代方案 Garnet

Redis 又双叒叕改开源协议了，微软提前推出高性能替代方案 Garnet

Redis 官宣&#xff1a;是的&#xff0c;我们又改开源协议了 3 月 20 号&#xff0c;Redis 商业公司 CEO Rowan Trollope 在公司官方博客上宣布了一项重大变革。Redis 核心软件将从 BSD 3-Clause 许可证过渡到双重许可证模式&#xff0c;这一变化将从 Redis v7.4 版本开始&…
阅读更多...
Java 应用程序监控

Java 应用程序监控

Java 监控涉及监控在 Java 上运行的应用程序的关键性能指标&#xff0c;以及 支持 Java 应用程序的服务器。Java 监控可以帮助优化 Java 应用程序的性能&#xff0c;发现和识别以下问题&#xff1a; 导致常见的应用程序问题&#xff0c;并在问题影响最终用户之前解决问题。 Ja…
阅读更多...
美联储3月会议来袭，市场对6月开启降息或仍较为乐观

美联储3月会议来袭，市场对6月开启降息或仍较为乐观

KlipC报道&#xff1a;美国联邦储备委员会结束了为期两天的货币政策会议&#xff0c;宣布仍继续将联邦基金利率目标区间维持在5.25%-5.50%之间不变。 值得一提的是会议声明声明几乎只字未改&#xff0c;唯一改动的是在描述就业市场时&#xff0c;将“新增就业过去一年有所放缓但…
阅读更多...
解决Oracle VM VirtualBox无法与Windows互相复制粘贴的教程

解决Oracle VM VirtualBox无法与Windows互相复制粘贴的教程

说明&#xff1a;要实现从Windows上复制然后在VM VirtualBox上粘贴&#xff0c;必须要在VM VirtualBox上下载virtualbox-guest-dkms 第一步&#xff1a; 第二步&#xff1a; 按CtrlALTT打开命令终端输入 sudo apt-get install virtualbox-guest-dkms 然后重启 第三步&…
阅读更多...
Linux下QT界面小程序开发

Linux下QT界面小程序开发

背景&#xff1a;需要在linux不同环境下可以测试我们的读卡器设备 搭建本地linux开发环境&#xff08;本来想VS里开发然后通过SSH的方式在linux下编译&#xff0c;但是工具链一直没搞起来&#xff0c;所以我是在ubuntu里安装的QT Creator工具直接开发的&#xff09;&#xff1b…
阅读更多...
（一）手把手教你如何通过ARM DesignStart计划在FPGA上搭建一个Cortex-M3软核

（一）手把手教你如何通过ARM DesignStart计划在FPGA上搭建一个Cortex-M3软核

&#xff08;一&#xff09;手把手教你如何通过ARM DesignStart计划在FPGA上搭建一个Cortex-M3软核 一、ARM DesignStart计划 1.1 如何下载ARM DesignStart Cortex-M3相关文件 ​ 关于ARM DesignStart计划的介绍:ARM DesignStart计划——私人定制一颗ARM处理器 - 知乎 (zhih…
阅读更多...
Android ViewPager不支持wrap_content的原因

Android ViewPager不支持wrap_content的原因

文章目录 Android ViewPager不支持wrap_content的原因问题源码分析解决 Android ViewPager不支持wrap_content的原因 问题 <androidx.viewpager.widget.ViewPagerandroid:id"id/wrap_view_pager"android:layout_width"match_parent"android:layout_he…
阅读更多...
快速画流程图

快速画流程图

使用在线工具&#xff1a;PlantUML PlantUML 官网:https://plantuml.com/ 中文官网:https://plantuml.com/zh/ 使用步骤如下&#xff1a; 1、拷贝一个完成函数&#xff1a; int func_init(const char *tag) {if (tag ! NULL) {printf("set TAG :%s", tag);}print…
阅读更多...
登录校验：JWT令牌、Filter、Interceptor

登录校验：JWT令牌、Filter、Interceptor

JWT&#xff1a; 全称&#xff1a;JSON Web Token 定义了一种简洁的、自包含的格式&#xff0c;用于在通信双方以json数据格式安全的传输信息&#xff0c;由于数字签名的存在&#xff0c;这些信息是可靠的。 组成&#xff1a; Header(头部)&#xff1a;&#xff08;“alg&q…
阅读更多...
每日学习笔记：C++ STL 的set、multiset

每日学习笔记：C++ STL 的set、multiset

定义 (自动排序&#xff0c;可指定自定义排序准则) 排序准则 特点 &#xff08;不同通过迭代器直接修改元素值&#xff0c;只能先删除后添加&#xff09; 操作函数 运行期指定排序准则
阅读更多...
【项目实践】VS配置Qt

【项目实践】VS配置Qt

文章目录 前言版本使用具体步骤1&#xff09;安装Qt或者添加删除组件2&#xff09;VS安装Qt Visual Studio Tools 如何使用遇到的问题双击ui文件编辑报错 前言 最近因为一个项目&#xff0c;需要使用Qt&#xff0c;本来想使用Python的&#xff0c;但是由于另外一个第三方的库是…
阅读更多...
Linux：vim编辑器的使用

Linux：vim编辑器的使用

1.Vim的安装 Linux默认是安装了的vim&#xff0c;未安装则可以使用以下指令安装。 yum install vim -y 2.Vim的四种模式 &#xff08;1&#xff09;命令模式 使用VIM编辑器时&#xff0c;默认处于命令模式。在该模式下可以移动光标位置&#xff0c;可以通过快捷键对文件内容…
阅读更多...
路灯单灯控制器 智慧路灯杆智能照明新宠

路灯单灯控制器 智慧路灯杆智能照明新宠

路灯单灯控制器是现代城市管理中非常重要的设备之一。它们不仅可以提供照明功能&#xff0c;还可以通过智能控制系统实现远程监控和调节。 　　路灯单灯控制器通过感知环境亮度和运行状态&#xff0c;实现对路灯的智能控制。它使用先进的传感器技术&#xff0c;能够实时感知路灯…
阅读更多...
von Mises-Fisher Distribution

von Mises-Fisher Distribution

1. 概率密度函数 关于 Bessel Function 请参阅《贝塞尔函数》《Modified Bessel Function of the First Kind》。 2. Relation to Normal Distribution 进一步的推导&#xff1a; G p ( x ; μ , κ ) ( κ 2 π ) p e x p ( − κ ( x − μ ) ⊺ ( x − μ ) 2 ) ( κ 2 π…
阅读更多...
109 项目整合 spring-quartz 启动自动执行定时任务

109 项目整合 spring-quartz 启动自动执行定时任务

前言 项目中使用了 quartz 来支持定时任务的相关基础支撑, 但是 最近添加了一个 资源消耗比较高的定时任务, 发布到测试环境之后, 发现服务突然 起不起来了[资源比较有限] 然后 查看了一下日志, 这个定时任务怎么在执行?, 不是 配置的是 凌晨两点么, 然后 仔细一看 几乎配置…
阅读更多...
跳槽多次未成功，问题源自何处？

跳槽多次未成功，问题源自何处？

众所周知&#xff0c;2023年市场很难&#xff01;看着企业们纷纷裁员&#xff0c;甚至连内推这个后门都走不通&#xff01;哪怕有面试&#xff0c;都是屡屡碰壁&#xff0c;你想清楚问题出在哪了吗&#xff1f;&#x1f62d;“求职不得&#xff0c;夜不能寐&#xff1b;三更半夜…
阅读更多...
免费升级https的方式（含教学）

免费升级https的方式（含教学）

背景&#xff1a;随着现在全民网络安全意识的日益提升&#xff0c;各个网站实现的https数量也随之提升&#xff0c;那么如何将原本网站的http访问方式升级为https呢&#xff1f;下面均为干货内容。 目录 http访问和https访问的区别&#xff1a; 实现https后有哪些好处&#x…
阅读更多...
两个现货白银理财产品投资技术分析方法

两个现货白银理财产品投资技术分析方法

现货白银是投资市场中比较受欢迎的理财产品。要投资现货白银&#xff0c;我们需要具备一定的金融投资经验。下面我们就来讨论一下&#xff0c;在现货白银这个理财产品的投资过程中&#xff0c;常常用到的一些技术分析方法。 宏观的趋势分析法。在现货白银理财产品投资中&#x…
阅读更多...
最新文章

Copyright @ 2022~2023