数据结构之二叉树与堆以及力扣刷题函数扩展

个人主页:点我进入主页

专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞,评论,收藏。

一起努力

目录

1.前言

2.树

2.1概念

 2.2树的相关概念

3.堆

3.1堆的概念

3.2小堆函数实现

4.力扣刷题函数

5.总结


1.前言

        在前面我们学习了关于顺序表,链表,栈,队列的存储方式。今天我将给大家带来关于树的一些内容以及堆的部分内容,详细包括树的定义,树相关的概念,二叉树和满二叉树的概念,树代码的实现会在后面的内容,大堆和小堆的代码实现。今天的内容相较于前面会有一点难以理解,希望大家可以认真学习,当然还有几个力扣刷题的函数扩展,其中的内容就绝对会让你感到其中的乐趣。

2.树

2.1概念

        树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。有一个特殊的结点,称为根结点,根节点没有前驱结点除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继因此,树是递归定义的。

下面我给出关于树的图:

 2.2树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点
非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林。

3.堆

3.1堆的概念

        如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。堆我们分为大堆个小堆,大堆是父节点永远大于子节点,小堆是父节点永远小于子节点。堆的图我们认为堆是如下的样子:

事实上我们是顺序表的形式存储的,我们知道堆是一颗完全二叉树,我们将树的每个节点用数字进行标记,如下:

我们不难得出我们知道父节点的编号为n,左孩子的编号为2n+1,右孩子的编号为2n+2,假设左孩子的标号为n那么父节点的编号为(n-1)/2,我们设右孩子的节点为n那么父节点的编号为(n-1)/2,那我们很容易得到孩子节点编号为n父节点的编号为(n-1)/2,根据这一特点我们就可以利用顺序表进行存储,这样也能更好的找到父节点和孩子节点的位置,接下来我们以实现小堆为例子来展示一下大堆和小堆的实现(大堆和小堆的差距只有向上调整的部分符号不同,其余基本一致)。

3.2小堆函数实现

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Swap(MyHeapData* num1, MyHeapData* num2)
{MyHeapData temp = *num1;*num1 = *num2;*num2 = temp;
}
void AdJustUp(MyHeapData* arr, int size)
{assert(arr);int child = size - 1, parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
void HeapInit(Heap* php)
{assert(php);php->data = (MyHeapData*)malloc(sizeof(MyHeapData));php->size = 0;php->capacity = 0;
}
void HeapDestory(Heap* php)
{assert(php);free(php->data);php->data = NULL;
}
void HeapPush(Heap* php, MyHeapData x)
{if (php->size == php->capacity){int newcapacity = php->capacity + 2;MyHeapData* arr = (MyHeapData*)realloc(php->data, newcapacity * sizeof(MyHeapData));if (arr == NULL){perror("realloc fail");return;}php->data = arr;php->capacity = newcapacity;}php->data[php->size++] = x;AdJustUp(php->data, php->size);
}
void print(Heap* php)
{for (int i = 0; i < php->size; i++)printf("%d ", php->data[i]);
}
void HeapPop(Heap* php)
{assert(php);if (!HeapEmpty(php)){Swap(&php->data[0], &php->data[php->size - 1]);php->size--;AdJustDown(php->data, php->size);}
}
void AdJustDown(MyHeapData* arr, int size)
{assert(arr);int parent = 0, child = parent * 2 + 1;while (child<size){if (child + 1 < size && arr[child] > arr[child + 1]){child++;}Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}
}
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}
void text()
{Heap ph;HeapInit(&ph);HeapPush(&ph, 7);HeapPush(&ph, 6);HeapPush(&ph, 4);HeapPush(&ph, 5);HeapPush(&ph, 1);HeapPush(&ph, 1);HeapPush(&ph, 3);print(&ph);printf("\n");HeapPop(&ph);print(&ph);printf("\n");HeapPop(&ph);print(&ph);HeapDestory(&ph);
}

到这里我们的小堆就实现完了。

4.力扣刷题函数

        函数为sscanf函数和sprintf函数,其中sscanf函数是将任意类型数据储存在字符串中,spintf函数是将字符串数据输入到新的变量中,他们重新定义了输入输出流,我们看下面代码来感受一下:

