二叉树的实现（详解，数据结构）

目录

一，二叉树需要实现的功能

二，下面是各功能详解

0.思想：

1.创建二叉树结点：

2.通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

3.二叉树销毁：

4.前序遍历：

5.中序遍历：

6.后序遍历：

 7.层序遍历：

1.先实现队列的基本功能：

2.基于队列实现层序：

8.计算各类结点数量：

1.计算二叉树结点数量：

2.计算叶子结点数量：

3.计算K层结点数量：

9.二叉树查找值为X的结点：

10.判断二叉树是否为完全二叉树：

一，二叉树需要实现的功能

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

二，下面是各功能详解

0.思想：

下面很多功能都涉及分治的思想（分治法是算法常用的解题方法之一，是将一个大的问题拆分为若干小的问题。）

1.创建二叉树结点：

//重命名存储变量类型，方便更改
typedef char BTDataType;

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

2.通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) {
	if (*pi >= n || a[*pi] == '#') {
		(*pi)++;
		return NULL;
	}
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL) {
		perror("BinaryTreeCreate::malloc");
		exit(0);
	}
	Node->_data = a[*pi];
	(*pi)++;
	Node->_left = BinaryTreeCreate(a, n, pi);
	Node->_right = BinaryTreeCreate(a, n, pi);
	return Node;
}

按照以上所给数组描述，我们创建出的二叉树：

3.二叉树销毁：

二叉树的存储类似链表，可以由前面的结点找到后面的结点，因此二叉树的销毁也是由后向前销毁会方便很多，所以我们采取后序来销毁二叉树

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

4.前序遍历：

        i、先访问根结点；

        ii、再前序遍历左子树；

        iii、最后前序遍历右子树；

算法实现：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root) {
	if (root != NULL) {
		printf("%c ", root->_data);
		BinaryTreePrevOrder(root->_left);
		BinaryTreePrevOrder(root->_right);
	}
}

5.中序遍历：

        i、中序遍历左子树；

        ii、访问根结点；

        iii、中序遍历右子树

算法实现：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {
	if (root != NULL) {
		BinaryTreeInOrder(root->_left);
		printf("%c ", root->_data);
		BinaryTreeInOrder(root->_right);
	}
}

6.后序遍历：

        i、后序遍历左子树

        ii、后序遍历右子树

        iii、访问根结点

 算法实现：

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {
	if (root != NULL) {
		BinaryTreePostOrder(root->_left);
		BinaryTreePostOrder(root->_right);
		printf("%c ", root->_data);
	}
}

 7.层序遍历：

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

思路：层序遍历需要用到队列的知识，就是先将根结点入队，判断队列是否为空，循环将队首元素出队的同时队首元素子节结点入队

算法实现：

1.先实现队列的基本功能：
typedef BTNode QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType* _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q) {
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
}
int QueueEmpty(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType* data) {
	assert(q);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL) {
		perror("QueuePush:malloc");
		return;
	}
	tmp->_data = data;
	tmp->_next = NULL;
	if (QueueEmpty(q)) {
		q->_front = tmp;
		q->_rear = tmp;
	}
	q->_rear->_next = tmp;
	q->_rear = tmp;
}
// 队头出队列 
void QueuePop(Queue* q) {
	if (QueueEmpty(q)) {
		printf("Pop: Queue is empty\n"); // 更清晰的错误信息  
		exit(0);
	}
	q->_front = q->_front->_next;
	//free(tmp);
}
// 获取队列头部元素 
QDataType* QueueFront(Queue* q) {
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType* QueueBack(Queue* q) {
	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q) {
	QNode* cur = q->_front;
	int size = 0;
	while (cur) {
		size++;
		cur = cur->_next;
	}
	return size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q) {
	assert(q);
	if (q->_front == NULL) {
		return 1;
	}
	return 0;
}
// 销毁队列 
void QueueDestroy(Queue* q) {
	assert(q);
	while (!QueueEmpty(q)) {
		QueuePop(q);
	}
}
2.基于队列实现层序：
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root) {
	Queue* queue = (Queue*)malloc(sizeof(Queue));
	BTNode* front;
	QueueInit(queue);
	if (root) {
		QueuePush(queue, root);
	}
	while (!QueueEmpty(queue)) {
		front = QueueFront(queue);
		if (front->_left)
		{
			QueuePush(queue, front->_left);
		}
		if (front->_right)
		{
			QueuePush(queue, front->_right);
		}
		printf("%c ",front->_data);
		QueuePop(queue);
	}
	printf("\n");
	QueueDestroy(queue);
}

8.计算各类结点数量：

1.计算二叉树结点数量：
// 二叉树节点个数
int BinaryTreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
	}
}
2.计算叶子结点数量：
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	else {
		return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
	}
}
3.计算K层结点数量：
// 二叉树第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);
}

