《二叉树》——2

目录

前言:

树的节点个数:

树的叶子节点个数:

树的高度:        

树的第K层节点个数:

 二叉树查找值为x的节点:

 二叉树的销毁:

总结:


前言:

我们在之前的blog中对于前中后的遍历有了深层次的了解,相信通过递归展开图能更好的对递归算法有更深的理解,接下来我们将对剩下的二叉树内容进行补充,内容包含《树的节点个数》《树的叶子节点个数》《树的高度》《树的第K层节点个数》《二叉树查找值为x的节点》《二叉树的销毁》

上一篇blog:《二叉树》——1-CSDN博客

 

树的节点个数:

int TreeSize(TreeNode* root)//树的节点个数
{
	return (root == NULL) ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

也可以写成:

int TreeSize(TreeNode* root)//树的节点个数
{
    if (root == NULL)
    {
        return 0;
    }
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

我们在分析递归问题的时候一定要清楚“分治子问题”和“返回条件 ”。

对于这一个函数而言,我们可以理解为:

左子树的节点数 + 右子树的节点数 + 1(根节点)

同时当我们的root指针访问到NULL时要选择返回!

 

树的叶子节点个数:

首先先复习一下什么是叶子节点,

叶节点终端节点:度为0的节点称为叶节点

节点的度:一个节点含有的子树的个数称为该节点的度

int TreeLeafSize(TreeNode* root)//树的叶子节点个数
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

 我们首先还是需要了解此函数的“分治子问题”以及“返回条件”

“左子树叶子节点数” + “右子树叶子节点数”

条件有:

1、空树返回0

2、叶子节点返回1(root->left == NULL && root -> right == NULL)

树的高度:        

int TreeHeight(TreeNode* root)//树的高度
{
	if (root == NULL)
		return 0;

	int LeftHeight = TreeHeight(root->left);
	int RightHeight = TreeHeight(root->right);

	return (LeftHeight > RightHeight) ? (LeftHeight + 1) : (RightHeight + 1);
}

首先我们依然需要进行回顾,什么是高度?

节点的层次从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度深度:树中节点的最大层次

综上我们不难发现,所谓的高度,就是对左子树和右子树的高度进行比较,取最大的高度+根节点(即+1)即可,因为根节点是第一层。

同时我们要注意的是,切勿写成以下这种:

int TreeHeight(TreeNode* root)//树的高度
{
	if (root == NULL)
		return 0;

	return (TreeHeight(root->left) > TreeHeight(root->right)) ? (TreeHeight(root->left) + 1) : (TreeHeight(root->right) + 1);
}

这个代码的逻辑没有问题,但是问题就出现在每次比较的时候都要进行多次递归操作,多次开辟建立函数栈帧,数据一旦大或者较为难处理时往往会发生“栈溢出”

因此我们需要向第一次的代码那样定义两个变量来接受左子树的高度和右子树的高度。

 

树的第K层节点个数:

int TreeK(TreeNode* root, int k)//树的第K层节点个数
{
	if (root == NULL)
		return 0;
	if (root != NULL && k == 1)
		return 1;

	return TreeK(root->left, k - 1) + TreeK(root->right, k - 1);
}

还是一如既往找出“分治子问题”和“返回条件”

1、root为空时,返回0

2、若root不为空时,k == 1时返回1

这里提供一个思路,如图:

 

 

 以上就是下面代码的由来

return TreeK(root->left, k - 1) + TreeK(root->right, k - 1);

 二叉树查找值为x的节点:

TreeNode* TreeFind(TreeNode* root, BTDataType x)// 二叉树查找值为x的节点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	TreeNode* tmp1 = TreeFind(root->left, x);
	TreeNode* tmp2 = TreeFind(root->right, x);

	if (tmp1)
		return tmp1;
	if (tmp2)
		return tmp2;
	return NULL;
}

该函数与刚刚所讲的大相径庭

对于“分治子问题”不难得出

1、若是空则返回空

2、若root -> data = x则返回root

同样也是先在左子树中找,再在右子树找,这里一样也是定义一个临时变量来接受递归下来的返回值。

若tmp1 和tmp2均为NULL则代表没找到相应的节点,直接返回NULL

 

 二叉树的销毁:

void TreeDestory(TreeNode* root)// 二叉树销毁
{
	if (root == NULL)
		return;


	TreeDestory(root->left);
	TreeDestory(root->right);
	root->left = root->right = NULL;
	free(root);
}

对于上面的铺垫和讲解,相信对于销毁函数也不难理解。

同样也是先销毁左子树再去销毁右子树,最后当左右子树都销毁完后只剩下了一个根节点,则最后我们只需要将根节点进行释放和另左右指针指向空。

总结:

以上就是我们对于二叉树的链式结构的基本功能的实现了,其中设计许许多多的递归算法思想,对于刚开始的递归学习我们还需要不断学习和磨炼,思路最需要先锻炼出来,需要把分治子问题想清楚,

刚开始思路绕不明白的可以看看我以前写的一篇关于汉诺塔问题的blog:利用递归详解《汉诺塔游戏》_ucode汉诺塔游戏-CSDN博客

下节内容我们将涉及二叉树的层序遍历,利用栈来实现,希望大家可以继续坚持下来在二叉树的学习中。 

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

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

相关文章

用JavaFX写了一个简易的管理系统

文章目录 前言正文一、最终效果1.1 主页面1.2 动物管理页面-初始化1.3 动物管理页面-修改&新增1.4 动物管理页面-删除&批量删除 二、核心代码展示2.1 启动类2.2 数据库配置-db.setting2.3 日志文本域组件2.4 自定义表格视图组件2.5 自定义分页组件2.6 动物管理页面2.7 …

Git教程学习:09 Git分支

文章目录 1 分支的简介2 分支的相关操作2.1 分支的创建2.2 分支的切换2.3 分支的合并2.4 分支推送到远程2.5 分支的删除2.6 分支的重命名 3 分支开发工作流程3.1 长期分支3.2 短期分支 1 分支的简介 几乎所有的版本控制系统都以某种形式支持分支。使用分支意味着我们可以把我们…

计算机硬件 6.1BIOS

第六章 计算机基本程序 第一节 BIOS与CMOS芯片 一、认识BIOS 1.中文含义:基本输入输出系统。 2.材质:ROM(Flash Rom) 3.地位:是操作系统与硬件之间的接口。 4.存放内容:①基本输入输出系统;…

自动化防DDoS脚本

简介 DDoS (分布式拒绝服务攻击)是一种恶意的网络攻击,旨在通过占用目标系统的资源,使其无法提供正常的服务。在DDoS攻击中,攻击者通常控制大量的被感染的计算机或其他网络设备,同时将它们协调起来向目标系…

行业分析|中国人工智能发展的优势与差距

​人工智能,被誉为第四次工业革命的催化剂,吸引着发达国家和众多科技公司大举投入研发。我国积极构筑人工智能发展的先发优势,党的二十大报告提出推动战略性新兴产业集群,构建一系列新的增长引擎,包括信息技术、人工智…

基于变异混合蛙跳算法的车间调度最优化matlab仿真,可以任意调整工件数和机器数,输出甘特图

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 车间调度问题(JSSP)描述 4.2 蛙跳算法(SFLA)基本原理 4.2.1 初始化 4.2.2 局部搜索 4.2.3 全局信息交换 4.2.4 变异策略 4.2.5 终止…

编写后端代码,使用yakit将任意字典进行编码发送,后端解码输出到页面上

挂上代理(小狐狸): yakit中挂上劫持: 编写后端代码: 一个简单的登录代码 访问页面: 给予传参后看yakit劫持了没有 yakit劫持: 将劫持到的数据发送到webFuzzer: 右键选择标签/字典—…

c\c++队列的链式表示(对小白友好)

文章目录 1.链式队列的定义2.初始化3.判断空4.入队5. 出队6.打印全部元素7.源代码 本篇中的链式表示都是带头结点的链式表示。 1.链式队列的定义 typedef struct LinkNode { //链式队列的结点int data;struct LinkNode *next; }LinkNode; typedef struct { //链式…

如何创建以业务为中心的AI?

AI是企业的未来,这一趋势越来越明显。各种AI模型可以帮助企业节省时间、提高效率并增加收入。随着越来越多的企业采用AI,AI很快就不再是一种可有可无的能力,而是企业参与市场竞争的必备能力。 然而,作为一名业务决策者&#xff0c…

pcl之滤波器(二)

pcl滤波器 pcl一共是有十二个主要模块,详细了解可以查看官网。https://pcl.readthedocs.io/projects/tutorials/en/latest/#basic-usage 今天学习一下pcl的滤波器模块。 滤波器模块,官网一共是提供了6个例程,今天看第三个、第四个。 滤波…

(学习日记)2024.01.23:结构体、位操作和枚举类型

写在前面: 由于时间的不足与学习的碎片化,写博客变得有些奢侈。 但是对于记录学习(忘了以后能快速复习)的渴望一天天变得强烈。 既然如此 不如以天为单位,以时间为顺序,仅仅将博客当做一个知识学习的目录&a…

【学网攻】 第(3)节 -- 交换机配置聚合端口

文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻】 第(2)节 -- 交换机认识及使用 前言 网络已经成为了我们生活中不可或缺的一部分,它连接了世界各地的人们,让信息和资源得以自由流动。随着互联网的发展,我们可以通过网络学习、工作、娱乐…

最新综述!3D Gaussian Splatting

作者:小柠檬 | 来源:3DCV 在公众号「3DCV」后台,回复「原论文」可获取论文 文章介绍了3D高斯喷洒在场景重建和渲染中的应用,并探讨了其在机器学习和计算机视觉领域的潜在应用。文章还提供了3D高斯喷洒的基本原理和优化方法&#x…

MoEs学习

和多任务学习的mmoe很像哦(有空再学习一下)moe layer的起源:Switch Transformers paper MoE moe由两个结构组成: Moe Layer :这些层代替了传统 Transformer 模型中的前馈网络 (FFN) 层。MoE 层包含若干“专家”(例如…

解读顺网算力与AI,破局AIGC落地“最后一公里”

全球知名AI科学家吴恩达和李飞飞在CES 2024上预测,2024年将是AI技术继续深化的一年,将成为下一次数字或工业革命真正的变革性驱动力。吴恩达还预测了2024年AI可能的突破性进展,其中包括边缘AI。吴恩达对边缘AI寄予厚望,他认为在笔…

luceda ipkiss教程 57:画微环调制器

案例分享:画微环调制器 全部代码如下: from si_fab import all as pdk from ipkiss3 import all as i3class DC(i3.PCell):straight_length i3.PositiveNumberProperty(default200)radius i3.PositiveNumberProperty(default50)spacing i3.Positive…

坚持刷题 |对称二叉树

文章目录 题目考察点代码实现实现总结扩展用迭代的方式判断是否为对称二叉树递归和迭代的对比可能的扩展提问 坚持刷题,老年痴呆追不上我,今天真的好累,就不难为自己了,刷个简单级别的吧:对称二叉树 题目 101.对称二叉…

Scapy编程指南(基础概念)

Scapy编程指南(基础概念) Scapy是什么 Scapy是Python中一个非常强大的库,它专门用于处理、发送和捕获网络协议中的数据包,它允许开发人员通过Python代码构建、解析和发送自定义网络协议的数据包。Scapy提供了一种直观、灵活的方…

luffy商城项目(二)

路飞后端配置 二次封装response drf提供的Response对象,不能很方便的加入code和msg字段,自己封装一个Response类,以后都用我们自己封装的,方便咱们写code和msg 封装步骤: 1 在utils/common_response.py from rest_…

GitLab升级版本(任意用户密码重置漏洞CVE-2023-7028)

目录 前言漏洞分析影响范围查看自己的GitLab版本升级路程 升级过程13.1.1113.8.8 - 14.0.1214.3.614.9.5 - 16.1.6 前言 最近GitLab发了个紧急漏洞需要修复,ok接到命令立刻着手开始修复,在修复之前先大概了解一下这个漏洞是什么东西 漏洞分析 1、组件…