C数据结构：二叉树

目录

二叉树的数据结构

前序遍历

中序遍历

后序遍历

二叉树的创建

二叉树的销毁

二叉树的节点个数

二叉树叶子节点个数

二叉树第K层节点个数

二叉树的查找

层序遍历

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

完整代码

二叉树的数据结构

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

这里二叉树是使用了链式存储

data负责存储数据，left指针负责存储左孩子节点，right负责存储右孩子节点

前序遍历

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

前序遍历的规则是先访问根节点，然后访问左子树，最后访问右子树

根据规则我们在遍历前先打印当前根节点的值（若是遇到NULL则打印N代替空节点），然后再往下递归左子树、右子树即可 

中序遍历

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

中序遍历的规则是先访问左子树，然后访问根节点，最后访问右子树

 所以这里先递归到左子树（最左边），然后打印当前节点的值，然后再访问右子树（右子树的左子树），打印值，循环往复

后序遍历

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ", root->_data);
}

 后序遍历的规则是先访问左子树，然后访问右子树，最后访问根节点

跟前面的前序遍历和中序遍历基本一致，都只是顺序不一样

二叉树的创建

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi >= n)
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

使用该函数需要传一个数组，并根据数组里的元素当作前序遍历构建起二叉树

并需要传一个数组的大小，和一个标记pi，在外面传参的时候从数组开始的下标开始传

这里为了让函数在递归过程中能够始终有一个变量能够指向数组的某个元素来迭代（遍历数组），不受递归变化而变化，所以需要一个指针变量，在下一次递归的时候只需要传地址，就能获得*pi的值，而不是通过传参

 在每次递归过程中需要先创建一个根节点root并开辟一块空间，并为该节点data赋值为当前走到的*pi的位置

接下来就要开始递归先从根的左子树开始到右子树，并分别赋值给root的左和右

这里的递归会一直递归，我们需要让他递归到空为止，所以需要设定if语句限定递归次数

if语句限定了当*pi超过了数组的长度或等于数组长度时，则不能继续递归获取空间

所以这里是从最后一个节点开始往回返，先return最后一个节点给上一个递归的左或者右节点，依次往复即可

二叉树的销毁

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestory(root);
	BinaryTreeDestory(root);
	free(root);
}

销毁我们需要用后序遍历，因为前序和中序会先将根节点给销毁了，这样就不好往下找了，故此要使用后序遍历来一个个free掉每一个节点

二叉树的节点个数

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->_left)
		+ BinaryTreeSize(root->_right) + 1;
}

控制好递归的次数 

只需要在遍历每一层节点时+1，即可

二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->_left == NULL && root->_right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->_left) 
		+ BinaryTreeLeafSize(root->_right);
}

还是先控制递归的层数，当root等于空时往回返

若root的左和右都为空，则说明当前节点为叶子节点，返回1

最后返回左子树叶子节点和右子树叶子节点个数相加即可

二叉树第K层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->_left, k - 1) 
		+ BinaryTreeLevelKSize(root->_right, k - 1);
}

 和前面的递归思路都差不多

这里返回1的条件是k == 1，因为只需要递归k-1次即可，当递归次数达到说明也到了第k层，则返回1即可

最后返回给外层的时候把左右子树的结果返回起来相加即可

二叉树的查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->_data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
		return ret2;

	return NULL;
}

 第一个if语句控制层数

第二个判断查找结果，若找到则返回根节点root

找到的结果返回给下面的ret1指针或者ret2指针，通过这两个指针返回给最外层

层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->_data);

		if (front->_left)
			QueuePush(&q, front->_left);
		if (front->_right)
			QueuePush(&q, front->_right);
	}
	QueueDestroy(&q);
}

层序遍历是一层一层从左到右遍历，那么我们就需要借助队列来完成（先进先出）

例如该图层序遍历后就是1，2，4，3，5，6

首先我们需要将根节点入队列

然后进入循环，我们循环的条件是队列为空则停止循环

所以我们还需要不断入栈

这里第一层已经入栈了，这时候就可以拿到这个节点，我把它叫做front

后面我们就可以打印这个front节点的data

然后就可以删除掉这个节点了，但是删除的同时需要把它的左右孩子带进来，但是左右孩子有可能为空，所以先判断，若不为空则push入队列，这样第二层就入队列了

接下来继续pop2和4（pop的同时打印），然后push2和4的左右孩子

 最后不要忘记将队列销毁，防止造成内存泄漏

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

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
			break;

		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	QueueDestroy(&q);
	return 1;
}

和前面层序遍历差不多，我们也需要借用一个队列来完成该函数

先入第一个根节点进队列，然后循环的将二叉树的全部节点按照层序遍历都push进去 

push到最后队列的头节点front总会碰到空节点，所以我们碰到空节点就break出去循环，这是第一个循环的主要作用

