【数据结构】二叉树的节点数,叶子数,第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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/137505.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源媒体浏览器Kyoo

什么是 Kyoo &#xff1f; Kyoo 是一款开源媒体浏览器&#xff0c;可让您流式传输电影、电视节目或动漫。它是 Plex、Emby 或 Jellyfin 的替代品。Kyoo 是从头开始创建的&#xff0c;它不是一个分叉。一切都将永远是免费和开源的。 软件特性&#xff1a; 管理您的电影、电视剧…

极致鸿蒙2.0——华为MatePad系列安装AidLux,一个自带vscode的Python编译环境

看着刚刚人入手的华为鸿蒙系统MatePad11平板&#xff0c;是如此的美轮美奂&#xff0c;但是总感觉少了点什么&#xff0c;少了点什么呢&#xff1f;是编程环境&#xff0c;我爱MatePad&#xff0c;也爱编程&#xff0c;那如果可以在MatePad上编程&#xff0c;会发生什么&#x…

性能测试 —— Tomcat监控与调优:status页监控

Tomcat服务器是一个免费的开放源代码的Web 应用服务器&#xff0c;Tomcat是Apache 软件基金会(Apache Software Foundation)Jakarta 项目中的一个核心项目&#xff0c;由Apache、Sun 和其他一些公司及个人共同开发而成。 Tomcat是一个轻量级应用服务器&#xff0c;在中小型系统…

车载通信架构 —— SOME/IP 协议概述

车载通信架构 —— SOME/IP 协议概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 对学习而言,学习之后的思考、思考之后的行动、行动之后的改变更重要,如果不盯住内层的改变量,那么在表层投…

Java下打印直角三角型(另一个方向)

代码如下&#xff1a; public class MyWork {public static void main(String[] args) {int num 5;for (int i 0; i < num; i) {for (int j 0; j < i; j) {System.out.print("-");}for (int j 0; j < num - i; j) {System.out.print("*");}S…

OceanBase杨传辉传递亚运火炬:国产数据库为“智能亚运”提供稳稳支持

9 月 14 日&#xff0c;亚运火炬传递到了浙江台州&#xff0c;OceanBase 的 CTO 杨传辉作为火炬手交接了第 89 棒火炬。 2010 年&#xff0c;杨传辉作为创始成员之一参与自研原生分布式数据库 OceanBase。十年磨一剑&#xff0c;国产数据库 OceanBase 交出了一张优秀的成绩单&a…

实施主品牌进化战略(一):确立主品牌进化架构

主品牌进化战略&#xff0c;即以主品牌为核心创造、巩固、转化竞争优势应对竞争环境变化&#xff0c;避免衰退&#xff0c;回归增长&#xff0c;让主品牌进化的方法论体系。主品牌进化战略制定要从 4 个方面出发&#xff1a;确立主品牌进化架构、更新和明确主品牌竞争方向、建立…

【100天精通Python】Day67:Python可视化_Matplotlib 3D绘图,绘制3D曲面图、3D填充图,3D极坐标图,示例+代码

目录 1 绘制曲面图 2 绘制3D填充图 3 绘制极坐标图 1 绘制曲面图 当绘制3D曲面图时&#xff0c;mpl_toolkits.mplot3d 模块中的 Axes3D 对象提供了多种方法来呈现不同类型的曲面图。以下是一些常见的3D曲面图类型以及示例&#xff1a; 曲面图&#xff1a;使用 plot_surface …

修炼离线:(三)sqoop插入hbase 报错权限问题

一&#xff1a;报错现象。 二&#xff1a;解决方式。 方法一&#xff1a;修改文件所有者。 切换hadoop用户&#xff1a;export HADOOP_USER_NAMEhdfs hadoop fs -chown -R root:root /方法二&#xff1a;修改权限 切换hadoop用户&#xff1a;export HADOOP_USER_NAMEhdfs ha…

Proteus的编译运行(以AT89C51为例)

最近&#xff0c;突然又用到了Proteus,之前还是大三上的时候上微机原理的时候用到过&#xff0c;今天记录一下如何在Proteus中编写代码&#xff0c;编译运行。 首先&#xff0c;选中AT89C51芯片&#xff0c;右键选择编辑源代码。 选择芯片的系列与对应的编译器&#xff0c;这里…

