树形结构C语言的实现

一.什么是树:

树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构,所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构:一棵树可以简单的表示为根,左子树,右子树。左子树和右子树又有自己的子树。

 树的一些属性:

1、结点(Node):表示树中的数据元素,由数据项和数据元素之间的关系组成。在图中,共有10个结点。

2、结点的度(Degree of Node):结点所拥有的子树的个数,在图中,结点A的度为3。

3、树的度(Degree of Tree):树中各结点度的最大值。在图5.1中,树的度为3。

4、叶子结点(Leaf Node):度为0的结点,也叫终端结点。在图5.1中,结点E、F、G、H、I、J都是叶子结点。

5、分支结点(Branch Node):度不为0的结点,也叫非终端结点或内部结点。在图5.1中,结点A、B、C、D是分支结点。

6、孩子(Child):结点子树的根。在图中,结点B、C、D是结点A的孩子。

7、双亲(Parent):结点的上层结点叫该结点的双亲。在图中,结点B、C、D的双亲是结点A。

8、祖先(Ancestor):从根到该结点所经分支上的所有结点。在图中,结点E的祖先是A和B。

9、子孙(Descendant):以某结点为根的子树中的任一结点。在图中,除A之外的所有结点都是A的子孙。

10、兄弟(Brother):同一双亲的孩子。在图5.1中,结点B、C、D互为兄弟。

11、结点的层次(Level of Node):从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1,其余结点的层次等于其双亲结点的层次加1。 [1]

12、堂兄弟(Sibling):同一层的双亲不同的结点。在图中,G和H互为堂兄弟。

13、树的深度(Depth of Tree):树中结点的最大层次数。在图5.1中,树的深度为3。 [1]

14、无序树(Unordered Tree):树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。 [1]

15、有序树(Ordered Tree):树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树,因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。 [1]

16、森林(Forest):m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大,但在数据结构中树和森林的概念差别很小。从定义可知,一棵树由根结点和m个子树构成,若把树的根结点删除,则树变成了包含m棵树的森林。当然,根据定义,一棵树也可以称为森林。

一些特殊的树:

树中最特殊最经典的就是二叉树,二叉树顾名思义就是只有两个分叉的树,也就是度为二的树。

二叉树中又有俩个最为经典的树分别为完全二叉树和满二叉树。

一棵深度为k且有个结点的二叉树称为满二叉树。

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

二.用c语言实现一颗树:

要实现一颗树我们首先要先定义一个树的结构体

然后要确定我们树的基本功能

 

接着就是写完这些函数

 

#include"BinaryTree.h"

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
 	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = a[(*pi)++];
	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);
	return root;
}

void BinaryTreeDestory(BTNode* root)
{
	assert(root);
	if (root == NULL)
		return;
	BinaryTreeDestory(root->right);
	BinaryTreeDestory(root->left);
	free(root);
	root = NULL;
}

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;
	k--;
	return BinaryTreeLevelKSize(root->left,k) + BinaryTreeLevelKSize(root->right,k);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind != NULL)
		return leftfind;
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind != NULL)
		return rightfind;
	return NULL;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root)
	{
		printf("%c", root->data);
		BinaryTreePrevOrder(root->left);
		BinaryTreePrevOrder(root->right);
	}
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreeInOrder(root->left);
		printf("%c", root->data);
		BinaryTreeInOrder(root->right); 
	}
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreePostOrder(root->left);
		BinaryTreePostOrder(root->right);
		printf("%c", root->data);
	}
}

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

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

相关文章

Android HWASAN使用与实现原理

一、背景 为了提前检测出Android User Sapce的app或native进程的内存错误问题,帮助研发定位与分析这些问题,基于Android 14版本上对HWASAN做了调研分析。 二、ASAN介绍 HWASAN是在ASAN的基础上做了拓展,因此在介绍HWASAN之前先了解下ASAN.…

电源设计改进稳定度和误差放大器的解决方案

电池,变压器,电源和转换器会不断受到能量损失的影响。结果,负载上的输出电压会降低。温度是性能的另一个关键特征。通过创建误差放大系统,可以在任何类型的负载下稳定输出电压。 稳压二极管稳定器 使用功率晶体管以及电流放大器…

自己动手实现语音识别

声音的本质是震动,震动的本质是位移关于时间的函数,波形文件(.wav)中记录了不同采样时刻的位移。 通过傅里叶变换,可以将时间域的声音函数分解为一系列不同频率的正弦函数的叠加,通过频率谱线的特殊分布,建立音频内容和文本的对应关系,以此作为模型训练的基础。 语音mfc…

比赛获奖的武林秘籍:02 国奖秘籍-大学生电子计算机类竞赛快速上手的流程,小白必看

比赛获奖的武林秘籍:02 国奖秘籍-大学生电子计算机类竞赛快速上手的流程,小白必看 摘要 本文主要介绍了大学生参加电子计算机类比赛(电赛、光电设计大赛、计算机设计大赛、嵌入式芯片与系统设计大赛等比赛)的流程和涉及到的知识…

【Portswigger 学院】文件上传

教程和靶场来源于 Burpsuite 的官网 Portswigger:File upload vulnerabilities - PortSwigger 原理与危害 很多网站都有文件上传的功能,比如在个人信息页面允许用户上传图片作为头像。如果网站应用程序对用户上传的文件没有针对文件名、文件类型、文件内…

解决中型组织三个人力资源基础问题的方法