例如该二叉树，我们push2的时候就会把左节点3和右节点NULL给入队列，那么我们的front肯定会接收到NULL从而跳出循环

如上并不是一个完全二叉树，所以我们判断它不是完全二叉树的理由就是根据层序遍历它的空节点后面还有一个节点6

所以我们第二个循环的任务就是pop掉队列剩下的所有值，若pop的时候发现里面还有非空节点，则不为完全二叉树，return 0

例如我们在把NULL节点接收给front时，我们肯定会经过4这个节点，然后4这个节点就会把它的左NULL和右6两个节点入队列

所以我们最后在把队列全部出掉的时候肯定会碰到这个6，既然碰到了这个6就说明这不是一个完全二叉树

完整代码

#include"BinaryTree.h"
#include"Queue.h"

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi >= n)
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	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);
	BinaryTreeDestory(root);
	free(root);
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->_left)
		+ BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->_left == NULL && root->_right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->_left) 
		+ BinaryTreeLeafSize(root->_right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->_left, k - 1) 
		+ BinaryTreeLevelKSize(root->_right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->_data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
		return ret2;

	return NULL;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->_data);

		if (front->_left)
			QueuePush(&q, front->_left);
		if (front->_right)
			QueuePush(&q, front->_right);
	}
	QueueDestroy(&q);
}

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
			break;

		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	QueueDestroy(&q);
	return 1;
}

完

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

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

相关文章

青蛙跳台阶问题

青蛙跳台阶问题

本期介绍🍖 主要介绍：青蛙跳台阶问题，青蛙跳台阶与斐波那契数列的关系👀。 文章目录 1. 题目2. 递归解题思路3. 迭代解题思路 1. 题目 从前有一只青蛙他想跳台阶，有n级台阶，青蛙一次可以跳1级台阶&#xff…
阅读更多...
06_Tomcat

06_Tomcat

文章目录 Tomcat1.概念2.Tomcat安装3.Tomcat项目结构4.标准web项目结构5.Tomcat部署项目方式6.IDEA关联Tomcat6.1 构建tomcat和idea关联6.2 使用idea创建一个Javaweb工程6.3 使用idea将工程**构建**成一个app6.4 使用idea将构建好的app**部署**到tomcat中 Tomcat 1.概念 Tomc…
阅读更多...
【MySQL事务（上）】

【MySQL事务（上）】

文章目录 前言一、什么是事务？1.关于事务的特性 二、为什么要有事务三、事务的提交方式测试事务准备工作事务的操作1.启动事务2.对事务进行回滚（只有在事务进行期间）3.提交事务（持久化）4.事务的异常情况结论 四、事务的…
阅读更多...
三十篇：动脉脉搏：企业业务处理系统的生命力

三十篇：动脉脉搏：企业业务处理系统的生命力

动脉脉搏：企业业务处理系统的生命力 1. 引言 在数字经济的浪潮下，企业之间的竞争已不仅仅是产品和服务的竞争，更是信息处理能力的竞争。业务处理系统（Transaction Processing System, TPS）是企业信息系统架构的基础&a…
阅读更多...
YOLOV8逐步分解（5）_模型训练初始设置之混合精度训练AMP

YOLOV8逐步分解（5）_模型训练初始设置之混合精度训练AMP

yolov8逐步分解(1)--默认参数&超参配置文件加载 yolov8逐步分解(2)_DetectionTrainer类初始化过程 yolov8逐步分解(3)_trainer训练之模型加载_yolov8 加载模型-CSDN博客 YOLOV8逐步分解(4)_模型的构建过程 在上述文章逐步分解（3）和（4&…
阅读更多...
第十二届蓝桥杯物联网试题（国赛）

第十二届蓝桥杯物联网试题（国赛）

不得不说国赛相比较省赛而言确实，功能变得更加复杂，更加繁琐，特别是串口LORA通信相结合的更加频繁，且对收取的字符处理要求要更加复杂，处理判别起来会更加复杂。 对于收发数据本身来说，收发的数据本身是以…
阅读更多...
导入 FDTD 仿真的 S 参数到 INTERCONNECT 的器件中

导入 FDTD 仿真的 S 参数到 INTERCONNECT 的器件中

导入 FDTD 仿真的 S 参数到 INTERCONNECT 的器件中 正文正文 很多时候，仿真链路比较大时，我们可以将仿真的每个部分分隔开来，用 FDTD 计算出每一部分的 S 参数，然后将这些 S 参数导入 INTERCONNECT 中得到最终的仿真结果。这里我们来介绍一下这种方法。 首先，我们从右侧…
阅读更多...
最简单的AI训练方法-RAG增强检索原理

最简单的AI训练方法-RAG增强检索原理

