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

链式二叉树的基本操作(C语言版)

目录

1.二叉树的定义

2.创建二叉树

3.递归遍历二叉树

1)前序遍历

2)中序遍历 

3)后序遍历

4.层序遍历

5.计算节点个数 

6.计算叶子节点个数

7.计算第K层节点个数

8.计算树的最大深度

9.查找值为x的节点

10.二叉树的销毁


从二叉树的概念中我们知道任何二叉树都难被分为,根,左子树,右子树,而左子树依然能被分为,根,左子树,右子树。右子树也是,所以我们这里可以采用递归的玩法来操作二叉树。

1.二叉树的定义

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

2.创建二叉树

由于是初学,为了便于观察,我们这里手搓一个二叉树

BTNode* CreateTree()
{BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));assert(n1);BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));assert(n2);BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));assert(n3);BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));assert(n4);BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));assert(n5);BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));assert(n6);BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));assert(n7);n1->data = 1;n2->data = 2;n3->data = 3;n4->data = 4;n5->data = 5;n6->data = 6;n1->left = n2;n1->right = n4;n2->left = n3;n2->right = NULL;n3->left = NULL;n3->right = n7;n4->left = n5;n4->right = n6;n5->left = NULL;n5->right = NULL;n6->left = NULL;n6->right = NULL;n7->left = NULL;n7->right = NULL;n7->data = 7;return n1;}

 注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式后序详解重点讲解。

3.递归遍历二叉树

根,左子树,右子树,遍历顺序的不同导致访问的结果也不同,先学习这三种遍历,这里递归较为简单,为我们后面做一些二叉树的oj题目打下基础。 

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

1)前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

// 二叉树前序遍历 
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

2)中序遍历 

中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。

// 二叉树中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

3)后序遍历

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 

// 二叉树后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

4.层序遍历

 层序遍历,自上到下,自左到右依次访问数的结点就是层序遍历。

思想(借助一个队列):
1、先将根节点入队,然后开始从队头出数据
2、出队头的数据同时将队头左右子树的结点入队(遇到NULL则不入队)
3、重复第二步,直到队列为空
 

//层序遍历
void TreeLevelOrder(BTNode* root)
{Queue 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);}printf("\n");
}

5.计算节点个数 

求树的结点总数时,可以将问题拆解成子问题:
 1.若为空,则结点个数为0。
 2.若不为空,则结点个数 = 左子树结点个数 + 右子树结点个数 + 1(自己)

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

6.计算叶子节点个数

 子问题拆解:
 1.若为空,则叶子结点个数为0。
 2.若结点的左指针和右指针均为空,则叶子结点个数为1。
 3.除上述两种情况外,说明该树存在子树,其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。

//叶子节点个数
int TreeLeaSize(BTNode* root)
{if (root == NULL)return 0;return (root->left == NULL && root->right == NULL) ? 1 : TreeLeaSize(root->left) + TreeLeaSize(root->right);
}

7.计算第K层节点个数

 这里我们要控制好递归的深度,我们依然把他给转换为子问题思考。

思路:

1、为空和非法时,结点个数为0个
2、为第一层时,结点个数为1个
3、不为空且合法时,第K层的结点个数=第K-1层的左子树结点个数+第K-1层的右子树结点个数

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

 8.计算树的最大深度

我们如何找出最深的那一条途径?这里是一个选择的问题。如果一条途径递归到倒数第二层,左边有一个叶子节点,右边无节点,那么我们应该选择左边作为它的最深途径。

思路:

1.若为空,则深度为0。
2.若不为空,则树的最大深度 = 左右子树中深度较大的值 + 1。

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

9.查找值为x的节点

思路:
 1.先判断根结点是否是目标结点。
 2.再去左子树中寻找。
 3.最后去右子树中寻找。

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;
}

10.二叉树的销毁

void BinaryTressDestory(BTNode* root)
{if (root == NULL)return;BinaryTressDestory(root->left);BinaryTressDestory(root->right);free(root);
}


相关文章:

链式二叉树的基本操作(C语言版)

目录 1.二叉树的定义 2.创建二叉树 3.递归遍历二叉树 1)前序遍历 2)中序遍历 3)后序遍历 4.层序遍历 5.计算节点个数 6.计算叶子节点个数 7.计算第K层节点个数 8.计算树的最大深度 9.查找值为x的节点 10.二叉树的销毁 从二叉树…...

Tcp三次握手四次挥手和SSL/TLS

1.Tcp三次握手四次挥手: 1.1基本概念: TCP(三次握手和四次挥手)是用于建立和终止可靠传输连接的过程。TCP协议是一种面向连接的传输层协议,确保数据在网络上可靠、有序地传输。下面详细解释三次握手和四次挥手的工作机…...

大棚分割数据集,40765对影像,16.9g数据量,0.8米高分二,纯手工标注(arcgis标注)的大规模农业大棚分割数据集。

数据集名称: )“Greenhouse Segmentation Dataset (GSD)” 数据集规模: 包含40,765对用于大棚分割的影像数据,每对影像包括一张原始图像和相应的分割标签图。 数据量: 总数据量约为16.9GB,适合存储在现…...

Jenkins插件安装失败时这么做就搞定啦!

1.网络或墙的问题导致插件下载安装失败 这种错误提示很明显,就是无法连接到插件下载地址,导致插件下载失败。 解决方法 为Jenkins更换源 点击Jenkins主页面左侧列表中【系统管理】—— 下拉找到【管理插件】 选择【高级】选项卡 替换最下方【升级站点…...

优化器与现有网络模型的修改

