数据结构DAY5--二叉树相关流程

流程有:创建->遍历->得到信息->销毁 

创建

根据先序遍历的流程以及对叶子结点的左后驱结点和右后驱结点以#号替代的原则,写出一个数组,并建立一个结构体,包括数据域,结构体类型的左后驱结点和右后驱结点指针。

typedef struct tree_node
{
	BTint data;//任意数据类型
	struct tree_node *pl;
	struct tree_node *pr;
}TREE_NODE;

char tree[] = "ABC##EH###DF##G##";

以上述两者为基础,建立函数:初始化一个数据,其值为创建的数组,数组角标为一个全局变量,以便于在树中插入数据,用结构体定义一个指针,大小为结构体大小,使其数据域为数组中的值,左右后驱结点指向函数自身(回调以创造子结点)最后返回该指针结点---当数组数据为#时,直接返回NULL,以结束创建过程。

TREE_NODE *create_Btree()
{
	BTDATA_TYPE data = tree[idx++];
	if (data == '#')
	{
		return NULL;
	}

	TREE_NODE *pnode = malloc(sizeof(TREE_NODE));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return  NULL;
	}
	pnode->data = data;
	pnode->pl = create_Btree();
	pnode->pr = create_Btree();

	return pnode;
}

遍历

前序

输入树,若树指向空则返回(证明从根节点到叶子结点一条线已经遍历完了),打印根结点(数据域),然后以左结点为新的根结点回调自身,再以左结点为新的根结点回调自身,即遍历完毕。

void pre_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	printf("%c", proot->data);
	pre_order(proot->pl);
	pre_order(proot->pr);
}

中序

void mid_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}

	mid_order(proot->pl);
	printf("%c", proot->data);
	mid_order(proot->pr);
}

后序

void pos_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	
	pos_order(proot->pl);
	pos_order(proot->pr);
	printf("%c", proot->data);
}

遍历以回调函数为主,看似复杂且难以理解,实际步骤很简单,以下以前序遍历为例做过程分析:

1.打印出A->2.以B为新的根结点,回调自身->3.打印B->4.以B为新的根结点,回调自身->

5.打印C->6.以C的左结点为新的根结点,回调自身->7.C的左结点为空,结束6返回上一级

->8.以C的右结点为新的根结点,回调自身->9.C的右结点为空,结束8返回上一级->10.C这一步回调函数运行结束,继续函数4的下一步,以B的右结点D为新的根结点,回调自身->11.与C的过程相同->12.B的函数运行结束,继续函数1的下一步->13.以E为新的根结点,回调自身->14.与C的过程相同->结束函数。

获得二叉树相关信息

获得二叉树的结点个数

传入树根结点,若树的结点为空,则返回0,否则返回1与以自身的左结点为根结点的回调函数与右以自身的右结点为根结点的回调函数,即可获得结点个数,其逻辑与前面遍历类似

int get_tree_node(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	return 1+get_tree_node(proot->pl)+get_tree_node(proot->pr);
}

获得二叉树的层数

其逻辑是获得所有分支的层数,然后通过对比获得最大值,就是二叉树的层数,思想与遍历类似,使用回调函数来实现:首先将根结点输入函数,若函数为空,则返回0,接着以左结点为根结点回调自身,然后以左结点为根结点回调自身,最后返回左右分支中最大的一只,并加上根结点这一层,就是层数

int get_btree_layer_cnt(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	int layL = get_btree_layer_cnt(proot->pl);
	int layR = get_btree_layer_cnt(proot->pr);

	return layL > layR ? layL+1 : layR+1;
}

销毁

与遍历思想类似:只不过是把打印换为了释放空间:

void destroy_btree(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	destroy_btree(proot->pl);
	destroy_btree(proot->pr);
	free(proot);
}

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

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

相关文章

数字证书在网络安全中的关键作用与日常应用

在当今数字化的时代,网络安全问题日益凸显,保护数据安全和用户隐私成为了人们关注的焦点。数字证书作为一种重要的网络安全技术,其在网络安全中扮演着关键的角色,并且在我们的日常生活中有着广泛的应用。现在给大家介绍简单介绍下…

blender怎么用GPU渲染?blender GPU云渲染推荐

在三维建模和渲染领域,Blender以其强大的功能和免费开源的特点广受好评。GPU渲染作为提升渲染效率的关键技术,越来越受到用户的关注。本文将详细介绍如何在Blender中设置并利用GPU进行渲染,以及探索其云渲染的可能性,助力用户高效…

装机指导。

everything winrar snipaste cmake git tortoisegit tortoisesvn inno setup vs2022 安装的时候注意sdk路径一定要默认!! 否则你会发现在你的sdk安装路径的根盘符下会多出一个Windows Kits,强迫症接受不了 默认的会跟已有的装在一起…

无法用raven-js,如何直接使用TraceKit标准化错误字符串(一次有趣的探索)

引子:网上三年前(2020)的文章介绍了一个raven-js 简单说就是把堆栈信息格式化兼容各浏览器,便于查看错误来源。 **but:**到处找了一下raven-js,已经没有官方出处了,只在Sentry的源码仓库里发现…

林江院长赴长沙见证爱尔眼科巩膜镜技术诊疗门诊启动仪式

近日,爱尔眼科“巩膜镜技术诊疗门诊、视觉康复及训练门诊”启动会在湖南长沙顺利举行。旨在通过成立爱尔眼科巩膜镜技术诊疗门诊、视觉康复及训练门诊,为有需要的疑难屈光不正患者提供全新的诊疗途径,为各年龄阶段人群视觉问题提供更全面的个…

[数据结构初阶]二叉树

