当前位置: 首页 > 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…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

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

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

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...