9.二叉树查找值为X的结点：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root==NULL) {
		return NULL;
	}
	if (root->_data == x) {
		return root;
	}
	BTNode* r1 = BinaryTreeFind(root->_left, x);
	if (r1 != NULL) {
		return r1;
	}
	return BinaryTreeFind(root->_right, x);
}

10.判断二叉树是否为完全二叉树：

根据完全二叉树的定义，具有n个结点的完全二叉树与满二叉树中编号从1~n的结点一一对应。
算法思想：采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空结点。若有，则二叉树不是完全二叉树。

判断二叉树是否为完全二叉树是二叉树层序遍历的基本用途之一，也要借助队列来实现；

算法实现：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {
	Queue queue;
	QueueInit(&queue);
	if (root) {
		QueuePush(&queue, root);
	}
	while (!QueueEmpty(&queue)) {
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);
		if (front == NULL) {
			break;
		}
		QueuePush(&queue, front->_left);
		QueuePush(&queue, front->_right);
	}
	while (!QueueEmpty(&queue)) {
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);
		if (front) {
			QueueDestroy(&queue);
			return 0;
		}
	}
	QueueDestroy(&queue);
	return 1;
}

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

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

相关文章

小红书「打工人」生存现状实录

小红书「打工人」生存现状实录

近年来，“打工人”一词频繁出现在内容场景中。调研小红书数据显示，近一年“打工人、职场”相关笔记声量增长440%，预估互动总量增长128%，热度高涨。 职场年轻人正披着“打工人”的外壳，不断自嘲中寻求身份认同。基于此&…
阅读更多...
各种流量包特征

各种流量包特征

[CVE-2013-1966] Apache Struts2 远程命令执行漏洞 要执行的命令在exec里面，而且回显数据包里面有明显执行结果回显 [CVE-2017-8046] Spring Data Rest 远程命令执行漏洞 回显不明显，考试提供的解码工具不能解密， [CVE-2017-12149] JBOSS…
阅读更多...
java多线程编码应用1——java多线程CompletableFuture使用技巧

java多线程编码应用1——java多线程CompletableFuture使用技巧

在实际项目开发过程中，大部分程序的执行顺序都是按照代码编写的先后顺序，依次从上往下挨个执行的，但是对于统计或者批量操作数据时，是否有更好的方案呢？这时候就可以考虑使用多线程编程，异步并行执行多个任…
阅读更多...
Flink checkpoint 源码分析- Checkpoint snapshot 处理流程

Flink checkpoint 源码分析- Checkpoint snapshot 处理流程

背景 在上一篇博客中我们分析了代码中barrier的是如何流动改的。Flink checkpoint 源码分析- Checkpoint barrier 传递源码分析-CSDN博客 最后跟踪到了代码org.apache.flink.streaming.runtime.io.checkpointing.CheckpointedInputGate#handleEvent 现在我们接着跟踪相应代…
阅读更多...
投资线上黄金是否属于外汇交易？探究黄金与外汇市场的关系

投资线上黄金是否属于外汇交易？探究黄金与外汇市场的关系

在金融市场中，线上黄金投资和外汇交易都是备受关注的领域。许多人可能会混淆这两者，认为投资线上黄金也是一种外汇交易。但实际上，尽管线上黄金和外汇交易有一些相似之处，但它们在本质上是不同的投资领域。本文将探讨投资线上黄金…
阅读更多...
前端 Android App 上架详细流程 （Android App）

前端 Android App 上架详细流程 （Android App）

1、准备上架所需要的材料 先在需要上架的官方网站注册账号。提前把手机号，名字，身份证等等材料准备好，完成开发者实名认证；软著是必要的，提前准备好，软著申请时间比较长大概需要1-2周时间才能下来&#xf…
阅读更多...
流畅的python-学习笔记_序列修改+散列+切片

流畅的python-学习笔记_序列修改+散列+切片

vector第一版 reprlib.repr用于选取有限长度较长变量 vector第二版切片 注意切片还有indices属性，它可以入参一个序列长度，根据此序列长度，转化不规矩的start stop stride， vector第三版动态存取属性 obj.attra时，先…
阅读更多...
构建 imx6ull sd 卡启动

构建 imx6ull sd 卡启动

1. 硬件环境 imx6ull 256MB tf 卡 512 MB 的 ddr； ubuntu 20.04； 芯片默认的启动方式是通过 LCD_DATA0 ~ LCD_DATA23；上下拉方式来确认的； 需要注意的上下拉是 BOOT_CFG1[7] BOOT_CFG1[6] BOOT_CFG1[5] 启动选择 和 BOOT_CF…
阅读更多...
leetcode-矩阵最长递增路径-102

leetcode-矩阵最长递增路径-102