我们在前两篇博客中主要介绍了堆及其应用,针对的对象堆是完全二叉树,存储方式采用顺序结构存储的方式。 那么好的,这篇博客我们浅谈二叉树的链式存储,针对的对象是二叉树,并不局限于完全二叉树了! 我们先来…

PlayerSettings.WebGL.emscriptenArgs设置无效的问题

1)PlayerSettings.WebGL.emscriptenArgs设置无效的问题 2)多个小资源包合并为大资源包的疑问 3)AssetBundle在移动设备上丢失 4)Unity云渲染插件RenderStreaming,如何实现多用户分别有独立的操作 这是第381篇UWA技术知…

MySOL之旅--------MySQL数据库基础( 3 )

本篇碎碎念:要相信啊,胜利就在前方,要是因为一点小事就停滞不前,可能你也不适合获取胜利,成功的路上会伴有泥石,但是走到最后,你会发现身上的泥泞皆是荣耀的勋章! 今日份励志文案: 凡是发生皆有利于我 目录 查询(select) 1.全列查询 2.指定列查询 3.查询字段为表达式 ​编…

PVE系统的安装

一.PVE系统的安装 前置准备环境:windows电脑已安装Oracle VM VirtualBox,电脑支持虚拟化,且已经开启,按住ctrl+shift+ESC打开任务管理器查看是否开启,如果被禁用,可进入BIOS开启虚拟化,重启电脑后再进行后续操作。本步骤选用windows10安装VirtualBox,版本为7.0.8。 …

被拒绝的职场空窗期,到底该怎么办?

打工人的心头刺 最近,一则新闻在网上炸开了锅:一位求职者因职场空窗期超过三个月,竟被无情拒绝应聘。消息一出,瞬间引起了广大职场人的共鸣。在这个快节奏的时代,我们似乎被一种无形的力量推着,不敢休息&am…

高性能代码如何编写?

引言: 性能优化一直是一个至关重要的议题。随着应用程序规模的不断增长和用户对性能的不断提升的要求,开发人员需要更加关注如何编写高性能的代码,以确保应用程序能够在各种情况下都能保持稳定和高效。编写高性能代码需要从多个方面入手&…

编译Nginx配置QUIC/HTTP3.0

1. 安装BoringSSL sudo apt update sudo apt install -y build-essential ca-certificates zlib1g-dev libpcre3 \ libpcre3-dev tar unzip libssl-dev wget curl git cmake ninja-build mercurial \ libunwind-dev pkg-configgit clone --depth1 https://github.com/google/b…

耐受强酸碱PFA试剂瓶高纯实验级进口聚四氟乙烯材质取样瓶

PFA取样瓶作为实验室中常备器皿耗材之一,主要用来盛放、储存和运输样品,根据使用条件不同,也可叫特氟龙试剂瓶、样品瓶、储样瓶、广口瓶、进样瓶等。广泛应用于半导体、新材料、多晶硅、硅材、微电子等行业。近年来随着新兴行业的快速发展&am…

软考 — 系统架构设计师 - 嵌入式真题

问题1: 可靠度表示系统在规定条件下,规定的时间内不发生失效的概率。 失效率表示系统运行到此时从未出现失效的情况下,单位时间内系统出现失效的概率 问题 2: 动态冗余又称为主动冗余,通过故障检测,故障定…

麒麟系统(kylin)安装ssh后,无法上传文件

1.赋予文件夹权限 chmod 777 filename 2.修改ssh配置文件 vi /etc/ssh/sshd_config 将Subsystem sftp /xxxxx 改为Subsystem sftp internal-sftp 重启服务 sudo service sshd restart 断开ssh连接,重新连接,即可正常上传文件

2012年认证杯SPSSPRO杯数学建模D题(第二阶段)人机游戏中的数学模型全过程文档及程序

2012年认证杯SPSSPRO杯数学建模 D题 人机游戏中的数学模型 原题再现: 计算机游戏在社会和生活中享有特殊地位。游戏设计者主要考虑易学性、趣味性和界面友好性。趣味性是本质吸引力,使玩游戏者百玩不厌。网络游戏一般考虑如何搭建安全可靠、丰富多彩的…

MindOpt APL向量化建模语法的介绍与应用(2)

前言 在数据科学、工程优化和其他科学计算领域中,向量和矩阵的运算是核心组成部分。MAPL作为一种数学规划语言,为这些领域的专业人员提供了强大的工具,通过向量式和矩阵式变量声明以及丰富的内置数学运算支持,大大简化了数学建模…

数学建模-Matlab中randperm函数及其双重进阶版

1.randperm函数的用法 (1)这种用法就是参数只有一个数字,代表的含义就是随机排列之后打印输出; 我们举例的数字是4,就会把1到4这4个数字随机打乱之后随机输出,每次运行结果都不一样 所有可能的情况是n的…

第十三章 OpenGL ES-RGB、HSV、HSL模型介绍

第十三章 OpenGL ES-RGB、HSV、HSL模型详细介绍 第一章 OpenGL ES 基础-屏幕、纹理、顶点坐标 第二章 OpenGL ES 基础-GLSL语法简单总结 第三章 OpenGL ES 基础-GLSL渲染纹理 第四章 OpenGL ES 基础-位移、缩放、旋转原理 第五章 OpenGL ES 基础-透视投影矩阵与正交投影矩阵…

面试:如何设计一个注册中心?

大家好,我是田哥 上周,一位群里的朋友反馈面试情况: 今天,给大家分享如何设计一个注册中心。其实这个问题,我之前在知识星球里分享过,可能是因为时间比较久了,加上这位朋友加入不久,…