哪个网站可以做高像素动图,北京网站推广|网站制作|网络推广|网站建设,建设工程公司网站,WordPress推送百家号个人主页~ 二叉树-堆 一、树的概念及结构1、概念2、相关概念3、树的表示4、树的实际应用 二、二叉树的概念和结构1、概念2、特殊二叉树3、二叉树的性质4、二叉树的存储结构#xff08;1#xff09;顺序存储#xff08;2#xff09;链式存储 三、二叉树的顺序结构以及实现1、… 个人主页~ 二叉树-堆 一、树的概念及结构1、概念2、相关概念3、树的表示4、树的实际应用 二、二叉树的概念和结构1、概念2、特殊二叉树3、二叉树的性质4、二叉树的存储结构1顺序存储2链式存储 三、二叉树的顺序结构以及实现1、二叉树的顺序结构2、堆的概念及结构1小根堆2大根堆 3、堆的实现1堆的向上调整算法--堆的创建①一般方法②向上调整建堆 2向上调整算法的时间复杂度3向下调整算法维护堆4向下调整算法的时间复杂度 一、树的概念及结构
在我们学习二叉树之前我们先要了解一下树的概念二叉树就是一种树
1、概念
树是一种非线性的数据结构它是由n个有限节点组成一个具有层次关系的集合因为根据它所画出的抽象图看起来像一棵倒挂着的树它的根朝上树叶朝下
一棵树最顶上的节点叫做根节点一棵树有且只有一个根节点根节点没有前驱节点也就是说根节点上面就没有节点了
除了根节点以外其余节点被分成N个互不相交的集合我们形象的来说就是一棵树的叶子和树枝是多对一的概念也就是说一个树枝可以有多个叶子或者没有叶子但是一个叶子只能长在一个树枝上一条小树枝只能长在一条大树枝上所以树是递归定义的
2、相关概念
节点的度一个节点含有子树的个数A的度是3C的度是0
叶节点终端节点度为0的节点称为叶节点GHIJKL
分支节点非终端节点度不为0的节点ABDF
子节点一个节点含有的子树的根结点B是A的子节点
父节点若一个节点含有子节点则这个节点称为其子节点的父节点A是B的父节点
兄弟节点这里的兄弟指的是亲兄弟也就是具有相同父节点的节点BCD是兄弟节点
树的度整棵树的度是这棵树中的节点的度中最大的那个度这棵树最大是3
节点的层次根为第一层根的子节点为第二层子节点的子节点为第 三层以此类推第一层A第二层BCD第三层FGHI第四层JKL
树的高度深度树中节点的最大层次四层
堂兄弟节点父亲为同一层的节点HI
节点的祖先从根到该节点所经分支上的所有节点J节点的祖先是ABF
子孙以某节点为根的子树中任意节点都称为该节点的子孙B-L都是A的子孙
森林由N棵N0互不相交的树组成的集合称为森林
树的概念都是由人类的亲缘关系决定的我们在记忆的时候可以结合我们人类的亲缘关系来记忆
3、树的表示
树的表示方法有很多种如果我们再像以前一样定义一个结构体其中存放指针和数据那样就不行了因为我们不知道一个节点有多少子树这样就没办法定义树的节点的结构体这里我们有一个最好的办法就是左孩子右兄弟法
左孩子右兄弟法
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点也就是最左边的孩子struct Node* _pNextBrother; // 指向其下一个兄弟结点就是右边第一个兄弟DataType _data; // 结点中的数据域
};左孩子右兄弟法就是一个指针指向左边第一个孩子右指针指向右边第一个兄弟 图画的不太好看将就一下 红色的线是左孩子 蓝色的线是右兄弟 这样我们可以简洁并且快速地找到这棵树所有的分支
4、树的实际应用
文件系统的目录就是树的应用 E盘 这里就是树的应用文件系统的目录是用树的结构实现的
二、二叉树的概念和结构
1、概念
二叉树就是在树的基础上加上特殊 二叉树是由一个根节点加上一个左子树和一个右子树组成的 二叉树不存在度大于2的节点 二叉树是有序树因为它的子树有左右之分次序不能颠倒
2、特殊二叉树
1满二叉树 一个二叉树如果每一个层的节点数都达到最大值那么这个二叉树就是满二叉树
2完全二叉树 完全二叉树是效率很高的二叉树它的最后一层可以不满最后一层之前的层都是满的然后最后一层的节点是需要按序排列的满二叉树是一种特殊的完全二叉树
3、二叉树的性质
若规定根节点的层数为1具有n个节点的满二叉树的深度hlog₂n1
对于具有n个节点的完全二叉树如果按照从上到下从左到右的数组顺序对所有节点从0开始编号则对于序号为i的节点有如下几个性质 ①若i0i位置节点的父亲序号i-1/2i0i为根节点编号无父亲节点 ②若2i1n左孩子序号为2i1并且2i1≥n否则无左孩子 ③若2i2n右孩子序号为2i2并且2i2≥n否则无右孩子
4、二叉树的存储结构
二叉树有两种存储结构一种是顺序存储另一种是链式存储
1顺序存储
顺序存储就是使用数组来存储一般只适合表示完全二叉树因为不是完全二叉树会有空间上的浪费二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树
2链式存储
链式存储就是使用链表来存储通常的方法是链表节点由三个域组成分别是数据域以及左右指针域左右指针存储左右孩子的地址
链式结构又分为二叉链和三叉链这里使用的是二叉链
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* Left; // 指向左孩子struct BinTreeNode* Right; // 指向右孩子BTDataType data; // 值域
};// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* Parent; // 指向父节点struct BinTreeNode* Left; // 指向左孩子struct BinTreeNode* Right; // 指向右孩子BTDataType data; // 值域
};三、二叉树的顺序结构以及实现
1、二叉树的顺序结构
现实中我们经常把堆一种二叉树使用顺序结构的数组来存储这里的堆与malloc位置的堆的概念是不同的malloc位置的堆是操作系统中的内存管理这里的堆是我们人为实现的一种数据结构
2、堆的概念及结构
把一堆数据按照完全二叉树的顺序存储方式存储在一个一维数组中并且满足第i项 ≤ 第2i2项i为自然数则称为堆根节点最大的堆叫大堆大根堆根节点最小的堆叫小堆小根堆
性质 ①堆总是一颗完全二叉树 ②堆中某个节点的值总是不大于或不小于其父节点的值
1小根堆
逻辑结构 物理结构存储结构
2大根堆
逻辑结构 物理结构存储结构 这里的存储结构中的数据不一定是有序的也可以不是升序或者降序但是大堆的父节点一定比子节点大小堆的父节点一定比子节点小
3、堆的实现
1堆的向上调整算法–堆的创建
①一般方法
我们在使用堆的向下调整算法之前要保证左右子树都要是堆那么在使用之前我们先要创建堆
我们创建一个数组在逻辑上可以看做一颗完全二叉树然后我们通过算法把它构建成为一个堆从倒数第一个叶子节点开始调整一直到根节点就可以调整成堆
int arr[] {1,4,7,2,5,9};最后的9与它的父节点7交换 19再交换 然后再检查最后一个叶子节点重复上面的步骤虽然这样最终可以建立一个堆但这样效率特别低所以我们有了向上调整算法来建堆
②向上调整建堆
现在我们有一个数组在逻辑上看成一棵完全二叉树我们要创建一个堆可以用向上调整算法
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//因为除法向下取整所以右孩子也能//因为是一颗完全二叉树所以父节点总是可以通过子节点减1除以二找到//while (parent 0)while (child 0)//这里用子节点作为循环条件因为child可能调整到根节点上{if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}//大于就交换把此时的父节点变成子节点父节点的父节点变成父节点比较上一层的关系else{break;}}
}从二叉树的根节点的左孩子开始调整按照下标依次调整最终会建成一个堆 图演示 下标1向上调整 下标2向上调整 下标3调整两次第二次小于7不调 下标4调整两次第二次小于7不调
下标5调整两次 第一次 第二次 这样就建成一个堆了
2向上调整算法的时间复杂度 设树的高度为h 第1层2^0个节点需要向上移动0层 第2层2^1个节点需要向上移动1层 第3层2^2个节点需要向上移动2层 …… 第h-1层2^(h-2)个节点需要向上移动h-2层 第h层2^(h-1)个节点需要向上移动h-1层 将它们相加 解得原式22^h*(h-2)
遍历一遍为N 2^h
去掉不重要的项得时间复杂度O(N*log₂N)
3向下调整算法维护堆
当我们需要将堆顶的数据删除掉那么这个堆就没有了根如果再重新进行建堆会浪费很多的时间这里有一种方法的时间复杂度小于重新建堆这种算法就是向下调整算法
void AdjustDown(int* a, int n, int parent)//n是数组a的数据个数
{int child parent * 2 1;//左孩子while (child n){// 选出左右孩子中大的那个if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}//谁大谁是爹else{break;}}
}4向下调整算法的时间复杂度 设树的高度为h 第1层2^0个节点需要向下移动h-1层 第2层2^1个节点需要向下移动h-2层 第3层2^2个节点需要向下移动h-3层 …… 第h-1层2^(h-2)个节点需要向下移动1层 第h层2^(h-1)个节点需要向下移动0层 将它们相加之后由错位相减法得 2^h-1-h 因为N 2^h所以原式N-1-log₂N
因为当h趋于无穷大时N远大于log₂N所以时间复杂度O(N) 今日分享就到这~
