网站开发和维护合同,服务器创建wordpress,企业门户网站建设精英,wordpress建站怎么上传各位读者老爷好#xff0c;鼠鼠我现在浅浅介绍一些关于二叉树的知识点#xff0c;在各位老爷茶余饭后的闲暇时光不妨看看#xff0c;鼠鼠很希望得到各位老爷的指正捏#xff01; 开始介绍之前#xff0c;给各位老爷看一张风景照#xff0c;有读者老爷知道在哪里吗#x…各位读者老爷好鼠鼠我现在浅浅介绍一些关于二叉树的知识点在各位老爷茶余饭后的闲暇时光不妨看看鼠鼠很希望得到各位老爷的指正捏 开始介绍之前给各位老爷看一张风景照有读者老爷知道在哪里吗 第一个在评论区答出正确答案的老爷鼠鼠会联系你有惊喜捏 目录
1.树
1.1.树的概念
1.2.树的相关概念
2.二叉树
2.1.二叉树的概念
2.2.特殊的二叉树
2.3.二叉树的存储结构
3.堆
3.1.堆的概念及分类
3.2.堆的顺序存储的实现二叉树的顺序存储的实现
3.2.1.堆大堆总览
3.2.2. 定义堆
3.2.3.堆的初始化
3.2.4.堆的插入
3.2.5.堆的删除
3.2.6.获取堆顶的数据
3.2.7.堆的数据个数
3.2.8.堆的判空
3.2.9.堆的销毁
4.运行结构分析 好的我们在介绍二叉树之前需要了解树的概念 1.树
1.1.树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 画个图给各位老爷看看 我们可以看到 1.有一个特殊的结点A节点称为根结点根节点没有前驱结点。 2.除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。 3.因此树是递归定义的。 注意树形结构中子树之间不能有交集否则就不是树形结构。 树形结构除了根节点外每个节点有且只有一个父节点。如图就不是一个树形结构。 1.2.树的相关概念 介绍下面相关概念鼠鼠以下面树形结构举例 1.节点的度一个节点含有的子树的个数称为该节点的度 如上图A节点的度为3B节点的度为2。
2.叶节点或终端节点度为0的节点称为叶节点 如上图G、H、I、J、K和L节点为叶节点。
3.非终端节点或分支节点度不为0的节点 如上图B、C、D、E和F节点为分支节点。
4.双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点也是C的父节点也是D的父节点。
5.孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B、C和D都是A的孩子节点。
6.兄弟节点具有相同父节点的节点互称为兄弟节点 如上图J、K和L互为兄弟节点。
7.树的度一棵树中最大的节点的度称为树的度 如上图树的度为3。
8.节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推。
9.树的高度或深度树中节点的最大层次 如上图树的高度为4。
10.堂兄弟节点双亲节点在同一层的节点互为堂兄弟节点如上图F和G互为堂兄弟节点。
11.节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先。
12.子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙。
13.森林由mm0棵互不相交的树的集合称为森林。 有了以上铺垫我们来了解二叉树的概念 2.二叉树
2.1.二叉树的概念 一棵二叉树是结点的一个有限集合该集合: 1. 或者为空。 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 说简单点呢二叉树是一颗特殊的树这颗树的度最大为2就像是对这颗树的节点进行了计划生育最多只能生两个节点宝宝。 从图可以看出 1. 二叉树不存在度大于2的结点。 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。 3.二叉树的子树也都是二叉树既然是二叉树就可以为空树。 注意对于任意的二叉树都是由以下几种情况复合而成的 2.2.特殊的二叉树
1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。 很容易知道满二叉树各层的节点个数构成一个以1为首项以2为公比的等比数列。如果一个二叉树的层数为K用等比数列的求和公式或者错位相减法就能得到满二叉树节点的和为2^K-1。
那么反过来如果知道了满二叉树的节点个数为X那么它的层数就为log2X1约等log2(X)。 2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
说简单易懂的话呢就是说完全二叉树如果有K层那么前K-1层的节点数都达到最大值第K层的节点数不一定达到最大值但是最后一层的节点从左到右必须连续。 跟上面分析的一样我们知道完全二叉树的前K-1层的节点数总和为2^(K-1)-1 。最后一层第K层的节点个数最少为1个最多为2^(K-1)个。那么完全二叉树的节点总数范围就是2^(K-1)到2^K-1。
相同的我们如果知道完全二叉树的节点个数为X那么它的层数也大概是log2(X)。
2.3.二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 1. 顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储至于堆是什么鼠鼠下面会讲的捏二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 也许各位老爷不明白为啥可以将二叉树存储到一个数组中呢 其实我们将二叉树在逻辑上想象成一颗二叉树在逻辑上我们将二叉树的节点一层一层按顺序存储到数组中。我们通过以下规律可以控制二叉树捏 1.左孩子节点下标父节点下标*21 2.右孩子节点下标父节点下标*21 3.父节点下标(左孩子节点下标-1)/2(右孩子节点下标-1)/2 那么为什么只有完全二叉树适合用顺序存储捏 因为用顺序存储就是用数组存储的话我们要保证父节点下标和孩子节点下标满足上面三条规律才能控制好二叉树。而非完全二叉树要想满足上面三条规律的话我们会有空间浪费如下图 如果根据错误对应来存储二叉树节点的话就不符合上面的三条规律了 所以顺序存储适合完全二叉树非完全二叉树也可以存储但不适合 2. 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法二叉链是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
本篇博客不细讲二叉树的链式存储我们主要搞定顺序存储链式存储后面博客再介绍 既然介绍二叉树的顺序存储而现实中使用中只有堆才会使用数组来存储鼠鼠就要介绍堆这个概念并实现堆也就是实现二叉树的顺序存储捏
3.堆
堆就是一颗二叉树堆一般是将数组数据看做一颗完全二叉树。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事本篇博客讲的堆一个是数据结构另外一个是操作系统中管理内存的一块区域分段。
3.1.堆的概念及分类 简单讲堆就是一颗二叉树不过这颗二叉树对数据摆放有要求 大堆任意一个父节点数据要大于或等于它的任意孩子节点数据 小堆任意一个父节点数据要小于或等于它的任意孩子节点数据 堆只有大堆和小堆之分没有中堆这个说法我们来看一道题方便理解 1.下列关键字序列为堆的是 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32 答案选A为什么A是堆其他不是捏我们来看 A选项 还原成逻辑结构的完全二叉树的话很明显是一个大堆 B选项 还原成逻辑结构的完全二叉树的话很明显不是大堆也不是小堆比如说6065符合小堆要求但是7032又符合大堆要求所以不是堆 其他选项分析相同鼠鼠就不解释了 3.2.堆的顺序存储的实现二叉树的顺序存储的实现
也许有读者老爷不明白为啥用堆的顺序存储的实现代表二叉树的顺序存储的实现因为堆的顺序存储的实现是有意义的它能很好的管理数据而并非单纯的存储数据。如果单纯存储数据我们大可不必用二叉树来存储至于堆能实现什么功能再下面的讲解中鼠鼠会浅谈。
因为堆有大堆和小堆之分鼠鼠我实现大堆的顺序存储为例
3.2.1.堆大堆总览
我们先总体看堆的顺序存储实现完的三个文件有兴趣的老爷可以放到一个工程下面玩玩
1.heap.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//大堆typedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size;int capacity;
}Heap;//堆的初始化
void HeapInit(Heap* HP);//堆的插入
void HeapPush(Heap* HP, HeapDataType x);//堆的删除
void HeapPop(Heap* Hp);//取堆顶的数据
HeapDataType HeapTop(Heap* HP);//堆的数据个数
int HeapSize(Heap* hp);// 堆的判空
bool HeapEmpty(Heap* hp);//堆的销毁
void HeapDestroy(Heap* HP);
2.heap.c
#define _CRT_SECURE_NO_WARNINGS
#includeheap.hvoid HeapInit(Heap* HP)
{assert(HP);HP-a NULL;HP-capacity HP-size 0;
}void swap(HeapDataType* parent, HeapDataType* child)
{HeapDataType tmp *parent;*parent *child;*child tmp;
}void AdjustUp(HeapDataType* a, int childcoordinate)
{int parentcoordinate (childcoordinate - 1) / 2;while (childcoordinate 0){if (a[parentcoordinate] a[childcoordinate]){swap(a[parentcoordinate], a[childcoordinate]);childcoordinate parentcoordinate;parentcoordinate (parentcoordinate - 1) / 2;}else{break;}}
}void HeapPush(Heap* HP, HeapDataType x)
{assert(HP);//扩容if (HP-capacity HP-size){int newcapacity HP-capacity 0 ? 4 : HP-capacity * 2;HeapDataType* tmp (HeapDataType*)realloc(HP-a, sizeof(HeapDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}HP-a tmp;HP-capacity newcapacity;}HP-a[HP-size] x;//向上调整AdjustUp(HP-a, HP-size - 1);
}void AdjustDown(HeapDataType* a, int size, int parentcoordinate)
{int childcoordinate parentcoordinate * 2 1;while (childcoordinate size){if (a[childcoordinate] a[childcoordinate 1]childcoordinate1size){childcoordinate;}if (a[childcoordinate] a[parentcoordinate]){swap(a[childcoordinate], a[parentcoordinate]);parentcoordinate childcoordinate;childcoordinate childcoordinate * 2 1;}else{break;}}
}void HeapPop(Heap* HP)
{assert(HP);assert(HP-size 0);swap(HP-a[0], HP-a[HP-size - 1]);HP-size--;//向下调整AdjustDown(HP-a, HP-size,0);
}HeapDataType HeapTop(Heap* HP)
{assert(HP-size 0);return HP-a[0];
}int HeapSize(Heap* HP)
{return HP-size;
}bool HeapEmpty(Heap* HP)
{return HP-size 0;
}void HeapDestroy(Heap* HP)
{free(HP-a);HP-a NULL;HP-capacity HP-size 0;
}3.test.c
#define _CRT_SECURE_NO_WARNINGS
#includeheap.hint main()
{int a[] { 100,90,80,110,75,3 };Heap p;HeapInit(p);for (int i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(p, a[i]);}for(int i0;ip.size;i){printf(%d , p.a[i]);}printf(\n);while (!HeapEmpty(p)){printf(%d , HeapTop(p));HeapPop(p);}return 0;
}
4.运行结果 运行结果为啥是这样的我们一会分析 3.2.2. 定义堆
typedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size;int capacity;
}Heap; 这里重命名int为HeapDataType大大方便后续代码的维护用a指向后来动态开辟的连续内存该连续内存用来存储堆的数据size用来记录堆的数据个数或者指向堆最后一个数据的下一个capacity用来记录连续内存可放入数据的容量。 这里用一个结构体来定义堆如代码所示定义的跟顺序表一样但是我们这里表示的堆对数据的摆放要求是大堆或者小堆而顺序表就没有这个要求
3.2.3.堆的初始化
void HeapInit(Heap* HP)
{assert(HP);HP-a NULL;HP-capacity HP-size 0;
}
断言防止传入结构体变量地址为空下面这点不在赘述。 不妨将a置空将capacity和size置0。
3.2.4.堆的插入
void swap(HeapDataType* parent, HeapDataType* child)
{HeapDataType tmp *parent;*parent *child;*child tmp;
}void AdjustUp(HeapDataType* a, int childcoordinate)
{int parentcoordinate (childcoordinate - 1) / 2;while (childcoordinate 0){if (a[parentcoordinate] a[childcoordinate]){swap(a[parentcoordinate], a[childcoordinate]);childcoordinate parentcoordinate;parentcoordinate (parentcoordinate - 1) / 2;}else{break;}}
}void HeapPush(Heap* HP, HeapDataType x)
{assert(HP);//扩容if (HP-capacity HP-size){int newcapacity HP-capacity 0 ? 4 : HP-capacity * 2;HeapDataType* tmp (HeapDataType*)realloc(HP-a, sizeof(HeapDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}HP-a tmp;HP-capacity newcapacity;}HP-a[HP-size] x;//向上调整AdjustUp(HP-a, HP-size - 1);
}堆的插入我们表面上是在数组中动态开辟的空间尾插但我们逻辑上要想象成数据插入在树的底层并调整数据使其符合大堆要求。 这里的精髓是调整数据也就是代码中的向上调整函数。关于向上调整函数鼠鼠画一个图方便理解吧 3.2.5.堆的删除
void swap(HeapDataType* parent, HeapDataType* child)
{HeapDataType tmp *parent;*parent *child;*child tmp;
}void AdjustDown(HeapDataType* a, int size, int parentcoordinate)
{int childcoordinate parentcoordinate * 2 1;while (childcoordinate size){if (a[childcoordinate] a[childcoordinate 1]childcoordinate1size){childcoordinate;}if (a[childcoordinate] a[parentcoordinate]){swap(a[childcoordinate], a[parentcoordinate]);parentcoordinate childcoordinate;childcoordinate childcoordinate * 2 1;}else{break;}}
}void HeapPop(Heap* HP)
{assert(HP);assert(HP-size 0);swap(HP-a[0], HP-a[HP-size - 1]);HP-size--;//向下调整AdjustDown(HP-a, HP-size,0);
} 对于堆的删除来说数据结构规定删除的是堆顶的数据根节点数据当然删除完堆顶数据后我们必须将剩余数据再构成大堆。
为啥删除的是堆顶的数据捏因为堆顶的数据是堆中所有数据中最大的删除完堆顶数据后新的堆顶就是“次大的”这样的话我们可以做到选数的功能后面可以更好体会。
完成堆的删除我们采取将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。堆的删除过程画图理解如下 3.2.6.获取堆顶的数据
HeapDataType HeapTop(Heap* HP)
{assert(HP-size 0);return HP-a[0];
}
简单返回a[0]即可。
3.2.7.堆的数据个数
int HeapSize(Heap* HP)
{return HP-size;
}
根据设定返回size即可。
3.2.8.堆的判空
bool HeapEmpty(Heap* HP)
{return HP-size 0;
}
当堆为空返回真堆不为空返回假所以容知上面代码逻辑可以实现逻辑自恰 。
3.2.9.堆的销毁
void HeapDestroy(Heap* HP)
{free(HP-a);HP-a NULL;HP-capacity HP-size 0;
}
销毁动态开辟的空间并将a置成NULL将capacity和size置成0即可。
4.运行结构分析 各位老爷先看结果如下 第一条语句定义一组数组a成员为100、90、80、110、75和3。
第二条语句定义一个结构体变量p。
第三条语句调用HeapInit函数初始化p。
接下来for循环语句取数组a成员依次入堆。由HeapPush函数可知执行完这个for循环语句后a成员构成大堆
接下来for循环语句打印大堆得出110 100 80 90 75 3。可以看出这样存储确实是大堆。
接下来while循环当堆不为空时打印堆顶数据并删除堆顶数据得出结果为110 100 90 80 75 3是递减的。 从这里我们可以看出堆大堆的管理数据的能力删除堆顶数据就是删除了大堆中最大的数据并将剩下的数据成大堆这样新的大堆的新的堆顶数据就是“次大的”再删除堆顶数据再成大堆…………这样出来的数据就是有序的。 我们再看删除堆顶数据的时间复杂度在PeadPop函数中时间消耗最多的是向下调整函数AdjustDown而我们知道向下调整函数中最多调整堆的层数-1次前面我们算过完全二叉树的层数约为log2(X)。再结合时间复杂度的知识我们就可以说删除堆数据的时间复杂度为O(logN))。 那么我们每删除一次栈顶数据就可以选一次“最大”的数时间复杂度是O(logN)。如果有1百万个数据让我们选出最大的数用堆来选的话我们最多选20一定可以选出来但如果用常规遍历的方法我们也许要遍历1百万遍。 感谢阅读如有不足恳请指正谢谢