#include<stdio.h>
int main()
{int a = 10;char arr[] = "abcd";double f = 1.99;char brr[100];sprintf(brr, "%d %s %f", a, arr, f);printf("%s\n", brr);a = 0;double b = 0.0;sscanf(brr, "%d %s %f", &a, &arr, &b);printf("%d %s %f", a, arr, f);return 0;
}

运行结果如下:

5.总结

        今天的内容到这里就结束了,非常感谢大家的观看,希望大家可一学到很多东西,尤其是堆的向下调整和向上调整这两个函数。

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

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

相关文章

orvibo旗下的VS30ZW网关分析之二:版本回退方法

概述 上接第一篇: orvibo旗下的VS30ZW网关分析之一-CSDN博客 此产品VS30ZW支持openwrt的页面,可以版本回退进行刷机。 openwrt固件下载: 固件名称:openwrt-VS30ZW-mt7628.bin 链接地址:https://download.csdn.net/download/leekwen/88579427 版本回退方法: 1、同…

Jupyter Markdown 插入图片

首先截图 注意 这一步是关键的&#xff01;&#xff01; 它需要使用电脑自带的截图&#xff0c;用qq啊vx啊美图秀秀那些都不行哦。 截图之后复制&#xff1a; 然后快捷键粘贴到jupyter里面&#xff0c;它会生成一段代码&#xff08;没有代码就是说截图形式不对&#xff09;&a…

Intellij idea 内存不够用了,怎么处理?

目录 如何判断内存不够用了 下面演示一下如何开启内存指示器&#xff08;Memory Indicator&#xff09; 解决方案 第一种&#xff1a;双击"内存指示器(Mempory Indicator)" 第二种&#xff1a;增大Intellij Idea 最大可使用内存 如何判断内存不够用了 运行项目后…

Vue3-Pinia

Pinia是什么 Pinia是Vue的最新状态管理工具&#xff0c;是Vuex的替代品 比Vuex更大的优势在于&#xff1a; 1.提供更加简单的API&#xff08;去掉了mutation&#xff09; 2.提供符合&#xff0c;组合式风格的API&#xff08;和Vue3新语法统一&#xff09; 3.去掉了modules…

【linux】信号——信号产生

信号产生 1.预备知识2.信号产生2.1通过键盘发送信号2.2系统调用接口向进程发送信号2.3硬件异常产生信号2.4软件条件2.5总结 自我名言&#xff1a;只有努力&#xff0c;才能追逐梦想&#xff0c;只有努力&#xff0c;才不会欺骗自己。 喜欢的点赞&#xff0c;收藏&#xff0c;关…

SpringBoot整合阿里云OSS、天翼云OSS、MinIO对象存储

大家好&#xff01;我是sum墨&#xff0c;一个一线的底层码农&#xff0c;平时喜欢研究和思考一些技术相关的问题并整理成文&#xff0c;限于本人水平&#xff0c;如果文章和代码有表述不当之处&#xff0c;还请不吝赐教。 以下是正文&#xff01; 对象存储是什么&#xff1f…

LeetCode.24两两交换链表中的节点

LeetCode.24两两交换链表中的节点 1.问题描述2.解题思路3.代码 1.问题描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 示…

HbuilderX 项目打包文件过大问题优化

文章目录 HbuilderX 项目打包文件过大问题优化主要操作收效甚微&#xff0c;但又有那么点用的方法使用 gulp 压缩&#xff08;最后一步&#xff09;使用与配置 网上找的 gulp 优化压缩配置还未尝试可能有用的方法 尝试过程中看到的一些优质文章 HbuilderX 项目打包文件过大问题…

CSS特效020:涌动的弹簧效果

CSS常用示例100专栏目录 本专栏记录的是经常使用的CSS示例与技巧&#xff0c;主要包含CSS布局&#xff0c;CSS特效&#xff0c;CSS花边信息三部分内容。其中CSS布局主要是列出一些常用的CSS布局信息点&#xff0c;CSS特效主要是一些动画示例&#xff0c;CSS花边是描述了一些CSS…

