厦门网络推广建网站网站标题关键词描述

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

厦门网络推广建网站,网站标题关键词描述,建设工程交易服务中心,建站系统有哪些目录​​​​​​​ 前言#x1f344; 1.树概念及结构☎️ 1.1 树的概念#x1f384; 1.2 树的相关概念#x1f99c; 1.2.1 部分概念的加深理解#x1f43e; 1.2.2 树与非树#x1fab4; 1.3 树的表示#x1f38b; 1.4 树在实际中的运用#xff08;表示文件系统… 目录​​​​​​​ 前言 1.树概念及结构☎️ 1.1 树的概念 1.2 树的相关概念 1.2.1 部分概念的加深理解 1.2.2 树与非树 1.3 树的表示 1.4 树在实际中的运用表示文件系统的目录树结构 2.二叉树概念及结构 2.1概念 2.2 特殊的二叉树 2.2.1 如何求h是多少h层高度为h节点数合计多少 2.3 二叉树的存储结构 3.二叉树顺序结构及实现 3.1 二叉树的顺序结构 3.2 堆的概念及结构 3.2.1 堆的意义 3.3 堆的实现 3.3.1 小堆—向下调整 3.3.2 大堆—向上调整♻️ 3.3.3 建堆时间复杂度 3.3.4 堆的插入 3.3.5 堆的删除 3.4 小堆代码实现 3.4.1 Heap.h 3.4.2 Heap.c 4.4.2.1 向上调整的while结束的判断条件 3.4.3 test.c 4. 堆的应用 4.1 堆排序—升序♀️ 4.1.1 建堆的实现 4.1.2 为什么建小堆不实现升序建大堆实现升序 4.1.3 代码实现 4.1.3.1 Heap.h 4.1.3.2 Heap.c 4.1.3.2 test.c ​编辑 4.2 Top-k问题 4.2.1 为什么找前k个最大的元素要建小堆 4.2.2 代码实现 4.2.1 Heap.h 4.2.2 test.c 后语 前言 之前我们学习了栈和队列的基础知识有需要的小伙伴可以看小江的上一片篇博客哦 Note2—栈和队列-CSDN博客文章浏览阅读323次点赞6次收藏7次。之前我们学习了顺序表和链表的相关知识也完成了相应的练习接下来我们要学习的是栈和队列本篇将会比较详细的进行讲解栈和队列的相关知识点及如何实现以及一些OJ题https://blog.csdn.net/2301_79184587/article/details/134438809这篇博客我们一起来了解并学习数据结构中的初阶的二叉树共同为C打下牢固的基础 二叉树的知识点和内容比较多友友们一定要有耐心看完跳到自己需要的部分也是OK的下面我们开始今天的学习 1.树概念及结构☎️ 1.1 树的概念 树是一种非线性线性一字排开的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i  m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 因此树是递归定义的。 这里我们先引入树的概念可能会有一些看不懂的但是没关系第一部分看懂就行 1.2 树的相关概念 注意⚠️ 不是所有的概念都是重要的我会把重要的概念标记出来其余的我们做个了解就好 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 思考一下为什么根定义成1而不是0 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 1.2.1 部分概念的加深理解

