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

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 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Docker 运行 Kafka 带 SASL 认证教程

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

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

OPENCV形态学基础之二腐蚀

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

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

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

【C++进阶篇】智能指针

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