中型企业 (通常在700 - 5000名员工之间)是从中小企业发展起来的,但不称为大型企业。虽然个别市场取得了成功,但到2023年,中端市场经历了一个艰难的结局,受到了更广泛的经济挑战的影响。然而,它仍然具有灵活性和乐观性&…

24_嵌入式系统输入输出设备

目录 GPIO原理与结构 A/D接口基本原理 A/D接口原理 A/D转换的重要指标 D/A接口基本原理 D/A接口原理 DAC的分类 D/A转换器的主要指标 键盘接口基本原理 键盘接口原理 用I/O口实现键盘接口 显示接口基本原理 基本结构和特点 基本原理 LCD种类 市面上出售的LCD的类…

dtpay聚合支付系统在跨境支付场景中技术及业务方案

1 什么是跨境支付 我们从两个维度来分析什么是跨境支付,第一个维度我们从资金流向分析,国内的消费者在境外进行消费对于国内资金流来说这属于资金流出,这是跨境支付的第一种应用场景。第二个场景国外游客在国内进行消费,这属于资…

【ECCV 2024】首个跨模态步态识别框架:Camera-LiDAR Cross-modality Gait Recognition

【ECCV 2024】首个跨模态步态识别框架:Camera-LiDAR Cross-modality Gait Recognition 简介:主要方法:实验结果: 论文:https://arxiv.org/abs/2407.02038 简介: 步态识别是一种重要的生物特征识别技术。基…

【论文阅读】-- Strscope:不规则测量的时间序列数据的多尺度可视化

Stroscope: Multi-Scale Visualization of Irregularly Measured Time-Series Data 摘要1 引言2相关工作2.1(大型)时间序列数据可视化2.2 事件序列数据可视化2.3 评价 3问题分析3.1 数据集3.2 场景——现状3.3 设计流程3.4 设计原理 4 涟漪图&#xff1a…

十大排序:插入/希尔/选择/堆/冒泡/快速/归并/计数/基数/桶排序 汇总(C语言)

目录 前言非线性时间比较类插入排序(1) 直接插入排序(2) 希尔排序 选择排序(3) 选择排序优化版(4) 堆排序 交换排序(5) 冒泡排序(6) 快速排序hoare版本挖坑版前后指针版非递归版 归并排序(7) 归并排序递归版非递归版 线性时间比较类(8) 计数排序基数排序与桶排序 总结 前言 在计…

昇思25天学习打卡营第16天|文本解码原理——以MindNLP为例

在大模型中,文本解码通常是指在自然语言处理(NLP)任务中使用的大型神经网络模型(如Transformer架构的模型)将编码后的文本数据转换回可读的原始文本的过程。这些模型在处理自然语言时,首先将输入文本&#…

自闭症儿童的治疗方法有哪些?

身为星贝育园自闭症儿童康复学校的资深教育者,我深知自闭症谱系障碍(ASD)儿童的教育与治疗需要一个全面、个性化的方案。在星贝育园,我们致力于为孩子们提供一个充满爱与理解的环境,采用多种科学验证的教育方法&#x…

【Java11】变量的初始化和内存中的运行机制

成员变量的初始化和内存中的运行机制 系统加载类或创建类的实例时,系统自动为成员变量分配内存空间,然后自动为成员变量指定初始值。 class Person {public String name; // 实例变量public static int eyeNum; // 类变量 }var p1 Person(); var p2 …

动态线程池思想学习及实践

引言 在后台项目开发过程中,我们常常借助线程池来实现多线程任务,以此提升系统的吞吐率和响应性;而线程池的参数配置却是一个难以合理评估的值,虽然业界也针对CPU密集型,IO密集型等场景给出了一些参数配置的经验与方案…

MQ:RabbitMQ

同步和异步通讯 同步通讯: 需要实时响应,时效性强 耦合度高 每次增加功能都要修改两边的代码 性能下降 需要等待服务提供者的响应,如果调用链过长则每次响应时间需要等待所有调用完成 资源浪费 调用链中的每个服务在等待响应过程中,不能释放请求占用的资源,高并发场景下…

【后端面试题】【中间件】【NoSQL】MongoDB查询优化2(优化排序、mongos优化)

优化排序 在MongoDB里面,如果能够利用索引来排序的话,直接按照索引顺序加载数据就可以了。如果不能利用索引来排序的话,就必须在加载了数据之后,再次进行排序,也就是进行内存排序。 可想而知,如果内存排序…

【RT-thread studio 下使用STM32F103-学习sem-信号量-初步使用-线程之间控制-基础样例】

【RT-thread studio 下使用STM32F103-学习sem-信号量-初步使用-线程之间控制-基础样例】 1、前言2、环境3、事项了解(1)了解sem概念-了解官网消息(2)根据自己理解,设计几个使用方式(3)不建议运行…

DataWhale-吃瓜教程学习笔记 (七)

学习视频**:第6章-支持向量机_哔哩哔哩_bilibili 西瓜书对应章节: 第六章 支持向量机 - 算法原理 几何角度 对于线性可分数据集,找距离正负样本距离都最远的超平面,解是唯一的,泛化性能较好 - 超平面 - 几何间隔 例…

堆叠的作用

一、为什么要堆叠 传统的园区网络采用设备和链路冗余来保证高可靠性,但其链路利用率低、网络维护成本高,堆叠技术将多台交换机虚拟成一台交换机,达到简化网络部署和降低网络维护工作量的目的。 二、堆叠优势 1、提高可靠性 堆叠系统多台成…