文章目录 1、RAG（ Retrieval-Augmented Generation）2、RAG的基本原理3、简化训练流程4、RAG增强检索原理图 1、RAG（ Retrieval-Augmented Generation） RAG（ Retrieval-Augmented Generation）是一种结合了检…
阅读更多...
完全背包+背包装满 总结

完全背包+背包装满 总结

目录 1.背包恰好装满 （1）问题是什么 （2）问题的有效状态和无效状态 （3）问题的常考形式，以及如何去处理 1.值的大小 2.组合个数 3.排列个数 2.例题 A. Cut Ribbon HDU1114 Piggy-Bank …
阅读更多...
计算机视觉中-语义分割

计算机视觉中-语义分割

语义分割 语义分割是计算机视觉中的一个关键技术，它涉及对图像中的每个像素进行类别划分，从而识别出图像中的不同物体或区域。具体来说，语义分割就是按照“语义”给图像上目标类别中的每一点打上一个标签，使得不同种类的东西在图像…
阅读更多...
装机必备——WinRAR安装教程

装机必备——WinRAR安装教程

装机必备——WinRAR安装教程 软件下载 软件名称：WinRAR 软件语言：简体中文 软件大小：3.38M 系统要求：Windows7或更高， 32/64位操作系统 硬件要求：CPU2GHz ，RAM4G或更高 下载通道①迅雷云盘丨下…
阅读更多...
AI重塑了我的工作流

AI重塑了我的工作流

阅读内容 Inhai: Agentic Workflow：AI 重塑了我的工作流 4 种主要的 Agentic Workflow 设计模式 Reflection（反思）：让 Agent 审视和修正自己生成的输出。 举例：如果有两个 Agent：一个负责 Coding&#…
阅读更多...
【uniapp】uniapp基本介绍

【uniapp】uniapp基本介绍

目录 介绍体验uni-app优势功能框架图 uni-app组成和跨端原理基本语言和开发规范 编译器运行时（runtime）uni-app runtime包括3部分：基础框架、组件、API基础框架：组件：组件的扩展： API： 逻辑层和…
阅读更多...
工业网关设备：HiWoo Box网关

工业网关设备：HiWoo Box网关

在数字化、智能化的工业浪潮中，工业网关以其卓越的性能和广泛的应用场景，成为了工业互联的核心驱动力。作为一款高效、稳定、智能的工业网关设备，HiWoo Box网关不仅实现了工业现场设备与网络的高效连接，更为企业提供了智能化的数据…
阅读更多...
C++青少年简明教程：switch语句

C++青少年简明教程：switch语句

C青少年简明教程：switch语句 在C中，switch语句用于基于一个表达式的值来执行不同的代码块。这个表达式通常是一个整数类型（如int，char，或枚举类型），并且case标签必须是整数常量表达式。 语法格…
阅读更多...
Node.js —— Express 中间件、接口编写、接口跨域 【0基础向Express模块学习】

Node.js —— Express 中间件、接口编写、接口跨域 【0基础向Express模块学习】

目录 中间件的概念 什么是中间件 现实生活中的例子 Express 中间件的调用流程 ​编辑 Express 中间件的格式 next 函数的作用 Express 中间件的初体验 定义中间件函数 全局生效的中间件 定义全局中间件的简化形式 中间件的作用 ​编辑 定义多个全局中间件 局部生…
阅读更多...
【技术分享】Maven常用配置

【技术分享】Maven常用配置

一、Maven简介 （一）为什么使用 Maven 由于 Java 的生态非常丰富，无论你想实现什么功能，都能找到对应的工具类，这些工具类都是以 jar 包的形式出现的，例如 Spring，SpringMVC、MyBatis、数据库驱…
阅读更多...
OrangePi Kunpeng Pro 开发板测评及Python开发实测

OrangePi Kunpeng Pro 开发板测评及Python开发实测

一、背景 首先感谢 创新乐知通过CSDN 邀请本人，参与这次 评测活动。这块开发板是香橙派联合华为精心打造，具有超强算力的鲲鹏开发板。本人使用最多的还是树莓派系列的板子，国产板子特别是华为为核心的板子还是头一次使用，特别感兴…
阅读更多...
Linux-挂盘-分区-卸盘

Linux-挂盘-分区-卸盘

Linux-挂盘-分区-卸盘 1. 添加硬盘 2. 查看硬盘 [rootlocalhost /]# lsblk # 查看我们新添加的磁盘 NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINT sda 8:0 0 80G 0 disk ├─sda1 8:1 0 1G 0 part /boot └─sda2 …
阅读更多...
Ubuntu22.04之解决：忘记登录密码(二百三十二)

Ubuntu22.04之解决：忘记登录密码(二百三十二)

简介： CSDN博客专家，专注Android/Linux系统，分享多mic语音方案、音视频、编解码等技术，与大家一起成长！ 优质专栏：Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏：多媒…
阅读更多...
最新文章

Copyright @ 2022~2023