计算机基础知识60

MySQL分组 # 概念&#xff1a;分组是按照某个指定的条件将单个单个的个体分成一个个整体 # MySQL分组的关键字&#xff1a;group by # 分组一般配合聚合函数使用&#xff1a; sum max min avg count 基本的语法格式: group by 字段名 [having 条件表达式] # 单独使用 group by关…

直播场景视频和特效解决方案

直播已经成为企业与消费者互动的重要方式&#xff0c;如何提供优质的直播内容&#xff0c;提升直播效果&#xff0c;以及实现直播内容的商业化转化&#xff0c;一直是企业面临的重要挑战。为此&#xff0c;美摄科技提供了一套全面的直播场景解决方案&#xff0c;帮助企业解决这…

微服务知识大杂烩

1.什么是微服务? 微服务(Microservices)是一种软件架构风格,将一个大型应用程序划分为一组小型、自治且松耦合的服务。每个微服务负责执行特定的业务功能,并通过轻量级通信机制(如HTTP)相互协作。每个微服务可以独立开发、部署和扩展,使得应用程序更加灵活、可伸缩和可…

java开发之个微群聊管理

简要描述&#xff1a; 群管理操作 请求URL&#xff1a; http://域名/operateChatRoom 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型说明w…

【算法刷题】Day8

文章目录 202. 快乐数解法&#xff1a; 11. 盛最多水的容器解法&#xff1a; 202. 快乐数 原题链接 拿到题&#xff0c;我们先看题干 把一个整数替换为每个位置上的数字平方和&#xff0c;有两种情况&#xff1a; 重复这个过程始终不到 1&#xff08;无限死循环&#xff09;结…

P27 C++this 关键字

目录 前言 01 this关键字的引入 02 this关键字 前言 本章的主题是 C 中的 this 关键字。 以前第一次学qt的时候就遇到了this关键字&#xff0c;那时候还不是很会C&#xff0c;所以有点懵&#xff0c;现在我们就来讲解以下C中的this关键字 C 中有一个关键字 this&#xff0…

考过了PMP,面试的时候应该怎么办?

近期喜番在后台收到了很多同学们的私信&#xff0c;表示自己已经过了8月份的PMP考试&#xff0c;开始着手往项目管理岗位转型&#xff0c;但是对于项目管理岗位的面试却一筹莫展。放轻松&#xff0c;大家的需求喜番都了解了&#xff0c;喜番给大家总结了一些项目经理在面试的时…

漏电保护器工作原理

漏电保护器 漏电保护器是低压线路中最常用的保护器之一&#xff0c;简称漏保&#xff0c;又称漏电开关或漏电断路器。漏电保护器除了具有空开的所有保护功能外&#xff0c;还具备漏电保护功能。 需要了解 一根通电导线可以产生磁场&#xff0c;磁场与电流方向遵循右手螺旋关…

【深度学习】学习率及多种选择策略

学习率是最影响性能的超参数之一&#xff0c;如果我们只能调整一个超参数&#xff0c;那么最好的选择就是它。相比于其它超参数学习率以一种更加复杂的方式控制着模型的有效容量&#xff0c;当学习率最优时&#xff0c;模型的有效容量最大。本文从手动选择学习率到使用预热机制…

深入理解OS--硬件高速缓存,缓存一致性,存储设备

存储技术 1.SRAM&#xff0c;DRAM 静态&#xff1a;更快&#xff0c;用作高速缓存存储器。处理器高速缓存采用SRAM。 动态&#xff1a;用作主存及图形系统的帧缓冲区。内存采用DRAM。 2.内存 2.1.内存数据访问示例 设备控制器存在缓存。设备芯片自身存在缓存。 2.2.采用并行…

【算法刷题】Day7

文章目录 283. 移动零1089. 复写零 283. 移动零 原题链接 看到题目&#xff0c;首先看一下题干的要求&#xff0c;是在原数组内进行操作&#xff0c;平切保持非零元素的相对顺序 这个时候我们看到了示例一&#xff1a; [ 0, 1, 0, 3,12 ] 这个时候输出成为了 [ 1, 3, 12, 0, …