【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 一、二叉数的结构体
- 二、构建二叉树,供后续测试使用
- 三、二叉树销毁
- 四、构建节点
- 五、二叉树的高度:
- 1.代码:
- 2.测试结果:
- 二叉树节点个数
- 1.代码:
- 2.测试结果:
- 六、二叉树叶子节点个数
- 1.代码:
- 2.测试结果:
- 七、二叉树第k层节点个数
- 1.代码:
- 2.测试结果:
- 八、二叉树查找值为x的节点
- 1.代码:
- 2.测试结果:
- 九、判断二叉树是否是完全二叉树
- 1.代码:
- 2.测试结果:
- 十、补充:队列代码
- Queue.h
- Queue.c
一、二叉数的结构体
每一个节点有
1.数据域_data
;
2.指向左子树的指针:_left
3.指向右子树的执指针:_right
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
二、构建二叉树,供后续测试使用
三、二叉树销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);
}
四、构建节点
//构建节点BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->_data = x;node->_left = NULL;node->_right = NULL;return node;
}
五、二叉树的高度:
fmax
函数的头文件:<math.h>
思路:每次选择左右子树中大的那一棵树,对其+1;
1.代码:
//树的高度int TreeHeight(BTNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->_left), TreeHeight(root->_right)) + 1;
}
2.测试结果:
二叉树节点个数
思路:如果当前节点为NULL;则返回0;如果不是NULL;则向左右子树递归并+1;
1.代码:
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
2.测试结果:
六、二叉树叶子节点个数
思路:
1.向下递归的条件是当前节点左或者右节点有一个为空,一个不为空。
2.当不满足下面的if语句时,就会return 左右两个节点,从而递归继续向下寻找叶子节点,
3.直到当前节点为空时,就停止返回0;或者找到叶子节点,返回1
1.代码:
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{//向下递归的条件是当前节点左或者右节点有一个为空,一个不为空。//当不满足下面的if语句时,就会return 左右两个节点,从而递归继续向下寻找叶子节点,//直到当前节点为空时,就停止返回0;或者找到叶子节点,返回1if (root == NULL)return 0;if (root->_left == NULL && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
2.测试结果:
七、二叉树第k层节点个数
思路:
1.当找到第k==1,就返回1,意思是第k层个数+1;
2.当节点为空时,就结束向下递归,开始往回走。
3.如果不满足if条件,就继续向下递归。
1.代码:
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//当找到第k==1,就返回1,意思是第k层个数+1;//当节点为空时,就结束向下递归,开始往回走。//如果不满足if条件,就继续向下递归。if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
2.测试结果:
八、二叉树查找值为x的节点
思路;
1.当root==NULL时,说明当前子树中没有没有找到,返回NULL
2.当root->_data==x时,就return 当前节点,停止向下递归,开始向上回。
3.如果不满足上面两个if条件,就向下递归左,再右节点,
4.如果root->_data == x成立,返回的就不是空值通过if判断,并返回tmp。
5.在一次递归中,如果没有找到等于x的节点,和root=NULL两个条件时,就返回NULL;
1.代码:
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//当root==NULL时,说明当前子树中没有没有找到,返回NULL//当root->_data==x时,就return 当前节点,停止向下递归,开始向上回。//如果不满足上面两个if条件,就向下递归左,再右节点,//如果root->_data == x成立,返回的就不是空值通过if判断,并返回tmp。//在一次递归中,如果没有找到等于x的节点,和root=NULL两个条件时,就返回NULL;if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* tmp = NULL;tmp=BinaryTreeFind(root->_left, x);if (tmp)return tmp;tmp = BinaryTreeFind(root->_right, x);if (tmp)return tmp;return NULL;
}
2.测试结果:
查询二叉树中节点值=3的节点。
查询
九、判断二叉树是否是完全二叉树
思路:
1.开始层序遍历,直到遇到NULL为止。
2.从遇到NULL的位置开始继续向下遍历,如果还能遇到非空节点,则说明不是完全二叉树。
1.代码:
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Que q;QueueInit(&q);//开始层序遍历,直到遇到NULL为止if (root)QueuePush(&q,root);while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);if (tmp == NULL)return false;QueuePush(&q,tmp->_left);QueuePush(&q,tmp->_right);QueuePop(&q);}//从遇到NULL的位置开始继续向下遍历,如果还能遇到非空节点,则说明不是完全二叉树。while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
2.测试结果:
十、补充:队列代码
Queue.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
Queue.c
#include "Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
相关文章:

【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
前馈神经网络(FFNN)和多层感知机(MLP)
多层感知器(MLP, Multi-Layer Perceptron)和前馈神经网络(Feed-Forward Neural Network, FFNN)是深度学习中两个经常被使用的术语,它们经常被互换使用。让我们详细地了解这两个术语: 多层感知器 (MLP): M…...

EasySwipeMenuLayout - 独立的侧滑删除
官网 GitHub - anzaizai/EasySwipeMenuLayout: A sliding menu library not just for recyclerview, but all views. 项目介绍 A sliding menu library not just for recyclerview, but all views. Recommended in conjunction with BaseRecyclerViewAdapterHelper Feature…...

优麒麟下载、安装、体验
下载 官网 优麒麟 点击增强版、或者基础版进行下载 虚拟机安装 选择镜像 修改名称和存储路径 设置为50G 下一步,点击完成 开启安装 设置语言 去掉下载更新选项 继续 点击restart now 输入密码 出现下图说明安装成功,可以畅快的使用了...