题目要求 思路 1.通过双循环去把每一个结点作为起始点进行统计，将返回的路径长度存放在res中，取最大的res的长度。 2.递归中需要的几个值，x和y当前结点的坐标，pre用于存储上一个结点的元素值，因为要求是路径上的元素是…
阅读更多...
3D 交互展示该怎么做？

3D 交互展示该怎么做？

在博维数孪（Bowell）平台制作3D交互展示的流程相对简单，主要分为以下几个步骤： 1、准备3D模型：首先，你需要有一个3D模型。如果你有3D建模的经验，可以使用3ds Max或Blender等软件自行创建。如果没…
阅读更多...
前后端分离项目中的一些疑惑

前后端分离项目中的一些疑惑

1、前后端分离项目，浏览器发起请求后，请求的是前端服务器还是后端服务器？ 在前后端分离的项目中，当浏览器发起请求时，它首先会请求的是前端服务器。 前后端分离的工作流程大致如下： 用户在浏览器中输入网…
阅读更多...
Echarts散点图的29个配置项，散点图可以随心所欲啦。

Echarts散点图的29个配置项，散点图可以随心所欲啦。

1-9 当使用 ECharts 绘制散点图时，可以配置以下一些常用的选项： 1. tooltip：配置提示框组件，用于显示鼠标悬停在散点上时的提示信息。 2. legend：配置图例组件，用于展示不同散点的标识和名称。 3. xAxis…
阅读更多...
图数据库 之 Neo4j 与 AI 大模型的结合绘制知识图谱

图数据库 之 Neo4j 与 AI 大模型的结合绘制知识图谱

引言 随着信息时代的到来，海量的文本数据成为了我们获取知识的重要来源。然而，如何从这些文本数据中提取出有用的信息，并将其以可视化的方式展示出来，一直是一个具有挑战性的问题。近年来，随着人工智能技术的发展&…
阅读更多...
rust使用serde_json转换Value为rust中的数据类型

rust使用serde_json转换Value为rust中的数据类型

为了方便转换未知json数据，我们可以使用serde提供的value类型来进行转换，将json字符串转化为Value值，然后可以快速使用get方法来获取值： let json_str r#"{"name": "John","age": 30,"c…
阅读更多...
科技控必看！让你轻松成为机器人领域达人

科技控必看！让你轻松成为机器人领域达人

科技控们注意了！你是不是经常对机器人技术充满无限的好奇，却又因为缺乏合适的渠道而难以深入了解和亲身体验呢？别担心，BFT机器人，正是你探索机器人世界的绝佳之地！ 在这里，你将发现一个充满惊喜…
阅读更多...
政安晨：【Keras机器学习示例演绎】（三十九）—— 使用 FNet 进行文本分类

政安晨：【Keras机器学习示例演绎】（三十九）—— 使用 FNet 进行文本分类

目录 简介 模型 设置 加载数据集 对数据进行标记 格式化数据集 建立模型 训练我们的模型 与变换器模型比较 政安晨的个人主页：政安晨 欢迎 👍点赞✍评论⭐收藏 收录专栏: TensorFlow与Keras机器学习实战 希望政安晨的博客能够对您有所裨益&…
阅读更多...
Linux学习之高级IO

Linux学习之高级IO

之前的内容我们基本掌握了基础IO，如套接字，文件描述符，重定向，缓冲区等知识都是文的基本认识，而高级IO则是指更加高效的IO。 对于应用层，在读写的时候，本质就是把数据写给OS，若一方…
阅读更多...
1W 3KVDC 隔离 单输出 DC/DC 电源模块 ——TPF 系列

1W 3KVDC 隔离 单输出 DC/DC 电源模块 ——TPF 系列

TPF系列提供输出稳压，精度高，对于输出电压有要求的场合特别适合，工业级环境温度，用于PCB安装的国际标准结构。此系列产品小巧，效率高，低输出纹波及提供3000V以上的直流电压隔离，封装有SIP和DIP可…
阅读更多...
实测幻方新出的超强AI大模型，中文能力对比GPT4.0不落下风

实测幻方新出的超强AI大模型，中文能力对比GPT4.0不落下风

目前从网上的消息来看，DeepSeek中文综合能力（AlignBench）开源模型中最强，与GPT-4-Turbo，文心4.0等闭源模型在评测中处于同一梯队。 话不多说，我们开测！ 1.首先我们来让他直接来一段逻辑推理【并…
阅读更多...
Jetpack Compose三：主题和基础控件的使用

Jetpack Compose三：主题和基础控件的使用

设置主题 与Android View的主题定义方式不同，Jetpack Compose中的主题由许多较低级别的结构体和相关API组成，它们包括颜色、排版和形状属性。 Theme.kt控制工程的主题，它是一个可组合的Compose函数 最后主题函数ComposeStudyTheme的相关设置…
阅读更多...
最新文章

Copyright @ 2022~2023