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

数据结构-二叉树

数据结构-二叉树

    • 二叉树的概念
    • 二叉树的遍历分类
  • 建立二叉树,并遍历
    • 二叉树的最小单元
    • 二叉树的最小单元初始化
    • 初始化二叉树
    • 前序遍历的实现
    • 中序遍历的实现
    • 后序遍历的实现
    • 计算节点的个数
    • 计算树的深度
    • 求第k层的个数
    • 查找二叉树的元素
    • 分层遍历
  • 全部代码如下

二叉树的概念

在这里插入图片描述

二叉树的遍历分类

有前序遍历,中序遍历,后序遍历和层序遍历
在这里插入图片描述

规则

1.遇到根可以直接访问根
2.遇到左子树,右子树,不可以直接访问,要将其看作一颗新的二叉树,按遍历规则,再次循环,直至左子树或右子树为空,则可访问空。

前序遍历
在这里插入图片描述
中序遍历和后序遍历
中序遍历:
三者访问根的时机不同

层序遍历:一层一层的进行

1 2 4 3 5 6

建立二叉树,并遍历

二叉树的最小单元

根,左子树和右子树

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二叉树的最小单元初始化

BTNode* BuyNode(BTDataType x)
{BTNode* node=(BTNode*)malloc(sizeof(BTNode));if (node==NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

初始化二叉树

BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right=node6;return node1;
}

前序遍历的实现

函数的回归条件为root为空,或者函数正常结束
按照顺序依次为:根,左子树,右子树

void PreOrder(BTNode* root)
{if (root==NULL){printf("NULL ");return;}//root,left,rightprintf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}

递归调用展开图
在这里插入图片描述

结果如下:
在这里插入图片描述

中序遍历的实现

函数的回归条件为root为空,或者函数正常结束
按照顺序依次为:左子树,根,右子树

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

后序遍历的实现

函数的回归条件为root为空,或者函数正常结束
按照顺序依次为:左子树,右子树,根

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

计算节点的个数

利用分治法求节点的个数,只有节点存在时,才会+1,并返回下层的统计个数
在这里插入图片描述

int TreeSize(BTNode* root)
{if (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+1;}
}

执行结果如下:
在这里插入图片描述

计算树的深度

在这里插入图片描述

int TreeHeight(BTNode* root)
{if (root==NULL){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ?leftHeight + 1 :rightHeight + 1;
}

代码执行结果如下:
在这里插入图片描述

求第k层的个数

在这里插入图片描述

int TreeLevel(BTNode* root,int k)
{if (root==NULL){return 0;}if (k==1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}

运行结果如下:
在这里插入图片描述

查找二叉树的元素

在这里插入图片描述

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){return root;}BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}return NULL;
}

结果如下:
在这里插入图片描述

分层遍历

利用队列,先将根push,进入循环,可pop,再将层子节点push,依次循环。安照队列先进先出的原则,可实现分层打印

void LevelOrder(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q,root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ",front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

结果如下:

在这里插入图片描述
判断是否为完全二叉树

bool TreeComplete(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front==NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

全部代码如下

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node=(BTNode*)malloc(sizeof(BTNode));if (node==NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);//BTNode* node6 = BuyNode(6);//node1->left = node2;//node1->right = node4;//node2->left = node3;//node4->left = node5;//node4->right=node6;node1->left = node2;node1->right = node3;node2->left = node4;//node4->left = node5;node3->right = node5;return node1;
}void PreOrder(BTNode* root)
{if (root==NULL){printf("NULL ");return;}//root,left,rightprintf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}//分治法求节点的个数
int TreeSize(BTNode* root)
{if (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+1;}
}int TreeHeight(BTNode* root)
{if (root==NULL){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ?leftHeight + 1 :rightHeight + 1;
}int TreeLevel(BTNode* root,int k)
{if (root==NULL){return 0;}if (k==1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}//查找元素
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){return root;}BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}return NULL;
}//分层遍历
void LevelOrder(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q,root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ",front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}//判断是不是完全二叉树
bool TreeComplete(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front==NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");printf("%d",TreeSize(root));printf("\n");printf("%d ", TreeHeight(root));printf("\n");printf("%d ", TreeLevel(root,3));printf("\n");printf("%p ", TreeFind(root, 5));printf("\n");printf("%p ", TreeFind(root, 60));printf("\n");LevelOrder(root);printf("TreeComplete: %d", TreeComplete(root));//二维数组return 0;
}

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"void QueueInit(Quene* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Quene* 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(Quene* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode==NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->data = x;//需要判断队列中是否有元素if (pq->head==NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Quene* pq)
{assert(pq);//确保有队列assert(pq->head != NULL);//确保队列不为空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--;
}int QueueSize(Quene* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Quene* pq)
{assert(pq);return pq->size==0;
}QDataType QueueFront(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef struct BinaryTreeNode* QDataType;//单个节点
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;//整个队列
typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;//初始化
void QueueInit(Quene* pq);
//销毁
void QueueDestroy(Quene* pq);//入队
void QueuePush(Quene* pq, QDataType x);
//出队
void QueuePop(Quene* pq);//计算队列中元素的个数
int QueueSize(Quene* pq);
//判断队列是否为空
bool QueueEmpty(Quene* pq);//队列中的队头元素
QDataType QueueFront(Quene* pq);
//队列中的队尾元素
QDataType QueueBack(Quene* pq);

相关文章:

数据结构-二叉树

数据结构-二叉树 二叉树的概念二叉树的遍历分类 建立二叉树&#xff0c;并遍历二叉树的最小单元二叉树的最小单元初始化初始化二叉树前序遍历的实现中序遍历的实现后序遍历的实现计算节点的个数计算树的深度求第k层的个数查找二叉树的元素分层遍历 全部代码如下 二叉树的概念 二…...

Open3D 进阶(4)高斯混合点云聚类

目录 一、算法原理1、原理概述2、实现流程3、参考文献二、代码实现三、结果展示四、测试数据本文由CSDN点云侠原创,原文链接。爬虫网站自重。 一、算法原理 1、原理概述 高斯混合聚类(GMM)算法假设数据点是由一个或多个高斯分布生成的,并通过最大似然估计的方法来估计每个簇…...

计算机组成和IO

文章目录 计组和Epoll&#xff1a;计算机组成原理&#xff1a;网络数据接收的流程&#xff1a;内核如何管理socket以及状态的更新select系统调用的复杂度epoll的et和lt模式及java的选择 国内访问chatai就可以 https://aiweb.douguguo.com/?typeadd计组和Epoll&#xff1a; 计…...

STM32CUBUMX配置RS485 modbus STM32(从机)亲测可用

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子&#xff0c;使用STM32CUBEMX做了很多驱动&#x…...

系统设计类题目汇总

1 设计一个系统统计当前时刻北京用户在线人数 【Redis】位图以及位图的使用场景(统计在线人数和用户在线状态) 1.1 方案一&#xff1a; 在用户登录时&#xff0c;使用 Redis SET 将用户 ID 添加到一个特定的键&#xff08;例如 “online:beijing”&#xff09;。用户退出时&…...

css滚动条样式指南

css滚动条样式指南 滚动条是网页设计中经常被忽视的元素。虽然它看起来像是一个小细节&#xff0c;但它在网站导航中起着至关重要的作用。默认的滚动条可能看起来不合适&#xff0c;有损整体美观。本文将介绍如何使用 CSS 自定义滚动条。 在 Chrome、Edge 和 Safari 中设置滚…...

vue子组件修改父组件传递的变量(自定义日期时间组件,时间间隔为15分钟或者一个小时)

vue子组件修改父组件传递的变量 子组件不能直接修改父组件变量的值&#xff0c;但是可以通过调用父组件的方法来修改。 实现步骤 在父组件声明变量 export default {data() {return {startTime:"",......},......} }在父组件使用子组件并传递数据&#xff0c;修改…...

【PyTorch】nn.Conv2d函数详解

nn.Conv2d 是 PyTorch 中的一个卷积层&#xff0c;用于实现二维卷积操作 torch.nn.Conv2d(in_channels, out_channels, kernel_size, stride1, padding0, dilation1, groups1, biasTrue, padding_modezeros, deviceNone, dtypeNone )参数解释 in_channels&#xff1a;输入的通…...

数智保险 创新未来 | GBASE南大通用亮相中国保险科技应用高峰论坛

本届峰会以“数智保险 创新未来”为主题&#xff0c;GBASE南大通用携新一代创新数据库产品及金融信创解决方案精彩亮相&#xff0c;与国内八百多位保险公司高管和众多保险科技公司技术专家&#xff0c;就保险领域数字化的创新应用及生态建设、新一代技术突破及发展机遇、前沿科…...

分布式天梯图算法在 Redis 图数据库中的应用

分布式天梯图算法在 Redis 图数据库中的应用 一、简介1 天梯图算法2 天梯图算法在Redis的应用 二、Redis分布式天梯图算法设计与优化1 基于天梯图的分布式算法设计2 多节点扩展与负载均衡优化3 数据存储方案与压缩策略 三、技术实现3.1 系统架构设计3.2 技术选型3.3 关键实现细…...

观察者模式——对象间的联动

1、简介 1.1、概述 在软件系统中&#xff0c;有些对象之间也存在类似交通信号灯和汽车之间的关系。一个对象的状态或行为的变化将导致其他对象的状态或行为也发生改变&#xff0c;它们之间将产生联动&#xff0c;正所谓“触一而牵百发”。为了更好地描述对象之间存在的这种一…...

【雕爷学编程】Arduino动手做(189)---特别苗条,使用微波传感器控制的纤细小车

装修屋子&#xff0c;找了一段墙面布线槽&#xff0c;外槽宽度只有23毫米&#xff0c;截取一段长为24厘米&#xff0c;尝试做个苗条小车 先在线槽上安装了二只N20小电机 装上二个快餐盒盖做轮子 测试一下使用3.7V锂电池的动力系统&#xff08;视频&#xff09; https://v.youk…...

机器学习基础算法及其实现

线性回归 知识点&#xff1a; 1. 线性回归模型可以使用不同的目标函数&#xff0c;最常用的是最小二乘法、最小绝对值法和最大似然法。 2. 在最小二乘法中&#xff0c;目标是最小化实际值与预测值之间的误差平方和&#xff0c;这可以通过求导数等方法来求解。 3. 在最小绝对值…...

docker安装MinIO

简介 Minio 是一个面向对象的简单高性能存储服务。使用 Go 语言编写&#xff0c;性能高、具有跨平台性。 Minio 官网为&#xff1a;https://min.io &#xff0c;有一个中文站点&#xff0c;单内容更新不是很及时&#xff0c;建议从原始官网学习。 本文采用 Docker 安装&…...

第5章 运算符、表达式和语句

本章介绍以下内容&#xff1a; 关键字&#xff1a;while、typedef 运算符&#xff1a;、-、*、/、%、、--、(类型名) C语言的各种运算符&#xff0c;包括用于普通数学运算的运算符 运算符优先级以及语句、表达式的含义 while循环 复合语句、自动类型转换和强制类型转换 如何编写…...

24考研数据结构-图的存储结构邻接矩阵

目录 6.3 储存结构&#xff08;邻接表表示法&#xff09;1. 储存方式2. 结构3. 图的邻接表存储表示&#xff08;算法&#xff09;4. 结论5. 邻接矩阵和邻接表的对比邻接矩阵优点&#xff1a;缺点&#xff1a; 邻接表优点&#xff1a;缺点&#xff1a; 邻接矩阵与邻接表的关系 6…...

在线推算两个日期相差天数的计算器

具体请前往&#xff1a;在线推算两个日期相差天数的计算器...

Spring源码解析(七):bean后置处理器AutowiredAnnotationBeanPostProcessor

Spring源码系列文章 Spring源码解析(一)&#xff1a;环境搭建 Spring源码解析(二)&#xff1a;bean容器的创建、默认后置处理器、扫描包路径bean Spring源码解析(三)&#xff1a;bean容器的刷新 Spring源码解析(四)&#xff1a;单例bean的创建流程 Spring源码解析(五)&…...

【C#学习笔记】引用类型(1)

文章目录 引用类型class匿名类 记录引用相等和值相等record声明 接口delegate 委托合并委托/多路广播委托 引用类型 引用类型的变量存储对其数据&#xff08;对象&#xff09;的引用&#xff0c;而值类型的变量直接包含其数据。 对于引用类型&#xff0c;两种变量可引用同一对…...

STM32CubeMX+VSCODE+EIDE+RT-THREAD 工程创建

Eide环境搭建暂且不表&#xff0c;后续补充。主要记录下Vscode环境下 创建Rt-thread工程的过程。分别介绍STM32CubeMX添加rtt支持包的方式和手动添加rtt kernel方式。STM32CubeMX生成工程的时候有"坑"&#xff0c;防止下次忘记&#xff0c;方便渡一下有缘人&#xff…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...