当前位置: 首页 > news >正文

【数据结构】二叉树的节点数,叶子数,第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节点,判断是否为完全二叉树等方法

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

前馈神经网络(FFNN)和多层感知机(MLP)

多层感知器&#xff08;MLP, Multi-Layer Perceptron&#xff09;和前馈神经网络&#xff08;Feed-Forward Neural Network, FFNN&#xff09;是深度学习中两个经常被使用的术语&#xff0c;它们经常被互换使用。让我们详细地了解这两个术语&#xff1a; 多层感知器 (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 下一步&#xff0c;点击完成 开启安装 设置语言 去掉下载更新选项 继续 点击restart now 输入密码 出现下图说明安装成功&#xff0c;可以畅快的使用了...

Appium混合页面点击方法tap的使用

原生应用开发&#xff0c;是在Android、IOS等移动平台上利用官方提供的开发语言、开发类库、开发工具进行App开发&#xff1b;HTML5&#xff08;h5&#xff09;应用开发&#xff0c;是利用Web技术进行的App开发。目前&#xff0c;市面上很多app都是原生和h5混合开发&#xff0c…...

求解灰度直方图,如何绘制灰度直方图(数字图像处理大题复习 P1)

文章目录 1. 画 X 轴2. 画直方图3. Complete 视频原链接 数字图像处理期末考试大题 B站链接 1. 画 X 轴 2. 画直方图 有几个 0 就在图上画多高&#xff0c;同理有几个 1 &#xff0c;X1 的地方就画多高 3. Complete 这里的情况比较平均&#xff0c;一般来说不会这么平均&a…...

8种结构型设计模式对比

一、适配器模式 简介 适配器模式是一种结构型设计模式&#xff0c;它用于将不兼容的接口转换为可兼容的接口。适配器模式允许两个不兼容的类能够协同工作&#xff0c;通过将一个类的接口转换为另一个类所期望的接口形式。这样就能够在不修改现有代码的情况下&#xff0c;使两…...

【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丢失怎么办?(五种方法快速解决)

首先&#xff0c;让我们来了解一下msvcp120.dll这个文件。msvcp120.dll是一个动态链接库文件&#xff0c;它是Microsoft Visual C 2012 Redistributable Package的一部分。这个文件的作用是支持一些应用程序的运行&#xff0c;例如游戏、办公软件等。当我们在使用这些软件时&am…...

eslint写jsx报错

eslint写jsx报错 ChatGPT提示 在写JSX时&#xff0c;ESLint可能会报出一些语法错误&#xff0c;这些错误通常是由于ESLint默认配置中不支持JSX语法导致的。为了解决这些错误&#xff0c;我们需要在ESLint配置文件中启用对JSX语法的支持。 首先&#xff0c;需要安装eslint-pl…...

最新适合小白前端 Javascript 高级常见知识点详细教程(每周更新中)

1. window.onload 窗口或者页面的加载事件&#xff0c;当文档内容完全加载完成会触发的事件&#xff08;包括图形&#xff0c;JS脚本&#xff0c;CSS文件&#xff09;&#xff0c;就会调用处理的函数。 <button>点击</button> <script> btn document.q…...

积分值和面积、对称性

积分的基本含义要从积分符号说起&#xff0c;积分号含有加号的意思&#xff0c; ∫ a b f ( x ) d x \int ^b_af(x)dx ∫ab​f(x)dx可以理解为&#xff1a;区间[a,b]无限细分为无穷多个dx,无穷多个f(x)乘以dx的累积和。根据上面的描述&#xff0c;面积可以理解为 ∫ a b ∣ f (…...

springboot 整合es

Spring Boot可以轻松地与Elasticsearch进行整合&#xff0c;以实现高效的搜索和分析功能。 以下是如何在Spring Boot应用程序中使用Elasticsearch的步骤&#xff1a; 1.添加依赖项 在pom.xml文件中添加以下依赖项&#xff1a; <dependency><groupId>org.spring…...

MyBatisPlus使用自定义JsonTypeHandler实现自动转化JSON

个人主页&#xff1a;金鳞踏雨 个人简介&#xff1a;大家好&#xff0c;我是金鳞&#xff0c;一个初出茅庐的Java小白 目前状况&#xff1a;22届普通本科毕业生&#xff0c;几经波折了&#xff0c;现在任职于一家国内大型知名日化公司&#xff0c;从事Java开发工作 我的博客&am…...

LeetCode 2097. 合法重新排列数对【欧拉通路,DFS】2650

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

学习笔记-接口测试(postman、jmeter)

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

如何高效批量查询快递单号,提高工作效率?

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

12万汉语源流词典汉字记性ACCESS\EXCEL数据库

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

深度解剖数据在队列的应用

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大一&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 望小伙伴们点赞&#x1f44d;收藏✨加关注哟&#x1f495;&#x1…...

IMX6ULL移植篇-Linux内核源码目录分析二

一. Linux内核源码目录 本文继续来具体说明 Linux内核源码的一些重要文件含义。 本文续上一篇文章&#xff0c;地址如下&#xff1a; IMX6ULL移植篇-Linux内核源码目录分析一_凌肖战的博客-CSDN博客 二. Linux内核源码目录分析 9. init 目录 此目录存放 Linux 内核启动的…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...