1. 子节点and父节点有的节点可能是子节点也可能同时是父节点—相对性 例如D是A的子节点D同时又是H的父节点
2. 节点的层次说从根开始定义那是从0还是1 例如数组我们从0开始定义下标—数组名是首元素地址a[i]等价于(ai) 但是我们这里却大多从1开始定义 树会有这2种特殊的情况如果我们从0开始定义 只有根节点0 空树0or -1 怎么和只有根节点的情况区分空树要定义成-1 是对定义成-1注意这样的定义方法也是可以的但是比较麻烦后序实现二叉树时每当需要高度的时候可能还要思考一下 如果我们从1开始定义 只有根节点1 空树0 现在就很好区分了 1.2.2 树与非树 树—递归—每次都根子树—子树不相交0的时候递归结束即只有叶节点没有子树了 —铺垫后面的实现二叉树 1.3 树的表示 要求保存值域也要保存结点和结点之间的关系 实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法 树的表示复杂在于定义多少个孩子 左孩子右兄弟的思路 左边第一个为孩子右边其余的为孩子的兄弟 孩子太多管不过来—生老大让老大管老二老二管老三…… typedef int DataType; struct TreeNode {DataType val;struct TreeNode leftChild;struct TreeNode* rightBrother; }; 1.4 树在实际中的运用表示文件系统的目录树结构 这里的实际运用主要是Linux中的树状目录结构之后的博客小江也会带大家学习Linux的基本知识和怎么写代码的 当前目录/根目录 指令cd user进入user路径下 遍历当前目录的下一层树遍历找到user然后进入user—指令的本质是程序 2.二叉树概念及结构 2.1概念 一棵二叉树是结点的一个有限集合该集合: 1. 一个节点只有2个孩子或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 可以理解为二叉树实行计划生育可以生1个or不生0个or2个最多2个 1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 二叉树的左右之分很重要 注意对于任意的二叉树都是由以下几种情况复合而成的之后二叉树的实现会考虑到只有左/右子树只有根节点空树的情况 注意⚠️二叉树不等价于度为2的树 例如二叉树也可能为空or只有根节点二者是必要不充分的关系 2.2 特殊的二叉树 满二叉树每一层都是满的每个节点都有2个孩子 完全二叉树前n-1层都是满的每个节点都有2个孩子最后一层不一定是满的但是从左到右必须是连续的是否连续的话就要看左子树和右子树了 满二叉树是特殊的完全二叉树 如图这就不是连续的了 2.2.1 如何求h是多少h层高度为h节点数合计多少 2.3 二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 1. 顺序存储—完全二叉树/满二叉树 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面会讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2. 链式存储—普通二叉树 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 这里说一下子节点和父节点之间的规律 3.二叉树顺序结构及实现 3.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 3.2 堆的概念及结构 堆—数据结构堆总是一棵完全二叉树。 所有元素按完全二叉树的顺序存储方式存储在一个一维数组中 堆分为大堆和小堆 大堆任意一个父亲data孩子data—根节点是max 小堆任意一个父亲data孩子data—根节点是min 3.2.1 堆的意义 1.堆排序 2.解决top k问题 1.堆排序 大堆不一定有序但是根是最大的—调堆选出max之后取出找次大的最多循环h次 小堆也是同样的道理 时间复杂度O(N*logN) 上面我们算出了完全二叉树N个节点的高度h范围我们粗略估算大概有logN层共N个节点建堆的需要的时间复杂度N、最多排序h次故时间复杂度O(N*logN) 我们大概粗略估算一下hlogN N100万    h20 最多20次就可以将100万个数据排完了 空间复杂度O(1) 只要开辟空间给数组存储就行了 2.解决top k问题 例如我们要在100万个数据里面排出前10个最大的数据利用堆排序的话不需要排序100万次只需要循环10次找出前10个最大的 3.3 堆的实现 在开始之前我们先思考一下之前说堆由顺序结构的数组来存储那么堆的底层逻辑是顺序表嘛 并不是因为堆还要区分大小堆而顺序表没有大小要求直接插入就行 3.3.1 小堆—向下调整 我们先以实现小堆为例讲解一下向下调整的算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 3.3.2 大堆—向上调整♻️ 我们再以实现大堆为例讲解一下向上调整的算法 下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 具体的步骤和实现小堆一样只不过遍历结束的条件是遍历到根节点还需要递归实现 3.3.3 建堆时间复杂度 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 向下调整建堆 因此向下调整建堆的时间复杂度为O(N)。 向上调整建堆 由于证明思路和向下调整差不多这里我们就不再证明了而是简单的提一下 我们向上调整最后几层的节点个数在整个堆中看作满二叉树占比较大往上移移动次数又多时间复杂度肯定高于向下调整 向下调整建堆的时间复杂度大概为O(NlogN 3.3.4 堆的插入 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 3.3.5 堆的删除 删除堆是删除堆顶的数据 思路将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 3.4 小堆代码实现 由于大堆和小堆只是调整到时候判断大小的符号不同我们这里就演示小堆的实现大堆大家可以自行实现 3.4.1 Heap.h #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.htypedef int HPDataType; typedef struct Heap {HPDataType _a;//数组存放int _size;//有效存储个数int _capacity;//空间 }Heap; // 堆的初始化 void HeapInit(Heap* hp); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 bool HeapEmpty(Heap* hp); 3.4.2 Heap.c #includeHeap.h // 堆的初始化 void HeapInit(Heap* hp) {assert(hp);hp-_a NULL;hp-_capacity hp-_size 0; } // 堆的销毁 void HeapDestory(Heap* hp) {assert(hp);free(hp-_a);hp-_a NULL;hp-_capacity hp-_size 0; } //交换 void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp *x;*x *y;y tmp; } //向上调整 void AdjustUp(HPDataType a, int child) {int parent (child - 1) / 2;while (child0)//到根节点结束{if (a[child] a[parent]){Swap(a[child], a[parent]);//交换位置child parent;//继续遍历parent (child - 1) / 2;}else{break;}} } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) {assert(hp);//判断空间是否足够if (hp-_capacity hp-_size){int newcapacity hp-_capacity 0 ? 4 : 2 * hp-_capacity;HPDataType* a (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);if (a NULL){perror(realloc error!\n);return;}hp-_a a;hp-_capacity newcapacity;}//插入数据hp-_a[hp-_size] x;hp-_size;//向上调整AdjustUp(hp-_a, hp-_size-1);//之前size了 } //向下调整 void AdjustDown(HPDataType* a, int size, int parent) {//假设法假设最小的是左孩子不对的话再修改int child 2 * parent 1;while (childsize)//child(左孩子)要在数组范围内{if (a[child 1] a[child] child 1 size)//保证右孩子也在范围内{child;//右孩子小—和parent交换}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}elsebreak;} } // 堆的删除 void HeapPop(Heap* hp) {assert(hp);assert(hp-_size0);//首尾交换Swap(hp-_a[hp-_size - 1], hp-_a[0]);hp-_size–;//向下调整AdjustDown(hp-_a, hp-_size, 0);//之前size–过了 } // 取堆顶的数据 HPDataType HeapTop(Heap* hp) {assert(hp);assert(hp-_size 0);return hp-_a[0]; } // 堆的数据个数 int HeapSize(Heap* hp) {assert(hp);return hp-_size; } // 堆的判空 bool HeapEmpty(Heap* hp) {assert(hp);return hp-_size 0; } 4.4.2.1 向上调整的while结束的判断条件 注意⚠️ 我们是循环到根节点结束遍历 这里不能是while(parent0) 因为最后一次的时候parent0—进入循环—计算得出parent0—还要再次循环 而应该是while(child0) 因为最后一次的时候child0—进入循环—计算得出child0—结束循环 3.4.3 test.c #includeHeap.h int main() {int a[] { 4,6,2,1,5,8,4,7,3,9 };Heap hp;HeapInit(hp);for (int i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(hp, a[i]);}while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}printf(\n);return 0; } 建堆的效果 虽然今天的代码和方法实现排序但其实不是真正的堆排序 因为 1.我们是把数组插入到堆里面相当于在堆里面开了一个数组—一定的消耗 2.时间复杂度ONlog N     空间复杂度ON 3.堆排序是对数组进行排序但是我们没有 更好的方法直接将数组变成堆—下面的内容这也是为什么前面传参没有把堆的结构体传过去为堆排序做铺垫而是传数组 4. 堆的应用 4.1 堆排序—升序♀️ 堆排序即利用堆的思想来进行排序总共分为两个步骤 1. 建堆 升序建大堆 降序建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 4.1.1 建堆的实现 由于升序和降序的思路和实现差不多我们这里就演示实现升序 上面提到建堆可以选择向上调整和向下调整2种方法我们这里优先选择向下调整因为时间复杂度低 代码实现是基于之前的堆的实现 本质是模拟堆插入的过程建堆 4.1.2 为什么建小堆不实现升序建大堆实现升序 按理来说不应该是小堆实现升序大堆实现降序嘛 我们实现升序分别2个思路对比实现一下 4.1.3 代码实现 4.1.3.1 Heap.h //堆排序 void HeapSort(int a, int n); 4.1.3.2 Heap.c //堆排序–升序 void HeapSort(int* a, int n) {for (int i (n - 1 - 1) / 2; i 0; i–){AdjustDown(a,n,i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end–;} } 4.1.3.2 test.c //堆排序—升序 int main() {int a[] { 13,2,6,8,4,6,0,9,5,7,3,1 };int n sizeof(a) / sizeof(a[0]);HeapSort(a, n);for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);return 0; } 4.2 Top-k问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前K个元素来建堆 不能是前N个元素来建堆否则占用内存过大 N个数据插入到堆里面pop K次 时间复杂度N*logNK*logN—O(N*logN)   KN(忽略不计)     前k个最大的元素则建小堆     前k个最小的元素则建大堆 2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 时间复杂度ONlogK 4.2.1 为什么找前k个最大的元素要建小堆 设想一下 建大堆的话当最大的数据入堆时后面的数据就进不来了 建小堆的话当最大的数据入堆时沉到堆底其他数据继续入堆 4.2.2 代码实现 4.2.1 Heap.h //向下调整 void AdjustDown(HPDataType a, int size, int parent); 4.2.2 test.c //TOP-K问题 void PrintTopK(int* a,int n,int k) {//建一个k个数据的小堆int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc error!\n);return;}//读取前k个建小堆for(int i (k - 1 - 1) / 2; i 0;i–){AdjustDown(a, k-1, i);}// 将剩余n-k个元素依次与堆顶元素交换不满则则替换int m 0;while (mn){if (a[m] minheap[0]){minheap[0] a[m];AdjustDown(minheap, k, 0);}m;}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n); } int main() {int n 10000000;//100万int* a (int*)malloc(sizeof(int) * n);srand(time(0));for (int i 0; i n; i){ai % 10000000;}//自定义k个不在范围内的好查看方法是否正确a[5] 10000000 1;a[1231] 10000000 2;a[531] 10000000 3;a[5121] 10000000 4;a[115] 10000000 5;a[2335] 10000000 6;a[9999] 10000000 7;a[76] 10000000 8;a[423] 10000000 9;a[3144] 10000000 10;PrintTopK(a, n, 10);return 0; } 后语 到这里初阶二叉树的部分就结束了。下篇文章我们会介绍如何实现二叉树的链式结构和一些二叉树的OJ题和关于二叉树的性质和概念的一些选择题。希望本篇文章对你有帮助 本次的分享到这里就结束了 PS小江目前只是个新手小白。欢迎大家在评论区讨论哦有问题也可以讨论的 如果对你有帮助的话记得点赞收藏⭐️关注➕