OpenCV实现图像去水印功能(inpaint)

水印定位 需要根据图像特征获取水印的位置。 如图所示&#xff0c;图像左下角、右下角有水印。第一步&#xff0c;我们首先得定位水印所在位置。 Mat gray;cvtColor(src, gray, COLOR_BGR2GRAY);//图像二值化&#xff0c;筛选出白色区域部分Mat thresh;threshold(gray, thres…

在VMware虚拟机中固定CentOS系统ip(使用桥接模式)

目录 一、前置说明二、前置准备2.1、切换虚拟机网络为桥接模式2.2、查看本机网络信息 三、配置CentOS系统IP3.1、进入系统输入ip addr 查看本机网络配置名称3.2、查看网络配置目录&#xff0c;网络配置文件名称3.3、修改网络配置文件 ifcfg-ens33 固定IP3.4、重启网络 一、前置…

增强企业的网络防御:从哪里开始

在当今的数字环境中&#xff0c;网络安全事件已经变得异常普遍&#xff0c;影响着各种规模和行业的企业。中小型企业 (SME) 不再局限于知名组织&#xff0c;由于其潜在的漏洞和应对复杂威胁的资源有限&#xff0c;越来越多地成为网络犯罪分子的目标。 2023 年第一季度&#xf…

计算机是如何工作的下篇

操作系统&#xff08;Operating System ) 操作系统是一组做计算机资源管理的软件的统称。目前常见的操作系统有&#xff1a;Windows系列、Unix系列、Linux系列、OSX系列、Android系列、iOS系列、鸿蒙等. 操作系统由两个基本功能&#xff1a; 对下,要管理硬件设备. 对上,要给…

单片机第三季-第三课:STM32开发板原理图、配置、浮点运算单元

目录 1&#xff0c;开发板原理图 2&#xff0c;浮点运算单元&#xff08;FPU&#xff09; 1&#xff0c;开发板原理图 课程视频比较早&#xff0c;介绍了三款开发板。观看视频时用的开发板说和51单片机共板的STM32核心板&#xff0c;将51单片机从底座拆下来后&#xff0c;安…

云原生Kubernetes:K8S存储卷

目录 一、理论 1.存储卷 2.emptyDir 存储卷 3.hostPath卷 4.NFS共享存储 二、实验 1.emptyDir 存储卷 2.hostPath卷 3.NFS共享存储 三、问题 1.生成pod一直pending 四、总结 一、理论 1.存储卷 &#xff08;1&#xff09;概念 容器磁盘上的文件的生命周期是短暂的…

如何玩转CSDN AI工具集

前言 人工智能生成内容&#xff08;AIGC&#xff09;是当下最具有前景的技术领域之一。AI能够以惊人的速度和准确度生成各种类型的内容&#xff0c;完成文章翻译、代码生成、AI对话、插图创作等工作&#xff0c;带来了许多令人兴奋的机遇。 本文将介绍CSDN AI工具集的基本使用…

Bard人工智能9月19日重大更新

1、巴德现在可以回复来自谷歌地图、航班、酒店和YouTube的实时信息&#xff0c;因此您可以在一个地方完成更多工作。 2、Bard 可能会与其他服务共享您的部分对话和其他相关信息&#xff0c;例如您的位置。这些服务可能会使用该信息进行改进&#xff0c;即使您以后删除了您的 Ba…

湖南湘潭家具3D轮廓扫描测量家居三维数字化外观逆向设计-CASAIM中科广电

随着科技的不断进步&#xff0c;CASAIM三维扫描技术在各个行业中得到了广泛应用&#xff0c;家具行业也不例外。传统的家具设计和展示方式已经无法满足现代消费者的个性化、多元化需求&#xff0c;而三维扫描技术的出现为家具行业带来了新的机遇和可能性。 家具表面有雕刻图案…

机器学习第九课--随机森林

一.什么是集成模型 对于几乎所有的分类问题(图像识别除外&#xff0c;因为对于图像识别问题&#xff0c;目前深度学习是标配)&#xff0c;集成模型很多时候是我们的首选。比如构建一个评分卡系统&#xff0c;业界的标配是GBDT或者XGBoost等集成模型&#xff0c;主要因为它的效…