文章目录 一、优化器是什么二、优化器的使用三、分类模型VGG16四、现有网络模型的修改 一、优化器是什么 优化器(Optimizer)是一个算法,用于在训练过程中调整模型的参数,以便最小化损失函数(Loss Function&#xff09…...

kafka 超详细的消息订阅与消息消费几种方式

kafka 消息订阅与消息消费几种方式 本文主要内容 消费者订阅几种方式 订阅多个主题 按正则表达式订阅 消息消费几种方式 按分区消费 按主题消费 不区分 “ 笔者建议一开始学习Kafka最好不要用SpringBoot 集成方式,因为SpringBoot推崇用注解方式,比如KafkaList…...

C++ 第三讲:内存管理

C 第三讲:内存管理 1.C内存分布2.内存管理方式2.1C语言内存管理方式2.2C内存管理方式2.2.1new\delete操作内置类型2.2.2new\delete操作自定义类型 3.operator new与operator delete函数4.new和delete实现原理4.1内置类型4.2自定义类型 5.定位new5.1内存池的基本了解…...

LeeCode打卡第二十九天

LeeCode打卡第二十九天 第一题:岛屿数量(LeeCode第200题): 给你一个由 1(陆地)和 0(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只…...

阿里云专业翻译api对接

最近我们一个商城项目涉及多语言切换,默认中文。用户切换语言可选英语和阿拉伯语言,前端APP和后端返回动态数据都要根据用户选择语言来展示。前端静态内容都做了三套语言,后端商品为了适用这种多语言我们也进行了改造。每一件商品名称&#x…...

基于Spring Boot的能源管理系统+建筑能耗+建筑能耗监测系统+节能监测系统+能耗监测+建筑能耗监测

介绍 建筑节能监测系统是基于计算机网络、物联网、大数据和数据可视化等多种技术融合形成的一套节能监测系统。 系统实现了对建筑电、水、热,气等能源、资源消耗情况的实时监测和预警、动态分析和评估,为用户建立了科学、系统的节能分析方法&#xff0c…...

大数据新视界 --大数据大厂之 Cassandra 分布式数据库:高可用数据存储的新选择

💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

ROS第五梯:ROS+VSCode+C++单步调试

解决问题:在ROS项目中进行断点调试。 第一步:创建一个ROS项目或者打开一个现有的ROS项目。 第二步:修改c_cpp_properties.json 增加一段命令: "compileCommands": "${workspaceFolder}/build/compile_commands.json"第三…...

SLA 概念和计算方法

SLA 概念和计算方法 SLA SLA:服务等级协议(简称:SLA,全称:service level agreement) 网站服务可用性的一个保证 9越多代表全年服务可用时间越长服务更可靠,停机时间越短,反之亦然…...

C++比大小游戏

目录 开头程序程序的流程图程序游玩的效果下一篇博客要说的东西 开头 大家好&#xff0c;我叫这是我58。 程序 #include <iostream> #include <Windows.h> using namespace std; int main() {int ir 1;char chparr[2] { 0 };int ip1 0;int ip2 0;int i 1;c…...

PCIe进阶之TL:Memory, I/O, and Configuration Request Rules TPH Rules

1 Memory, I/O, and Configuration Request Rules 下述规则适用于 Memory 请求、IO 请求和配置请求。 除了公共的 header 字段外,所有 Memory 请求、IO 请求和配置请求还包括以下字段: (1)Requester ID[15:0] 和 Tag[9:0],组成了 Transaction ID 。 (2)Last DW BE[3:0]…...

【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树(二)(内含TOP-K问题)

文章目录 前言1. 堆1.1 堆的概念1.2 堆的分类 2. 堆的实现2.1 堆的结构体设置2.2 堆的初始化2.3 堆的销毁2.4 添加数据到堆2.4.1 "向上调整"算法 2.5 从堆中删除数据2.5.1 “向下调整”算法 2.6 堆的其它各种方法接口函数 3. 堆排序3.1 堆排序的代码实现 4. TOP-K问题…...

sqli-lab靶场学习(二)——Less8-10(盲注、时间盲注)

Less8 第八关依然是先看一般状态 http://localhost/sqli-labs/Less-8/?id1 然后用单引号闭合&#xff1a; http://localhost/sqli-labs/Less-8/?id1 这关的问题在于报错是不显示&#xff0c;那没办法通过上篇文章的updatexml大法处理。对于这种情况&#xff0c;需要用“盲…...

Dijkstra算法和BFS算法(单源最短路径)

基于你设计的带权有向图&#xff0c;从某一结点出发&#xff0c;执行Dijkstra算法求单源最短路径。用文字描述每一轮执行的过程 文字描述&#xff1a;用BFS算法求单源最短路径的过程 Dijkstra 算法 BFS算法 广度优先算法...

在WordPress中最佳Elementor主题推荐:专家级指南

对于已经在WordPress和Elementor上有丰富经验的用户来说&#xff0c;选择功能强大且高度灵活的主题&#xff0c;能大大提升网站的表现和定制能力。今天&#xff0c;我们来介绍六款适合用户的专家级Elementor主题&#xff1a;Sydney、Blocksy、Rife Free、Customify、Deep和Laye…...

关于RabbitMQ消息丢失的解决方案

RabbitMQ如何保证消息的可靠性传输 一、消息丢失的原因 1. 生产者端 网络问题&#xff1a; 原因&#xff1a;生产者与RabbitMQ服务器之间的网络连接不稳定或中断&#xff0c;导致消息在传输过程中丢失。解决方案&#xff1a;确保网络连接稳定&#xff0c;监控网络状态&#x…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...