做网站运营如何提升用户粘度,哈尔滨建设工程交易中心,上海公共招聘网怎么打不开,如何进行电商营销推广详解数据结构之二叉树(堆)
树
树的概念
树是一个非线性结构的数据结构#xff0c;它是由 n(n0)个有限节点组成的一个具有层次关系的集合#xff0c;它的外观形似一颗倒挂着的树#xff0c;根朝上#xff0c;叶朝下#xff0c;所以称呼为树。每颗子树的根节点有且只…详解数据结构之二叉树(堆)
树
树的概念
树是一个非线性结构的数据结构它是由 n(n0)个有限节点组成的一个具有层次关系的集合它的外观形似一颗倒挂着的树根朝上叶朝下所以称呼为树。每颗子树的根节点有且只有一个前驱可以0个有多个后继。
如图这两颗树就不是树形结构子树是不会相交的除根节点外每个节点有且只有一个父节点一颗有n个节点的树有n - 1条边。 根节点 根节点没有前驱节点如图9为根节点。 父节点若一个节点含有子节点则称这个节点为字节的的父节点如图9为12个父节点。 子节点/孩子节点一个节点含有父节点那这个节点就为孩子节点如图12. 节点的度一个节点右多少个孩子节点那他的度就为多少。 树的度为最大节点的度如上图12这个节点的度为3它是最大的那他就为树的度。 树的层次从根开始定义为第一层根节点的子节点为第二层以此类推。 树的深度、高度树的最大层次如图树最大有4层那树的深度为4。 叶子节点度为0的节点为叶子节点。 分支节点度不为0的节点。 兄弟节点具有相同父节点的节点互称为兄弟节点。 节点的祖先从根到该结点所经分⽀上的所有结点 所有节点的祖先为根节点 节点的子孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙 除根节点外所有节点是根节点的子孙。 森林由m颗不相加的树的集合m 0。
二叉树
在树形结构里最常用的就是二叉树一颗二叉树是节点的有限集合该集合右一个根节点加上两颗左子树和右字树组成或者为空。
二叉树形态
空二叉树只有一个根节点根节点只有左子树根节点只有右子树根节点有左右子树
二叉树的特点
二叉树不存在度大于2的节点二叉树的节点有左右之分次序不能颠倒而二叉树又是有序树
特殊二叉树 满二叉树
满二叉树是节点总数满足 2^k - 1k为树的最大层数的树每一层的节点个数都达到最大值。 完全二叉树
完全二叉树对于一颗具有n个节点的二叉树按层序编号如果编号为i1 i n的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同这颗二叉树称为完全二叉树。
例如
序号为2的节点没有右节点而序号为3的节点先有了序号为5、6的节点此时它们的序号与上图的完全二叉树序号并不相同那它就不是完全二叉树。
正确的完全二叉树
判断完全二叉树时可以先按照当前二叉树的层次画一个或着心里想一个满二叉树判断对应位置上的序号大小是否一致。
完全二叉树的性质
叶子节点只能出现在最后两层最下层的叶子节点一定集中在左部连续的位置倒数第二层有叶子节点那他一定在右部连续位置
二叉树的性质
二叉树总节点个数深度为k的二叉树具有n 2^k - 1个节点
二叉树第i层的节点个数第i层的节点有2^(i-1) 个。
对应具有n个节点个数的二叉树对应的深度为k logn 1底数为2
堆
堆将一个元素集合k里所有数据按照完成二叉树的存储方式存储。
这里的堆是基于顺序存储结构实现因为堆是一种要求严格的二叉树在节点的顺序上必须是从左孩子节点开始放数据不会允许一个节点先有右孩子节点而没有左孩子节点。
有了这种特殊的限制在数组里就可以利用节点所对应的下标来寻找对于的父亲节点孩子节点。‘
对于具有 n 个结点的完全⼆叉树如果按照从上到下从左到右的数组顺序对所有结点从 0 开始编号则对于序号为 i 的结点有
i 0 ,i 位置的节点的双亲序号为(i - 1) / 2i 0 为根节点为双亲。
若 2i 1 n,左孩子序号2i 1否则2i 1 n无左孩子
若 2i 2 n,右孩子序号2i 2否则2i 2 n无右孩子
堆的分类 小根堆小堆父亲节点的大小总是小于孩子节点 大根堆大堆父亲节点的大小总是大于孩子节点
不满足以上两种的堆是无序的无效的堆必须对其的循序进行调整。
typedef int HeapDataType;
typedef struct Heap
{HeapDataType* arr;int size;int capacity;
}Heap;功能实现
//初始化
void HpInit(Heap* hp);
//销毁
void HpDestory(Heap* hp);
//堆尾放数据
void HpPush(Heap* hp, HeapDataType x);
//出堆顶数据
void HpPop(Heap* hp);
//自下向上调整
void AdjustUp(HeapDataType* arr, int child);
//自上向下调整
void AdjustDown(HeapDataType* arr, int parent, int n);
//返回堆顶数据
HeapDataType HeapTop(Heap* hp);
//返回堆的数据个数
int HeapSize(Heap* hp)
//交换函数Swap
void Swap(HeapDataType* x, HeapDataType* y);初始化、销毁
初始化基于顺序结构实现的堆将指向堆的变量的地址传递过来使用一级指针接收实现形参的改变影响到实参。初始化堆只需对其指针置空、空间大小和栈顶置0即可。
void HpInit(Heap* hp)
{assert(hp);if(hp-arr)free(hp-arr);hp-arr NULL;hp-capacity hp-size 0;
}销毁堆堆的空间是使用函数动态开辟的那他得使用对应得free对空间进行释放让后将堆的空间大小和size置0即可。
需要注意的是若数组本身是空的那就不能对齐进行释放在使用free释放前还需要使用if语句进行判断。是否为空。
void HpDestory(Heap* hp)
{assert(hp);if (hp-arr)free(hp-arr);hp-capacity hp-size 0;
}堆插入数据、自下向上调整算法
在堆里插入数据有着严格的要求必须按照这从左节点到右节点的顺序放入数据不能跳过左节点先放入右节点的数据。
现在想要在堆里放入一个数据不能是我想在哪放就在哪放的必须先将节点20的右孩子节点放入数据才能到下一层放入数据。这些严格的要求也导致了用数组实现堆存放数据也是从末尾开始。
而前文说过堆是按照一定顺序存放的在如图的小堆里我放入了一个10的数据改如何应对呢这里就得使用到堆的自下向上调整函数其函数功能是将堆里新放入的数据按照小堆的结构摆放。
堆插入数据
在堆里放入数据只需在数组末尾存放即可。
需要注意的是对空间大小的判断以及自下向上调整算法。
在函数里需要对有效数据个数和空间大小是否相等进行判断所以使用if语句在if语句里使用realloc函数开辟为啥不使用malloc函数呢~我们需要实现的动态开辟存放的数据越多空间越开越大malloc函数做不到。扩容时需扩容原空间的2倍或3倍可以减少扩容操作的频率。如果每次只增加少量空间那么在元素数量增长时需要频繁进行扩容操作这会降低性能。
在完成对空间大小的判断与开辟后将待插入数据放入数组末尾即可。然后使用自下向上调整算法对新放入的数据根据大小调整顺序。
void HpPush(Heap* hp, HeapDataType x)
{assert(hp);if (hp-capacity hp-size){int newcapacity hp-arr 0 ? 4 : hp-capacity * 2;HeapDataType* newarr (HeapDataType*)realloc(hp-arr, sizeof(HeapDataType) * newcapacity);if (newarr NULL){perror(malloc );exit(1);}hp-arr newarr;hp-capacity newcapacity;}hp-arr[hp-size] x;AdjustUp(hp-arr, hp-size);hp-size;//交换完在进行加加提前加加hp-arr[hp-size] x;然后在调整会有越界情况
}自下向上调整算法
这里将交换两个数据的功能封装为一个函数后续实现出堆顶数据还需要使用它。
void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType temp *x;*x *y;*y temp;
}计算父亲节点的大小父亲 孩子 - 1 / 2。
自下向上算法的实现基于二叉树的性质更具孩子节点找父亲节点。新插入的孩子节点需要与父亲节点进行比较大小若孩子节点小于父亲节点就交换顺序而新的父亲节点又是前一个节点的孩子节点同样需要判断其大小然后交换顺序若父亲节点小于孩子节点的话就不需要继续循环下去使用break跳出。
循环结束的条件当child不大于0时跳出若child都小于0了还怎么访问堆里的数据而child刚好为0的说明此时孩子指的是根节点根节点并不需要交换所以child不大于0时跳出即可。
从孩子开始为堆的最后一个数据所以称为自下向上调整。 void AdjustUp(HeapDataType* arr, int child)//传递数组和数组的大小也就是插入数据的位置
{int parent (child - 1) / 2;while (child 0){//小堆//大堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);//交换child parent;//交换完后更新孩子节点的位置。parent (child - 1) / 2;//跟新父亲节点的位置为新孩子节点的父亲节点。}else{break;}}
}建大堆
若我们需要一个大堆这里只需要改变if语句里的条件判断将找更小的逻辑改为找更大的数据即可。
出堆顶数据、自上向下调整算法
出堆顶数据也有严格的要求并不是将数组末尾的数据删除直接将size减1也不是让数组所有数据前移一位这将会到的堆的顺序全部乱套了~坏掉了
出堆顶数据
出堆顶数据是将堆顶的数据与堆尾的数据进行交换然后让size减1堆的数据个数最后将新的堆顶数据按照小堆的摆放调整顺序。
出堆顶数据时需要注意堆不能为空以及数组也不能为空否则将会做坏事导致统子哥报错。
void HpPop(Heap* hp)
{assert(hp hp-size);Swap(hp-arr[0], hp-arr[hp-size - 1]);//将最后一个元素与堆顶元素交换hp-size--;//调整顺序AdjustDown(hp-arr, 0, hp-size);
}自上向下调整算法
左孩子孩子 父亲 * 2 1child n
右孩子孩子 父亲 * 2 2child n
前文提过的自下向上调整算法是向上找父亲节点而自上向下算法是向下找孩子节点更具传递过来的参数 parent 向下个找孩子。
与前一个调整算法相比它会进行更多的判断因为向下找的孩子有两个。而我们默认的孩子起始是左孩子节点。
在对孩子节点与父亲节点比较大小交换之前还需要比较左孩子节点和右孩子节点arr[child] arr[child 1]若左孩子节点大于有孩子那child就需要加1但还有个前提万一child加1后刚好不满足 child n的条件从而在后续的交换里导致数组越界访问所以在if语句里还需要加上一条判断 child 1 n。
执行孩子节点与父亲节点交换的if语句里在交换完两个节点后需要更新新的父亲节点和孩子节点来是否存在比父亲节点还小的值。最后若孩子节点大于父亲节点那就说明不需要交换使用break跳出循环即可。
void AdjustDown(HeapDataType* arr, int parent, int n)
{int child parent * 2 1;while (child n){//小堆//大堆if (child 1 n arr[child] arr[child 1]){child;}//小堆//大堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}建大堆
若我们需要一个大堆那该如何调整这里只需要改变其两个if语句里的条件判断将找更小的逻辑改为找更大的数据即可。
返回堆顶数据
将数组下标为零的元素返回即是堆顶。
HeapDataType HeapTop(Heap* hp)
{assert(hp hp-size);return hp-arr[0];
}返回堆的数据个数
将size的大小返回即是堆存储的数据个数。
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}源码
Heap.h
#pragma once#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int HeapDataType;
typedef struct Heap
{HeapDataType* arr;int size;int capacity;
}Heap;//初始化
void HpInit(Heap* hp);//销毁
void HpDestory(Heap* hp);//堆尾放数据
void HpPush(Heap* hp, HeapDataType x);
//出堆顶数据
void HpPop(Heap* hp);
//自下向上调整
void AdjustUp(HeapDataType* arr, int child);
//自上向下调整
void AdjustDown(HeapDataType* arr, int parent, int n);
//返回堆顶数据
HeapDataType HeapTop(Heap* hp);
//返回堆的数据个数
int HeapSize(Heap* hp)
//交换函数Swap
void Swap(HeapDataType* x, HeapDataType* y);Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include Heap.h//初始化
void HpInit(Heap* hp)
{assert(hp);hp-arr NULL;hp-capacity hp-size 0;
}//销毁
void HpDestory(Heap* hp)
{assert(hp);if (hp-arr)free(hp-arr);hp-capacity hp-size 0;
}
void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType temp *x;*x *y;*y temp;
}
//自下向上调整
void AdjustUp(HeapDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
//堆尾放数据
void HpPush(Heap* hp, HeapDataType x)
{assert(hp);if (hp-capacity hp-size){int newcapacity hp-arr 0 ? 4 : hp-capacity * 2;HeapDataType* newarr (HeapDataType*)realloc(hp-arr, sizeof(HeapDataType) * newcapacity);if (newarr NULL){perror(malloc );exit(1);}hp-arr newarr;hp-capacity newcapacity;}hp-arr[hp-size] x;AdjustUp(hp-arr, hp-size);hp-size;
}//自上向下调整
void AdjustDown(HeapDataType* arr, int parent, int n)
{int child parent * 2 1;while (child n){if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
//出堆顶数据
void HpPop(Heap* hp)
{assert(hp hp-size);Swap(hp-arr[0], hp-arr[hp-size - 1]);//将最后一个元素与堆顶元素交换hp-size--;//调整顺序AdjustDown(hp-arr, 0, hp-size);
}
//返回堆顶数据
HeapDataType HeapTop(Heap* hp)
{assert(hp hp-size);return hp-arr[0];
}int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
//出堆顶数据
void HpPop(Heap* hp)
{assert(hp hp-size);Swap(hp-arr[0], hp-arr[hp-size - 1]);//将最后一个元素与堆顶元素交换hp-size--;//调整顺序AdjustDown(hp-arr, 0, hp-size);
}
//返回堆顶数据
HeapDataType HeapTop(Heap* hp)
{assert(hp hp-size);return hp-arr[0];
}int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}
