当前位置: 首页 > 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 内核启动的…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...