首页 > 其他分享 >数据结构 ——— 计算链式二叉树叶子节点的个数以及计算链式二叉树的高度

数据结构 ——— 计算链式二叉树叶子节点的个数以及计算链式二叉树的高度

时间:2024-11-05 10:50:13浏览次数:5  
标签:right BTNode 二叉树 计算 链式 root 节点

目录

前言

链式二叉树示意图​编辑

手搓一个链式二叉树

计算链式二叉树的叶子节点个数

计算链式二叉树的高度 


前言

上一章学习了计算链式二叉树的节点个数

数据结构 ——— 计算链式二叉树节点的个数-CSDN博客

接下来学习的是计算链式二叉树叶子节点的个数以及计算链式二叉树的高度 


链式二叉树示意图


手搓一个链式二叉树

代码演示:

// 数据类型
typedef int BTDataType;
 
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
    BTDataType data; //每个节点的数据
 
    struct BinaryTreeNode* left; //指向左子树的指针
 
    struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
 
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 
    // 判断是否申请成功
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
 
    // 初始化
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
 
    return newnode;
}
 
BTNode* CreatBinaryTree()
{
    BTNode* n1 = BuyNode(1);
    assert(n1);
    BTNode* n2 = BuyNode(2);
    assert(n2);
    BTNode* n3 = BuyNode(3);
    assert(n3);
    BTNode* n4 = BuyNode(4);
    assert(n4);
    BTNode* n5 = BuyNode(5);
    assert(n5);
    BTNode* n6 = BuyNode(6);
    assert(n6);
 
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
 
    return n1;
}

计算链式二叉树的叶子节点个数

代码演示:

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

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

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

代码解析:

当 root 为空时,说明没有节点,返回 0
当 root 的 left 和 root 的 right 为空时,就说明 root 为叶子节点,返回 1
通过 BTreeLeafSize 函数递归找到二叉树的所有叶子节点

大致走读代码(以上图为例):

进入函数,root 为 1 节点,那么就会走 BTreeLeafSize(root->left)
直到走到 root 为 3 节点,root 的 left 和 root 的 right 都为空,那么说明当前 root 为叶节点
返回 1 ,注意:并不是直接返回,而是返回到上一层,也就是 root 为 2 节点时
因为 2 节点的 right 为空,所当 root 为 2 节点的 right 时,返回 0
返回到 root 为 节点 1 时,那么就会走 BTreeLeafSize(root->right)………………
最后递归完之后,返回的值,就是链式二叉树的叶子节点个数

代码验证:


计算链式二叉树的高度(分治算法)

代码演示:

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

	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

代码解析:

当 root 为空时,说明没有节点,返回 0
创建两个变量用来记录左右子树的节点高度
最后再比较,返回高的那个节点的高度,也就是整个二叉树的高度

大致走读代码(以上图为例):

进入函数,root 为 1 节点,先走 BTreeHeight(root->left)
直到 root 为 3 节点的 left 节点,为空返回 0,返回到 3 节点
再走 BTreeHeight(root->right) ,也就是 3 节点的 right 节点,同样为空返回 0
此时的 leftHeight 和 rightHeight 同样为 0,返回 0+1
也就是返回到 root 为 2 节点的时候,且 2 节点的 right 为空,返回 0
此时 2 节点的 leftHeight 为 1,rightHeight 为 0,比较后,返回 1+1
返回的 2 返回到 root 为 1节点的时候,再走 BTreeHeight(root->right)………………
直到递归走完,最后返回的结果就是左右子树比较大的值,也就是二叉树的高

代码验证:

标签:right,BTNode,二叉树,计算,链式,root,节点
From: https://blog.csdn.net/weixin_55341642/article/details/143489072

相关文章

  • 0基础读顶会论文—Kappa:一种用于无服务器计算的编程框架
    原文链接代码:快速使用kappa首先的首先,可以先去了解一下lambda架构Abstract在本文中提出了Kappa,一个简化无服务器开发的框架。它使用检查点来处理lambda函数超时,并提供并发机制,实现并行计算和协调1Introduction无服务器计算是一种新的云范例,在这种范例中,租户不是配置虚拟机(V......
  • 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-11-01
    计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-11-01目录文章目录计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-11-01目录1.APerspectiveforAdaptingGeneralistAItoSpecializedMedicalAIApplicationsandTheirChallenges2.S......
  • 就是这个样的粗爆,手搓一个计算器:黄金重量计算器
        作为程序员,没有合适的工具,就得手搓一个,PC端,移动端均可适用。废话不多说,直接上代码。HTML:<divclass="calculator"><labelfor="volume">体积(单位:立方厘米):</label><inputid="volume"required=""step="0.01"type="numb......
  • 基于Liquid State Machine的时间序列预测:利用储备池计算实现高效建模
    LiquidStateMachine(LSM) 是一种 脉冲神经网络(SpikingNeuralNetwork,SNN) ,在计算神经科学和机器学习领域中得到广泛应用,特别适用于处理 时变或动态数据。它是受大脑自然信息处理过程启发而提出的一种 脉冲神经网络 。设想你正处于一片平静的湖面,四周环绕着高山......
  • SSM动漫论坛系统-计算机毕业设计源码52529
    目录1绪论1.1研究背景和意义1.2国内外研究现状1.3论文结构与章节安排1.4SSM框架介绍2 系统分析2.1可行性分析2.1.1技术可行性分析2.1.2经济可行性分析2.1.3操作可行性分析2.2系统功能分析2.2.1功能性分析2.2.2非功能性分析2.3 系统用例分......
  • (3)---【C语言】【GL库】【计算机图形学】DEV C++ 平台openGL库 下的画线图案设计 房
    声明:        由于本人是一名学生,现阶段还要完成学业,所以我们每周假期再回!谢谢大家理解和支持!上篇上手实践  运行结果 实现代码#include<windows.h>#defineGLUT_DISABLE_ATEXIT_HACK//处理不同系统的配置问题的宏#include<GL/glut.h>#include<std......
  • 知识点:树中结点的度以及叶子结点(度为0的结点)的计算
    知识点:这道题目考察的是树的基本概念和性质,特别是关于树中结点的度以及叶子结点(度为0的结点)的计算。知识点相关内容:树(Tree):树是一种特殊的图,它是一个无向图,由结点(或称为顶点)和边组成,满足以下条件:任意两个结点之间有且仅有一条路径。树中的结点可以分为根结点、分支结点和叶......
  • java计算机毕业设计基于SpringBoot的模具管理(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景在现代制造业中,模具扮演着极为关键的角色,广泛应用于汽车、电子、家电等众多行业。随着工业4.0的推进,制造业朝着智能化、高效化发展,模具管理面临......
  • java计算机毕业设计基于的滑雪场学具租赁管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着社会经济的发展以及人们生活水平的提高,滑雪运动逐渐成为大众喜爱的休闲娱乐项目。滑雪场的规模不断扩大,雪具租赁业务量也日益增长。然而,传统......
  • java计算机毕业设计在线投票数据分析平台研究与设计(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着互联网的迅速发展,在线投票活动日益频繁,涵盖了社会的各个领域,如商业营销中的产品评选、娱乐行业的选秀投票、学术领域的成果评价以及各类社会......