Appium混合页面点击方法tap的使用
原生应用开发,是在Android、IOS等移动平台上利用官方提供的开发语言、开发类库、开发工具进行App开发;HTML5(h5)应用开发,是利用Web技术进行的App开发。目前,市面上很多app都是原生和h5混合开发,…...

求解灰度直方图,如何绘制灰度直方图(数字图像处理大题复习 P1)
文章目录 1. 画 X 轴2. 画直方图3. Complete 视频原链接 数字图像处理期末考试大题 B站链接 1. 画 X 轴 2. 画直方图 有几个 0 就在图上画多高,同理有几个 1 ,X1 的地方就画多高 3. Complete 这里的情况比较平均,一般来说不会这么平均&a…...
8种结构型设计模式对比
一、适配器模式 简介 适配器模式是一种结构型设计模式,它用于将不兼容的接口转换为可兼容的接口。适配器模式允许两个不兼容的类能够协同工作,通过将一个类的接口转换为另一个类所期望的接口形式。这样就能够在不修改现有代码的情况下,使两…...

【PX4】Ubuntu20.04+ROS Noetic 配置PX4-v1.12.2和Gazebo11联合仿真环境【教程】
【PX4】Ubuntu20.04ROS Noetic 配置PX4-v-v1.12.2和Gazebo11联合仿真环境【教程】 文章目录 【PX4】Ubuntu20.04ROS Noetic 配置PX4-v-v1.12.2和Gazebo11联合仿真环境【教程】0. 安装UbuntuROS1. 安装依赖2. 安装QGC地面站3. 配置PX4-v1.12.23.1 安装PX43.2 测试PX4是否成功安装…...

msvcp120.dll丢失怎么办?(五种方法快速解决)
首先,让我们来了解一下msvcp120.dll这个文件。msvcp120.dll是一个动态链接库文件,它是Microsoft Visual C 2012 Redistributable Package的一部分。这个文件的作用是支持一些应用程序的运行,例如游戏、办公软件等。当我们在使用这些软件时&am…...
eslint写jsx报错
eslint写jsx报错 ChatGPT提示 在写JSX时,ESLint可能会报出一些语法错误,这些错误通常是由于ESLint默认配置中不支持JSX语法导致的。为了解决这些错误,我们需要在ESLint配置文件中启用对JSX语法的支持。 首先,需要安装eslint-pl…...

最新适合小白前端 Javascript 高级常见知识点详细教程(每周更新中)
1. window.onload 窗口或者页面的加载事件,当文档内容完全加载完成会触发的事件(包括图形,JS脚本,CSS文件),就会调用处理的函数。 <button>点击</button> <script> btn document.q…...

积分值和面积、对称性
积分的基本含义要从积分符号说起,积分号含有加号的意思, ∫ a b f ( x ) d x \int ^b_af(x)dx ∫abf(x)dx可以理解为:区间[a,b]无限细分为无穷多个dx,无穷多个f(x)乘以dx的累积和。根据上面的描述,面积可以理解为 ∫ a b ∣ f (…...
springboot 整合es
Spring Boot可以轻松地与Elasticsearch进行整合,以实现高效的搜索和分析功能。 以下是如何在Spring Boot应用程序中使用Elasticsearch的步骤: 1.添加依赖项 在pom.xml文件中添加以下依赖项: <dependency><groupId>org.spring…...
MyBatisPlus使用自定义JsonTypeHandler实现自动转化JSON
个人主页:金鳞踏雨 个人简介:大家好,我是金鳞,一个初出茅庐的Java小白 目前状况:22届普通本科毕业生,几经波折了,现在任职于一家国内大型知名日化公司,从事Java开发工作 我的博客&am…...
LeetCode 2097. 合法重新排列数对【欧拉通路,DFS】2650
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

学习笔记-接口测试(postman、jmeter)
目录 一、什么是接口测试 二、前端和后端 三、get请求和post请求的区别 四、cookie和session 五、接口测试的依据 六、HTTP状态码 七、通用接口用例 八、postman接口测试 九、Jmeter接口测试 一、什么是接口测试 通常做的接口测试指的是系统对外的接口,比…...

如何高效批量查询快递单号,提高工作效率?
在日常生活中,快递单号的查询是一项常规任务。过去,这项任务需要通过人工一个一个地在快递平台上查询,既耗时又费力。然而,随着科技的发展,我们有了更多的工具可以帮助我们高效地完成这项任务。本文将介绍如何使用固乔…...

12万汉语源流词典汉字记性ACCESS\EXCEL数据库
《12万汉语源流词典汉字记性ACCESS数据库》在继承前人经验的基础上,注意吸收今人的研究成果,注重形音义的密切配合,尽可能历史地、正确地反映汉字形音义的发展。在字形方面,简要说明其结构的演变。语义解释遵循古今语义的发展变化…...

深度解剖数据在队列的应用
> 作者简介:დ旧言~,目前大一,现在学习Java,c,c,Python等 > 座右铭:松树千年终是朽,槿花一日自为荣。 > 望小伙伴们点赞👍收藏✨加关注哟💕…...
IMX6ULL移植篇-Linux内核源码目录分析二
一. Linux内核源码目录 本文继续来具体说明 Linux内核源码的一些重要文件含义。 本文续上一篇文章,地址如下: IMX6ULL移植篇-Linux内核源码目录分析一_凌肖战的博客-CSDN博客 二. Linux内核源码目录分析 9. init 目录 此目录存放 Linux 内核启动的…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...

【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...