个人网站论坛展示,网站建设推广哪家专业,seo职业,北京vi设计公司怎么样写在前面
在学习数据结构前#xff0c;我们早就听说大名鼎鼎的树#xff0c;例如什么什么手撕红黑树大佬呀#xff0c;那这篇笔记不才就深入浅出的介绍二叉树。 文章目录 写在前面一、树的概念及结构1.1、数的相关概念1.2、数的表示1.3 树在实际中的运用#xff08;表示文…写在前面
在学习数据结构前我们早就听说大名鼎鼎的树例如什么什么手撕红黑树大佬呀那这篇笔记不才就深入浅出的介绍二叉树。 文章目录 写在前面一、树的概念及结构1.1、数的相关概念1.2、数的表示1.3 树在实际中的运用表示文件系统的目录树结构 二、二叉树概念及结构2.1 特殊的二叉树2.2、二叉树的存储结构2.2.1、顺序存储2.2.2、链式存储 三、二叉树(堆)的顺序结构3.1、堆的概念及结构3.2、堆的调整3.2.1、堆的向上调整向上调整的代码实现 3.2.2、堆的向下调整向下调整的代码实现 四、堆的创建4.1、堆的创建的代码实现4.2、计算方法二建堆的时间复杂度 五、堆排序5.1、堆排序的代码实现 六、堆的实现6.1、堆的结构体定义6.2、堆的初始化6.3、堆的数据插入6.4、堆的删除6.5、取堆顶的数据6.6、堆的数据个数6.7、堆的判空6.8、堆的销毁 七、TOPK问题 一、树的概念及结构
在学习二叉树之前我们必须得明白什么是树。 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 因此树是递归定义的。 注意树形结构中子树之间不能有交集否则就不是树形结构(如下图)
1.1、数的相关概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如下图P的祖先是J、E、A 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林
1.2、数的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
1.3 树在实际中的运用表示文件系统的目录树结构
如下图 二、二叉树概念及结构
二叉树是一棵特殊的树该特点是
一棵二叉树是结点的一个有限集合该集合可以为空或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成每个节点最大的度是2二叉树的子树有左右之分在每棵树中次序不能颠倒只能小往大或者大往小因此二叉树是有序树
注意对于任意的二叉树都是由以下几种情况复合而成的
2.1 特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2(i-1)个结点. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2h-1 - 1。 结合结论12可以推导出高度为h的完全二叉树节点数量的范围[2(h-1), 2h-1]。 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0n2 1。即度为0永远比度为2的多一个 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2(n1)。 (pslog2(n1) 是log以2为底n1为对数) 推导过程如下图:
2.2、二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 2.2.1、顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树
2.2.2、链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链其中红黑树等会用到三叉链。当前我们本篇笔记主要讲解是二叉链。 链式存储的结构体
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};三、二叉树(堆)的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
3.1、堆的概念及结构
堆是可以理解为有序的完全二叉树它一种特殊二叉树其中将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
堆的性质
在大堆中某个节点的值总是大于或等于其父节点的值 在小堆中某个节点的值总是小于或等于其父节点的值堆总是一棵完全二叉树。
堆中的逻辑结构与物理结构 物理结构怎么转变成逻辑结构(如下图) 在上图中我们也可以清楚看到随着数组下标的增加对应着堆的节点增加这样也符合堆从左到右增加节点的顺序。 其中最重要的是父子之间的节点是有关系的
在数组中我们知道子节点(child)后只需要(child-1) / 2就可以算出父节点。 因为在数组中左节点一定在奇数位右节点一定在偶数位整形运算中(偶数位-1) / 2得到的结果是整数这样就可以算出父节点的位置。(如下图) 在数组中我们知道父节点(parent)后只需要与求父节点相反就可以算出父节点。 计算左节点parent*2 1计算右节点parent*2 2
结合3.1与3.2可以轻松理解数组表示堆的方法
3.2、堆的调整
在上述的3.1与3.2中我们知道了如何用数组表示堆但是堆的要求是大堆中某个节点的值总是大于或等于其父节点的值、小堆中某个节点的值总是小于或等于其父节点的值
3.2.1、堆的向上调整
在一颗树中如果我们插入了一个值就必须判断这个数是否符合当前堆对这个位置的限制。数的高度为h,有n个节点如下图 在数组属于尾插了一个9在大堆中如上图显示这个时候9与其父节点的5不符合大堆的性质。此时我们需要交换父子节点之间的值。如下图 相互调换完成后我们继续比较当前节点与其父节点的值是否符合大堆的需求。循环比较交换后我们可以得到下图 当进行插入时都会向上调整向上调整最多调整h次时间复杂度就为O(logN)次
向上调整的代码实现
//向上调整
void AdjustUp(HPDataType* a, int child) {int farent (child - 1) / 2;//while(farent ! 0) {如果写父亲不等于0则需要结束循环后在判断一次父亲等于0时的情况while(child 0){//把孩子用来判断大于0结束循环这时循环就一定会判断父亲等于0时的情况//只有父亲等于0时父亲给孩子赋值孩子才会等于0if (a[farent] a[child]) {return;}HPDataType num a[farent];a[farent] a[child];a[child] num;child farent;farent (child - 1) / 2;}/*if (a[farent] a[child]) {如果写父亲不等于0则时判断一次父亲等于0时的情况return;}HPDataType num a[farent];a[farent] a[child];*/
}代码实现与我们分析结构时相同。父亲结点 (child - 1) / 2;if (a[farent] a[child])是大小堆选择的关键。 如果选择父节点大于子节点结束交换(a[farent] a[child])创建大堆。如果选择子节点大于父节点结束交换(a[farent] a[child])。创建小堆。 3.2.2、堆的向下调整
在一颗树中如果我们已经实现了一个堆现在要删除堆中的一个数据在堆中只有删除堆顶的数据才有意义因为在大堆中堆顶代表着堆中最大值其他结点没有意义在小堆中堆顶代表着堆中最小值其他结点没有意义。数的高度为h,有n个节点
向下调整规则
左右子树必须是一个堆才能调整堆顶与子结点的较大值进行交换循环交换直到原堆顶元素到规定结点
首先把堆顶元素与数组中最后一个元素进行调换(如下图) 这时候我们删除最后一个元素这样左子树和右子树依旧维持着大堆结构 为了确保删除后结构还是大堆结构我们把堆顶1根据规则进行向下调整与子结点较大值进行交换这样可以确保堆顶一定比子结点大(维持大堆结构)。 循环交换可得下图 这样我们就完成了向下调整把数据重新恢复成大堆并且此时在原数据中第二大的数据成为了堆顶这样也把向下调整赋值了新意义
当每次删除都进行向下调整向下调整最多调整h次时间复杂度就为O(logN)次
向下调整的代码实现
void HeapSwap(HPDataType* a, int n1, int n2) {//交换数据HPDataType num a[n1];a[n1] a[n2];a[n2] num;
}//向下调整
void AdjustDown(HPDataType* a, int capacity, int farent) {assert(a); // 确保数组指针不为空HPDataType child farent * 2 1; // 计算当前父节点的左子节点索引while (child capacity) { // 如果当前节点有子节点// 确保右子节点大于左子节点如果右子节点存在if (child capacity - 1 a[child 1] a[child]) {child child 1; // 选择右子节点}// 如果父节点小于子节点大堆则交换父子节点if (a[child] a[farent]) { // 大堆调整HeapSwap(a, child, farent); // 交换父节点和子节点的值farent child; // 更新父节点为被交换的子节点child farent * 2 1; // 重新计算新的左子节点索引} else {break; // 如果父节点不小于任何子节点结束调整}}
}
与逻辑分析一致。默认左节点大于右节点进行向下调整。if (child capacity -1 a[child 1] a[child]) child capacity -1防止子结点(child)越界。a[child 1] a[child]判断右结点是否大于左结点。若右节点大于左结点就把child赋值给右结点。 用于创建大小堆的关键if (a[child] a[farent])。 如果子结点大于父结点进行交换则是创建大堆。a[child] a[farent]如果子结点小于父结点进行交换则是创建小堆。a[child] a[farent] 四、堆的创建 在顺序存储二叉树中底层逻辑和数组一致那么一个普通数组我们可以把它看为一个顺序存储的二叉树这样我们就可以在一个普通数组中创建一个堆。 创建堆的方法 方法1把数组全部元素遍历以入堆的形式向上调整不使用因为时间复杂度是O(N*logN)效率极其低下
方法2 把数组本身当作堆的本身在最后一个非叶子结点开始向下调整把一个数组拆分为一个个小二叉树把每一个小二叉树都进行向下调整形成堆之后再结合每个堆形成一个完整的堆此时时间复杂度是O(N)。
举例方法2(方法1不举例) 我们把数组[1,5,8,9,70,3,4,6,21,95] 创建成为大堆(大小堆的创建逻辑一样)。
先把数组画成二叉树的逻辑结构。(如下图) 根据上图找到最后一个非叶子结点后我们可以把上面的二叉树划分为5个小二叉树之后分别对这5个小二叉树进行向下调整形成堆。(如下图) 观察上图我们发现每一个小二叉树的树顶元素都是上一个小二叉树树顶的下标-1,因为物理结构中此时是数组[1589703462195]之后每次下标-1就可以找到下一个小二叉树了。
首先找到最后一个非叶子结点即70结点 把70结点作为一棵二叉树进行向下调整实现大堆结构。此时子结点的95大于父结点的70进行交换。(如下图)此时原70结点这个二叉树就形成了大堆 完成交换后我们需要继续完成其他小二叉树进行向下调整。只需要下标-1即可进入小二叉树2。(如下图) 此时进行向下调整。 下标-1即可进入小二叉树3。但是小二叉树3本身就是大堆所以不需要向下调整。 这时小二叉树4的左子树和右子树都是堆(如下图),可以进行向下调整 向下调整后可得 在下标-1后到达树顶1观察上图可以知这时左右子树都为堆可以进行向下调整。最终如下图 此时就完成了大堆的创建。物理结构[9570821534691]
4.1、堆的创建的代码实现
//创建堆
void HeapCreate(HPDataType* arr, int len) {int child len - 1;int farent (child - 1) / 2;for (int i farent; i 0; i--) {AdjustDown(arr, len, i);}
}最后叶子节点的父节点就是堆中的最后一个非叶子结点之后在最后一个非叶子节点循环向下调整。即可完成对的创建。 4.2、计算方法二建堆的时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 五、堆排序 在堆的的逻辑结构中是严格遵循有序但这并不意味着整个堆的物理存储结构是有序的。堆排序的目的是对堆中的元素进行排序通过堆这种数据结构的特性来实现元素的排序。 排序中分为升序和降序堆排序即利用堆的思想来进行排序
排升序对应着建大堆排降序对应着建小堆
堆排序的方法
因为堆排序的逻辑与堆的删除逻辑是完全一致的都是先把堆顶元素与最后一个元素进行交换之后向下调整。与删除不同的是删除需要把数组中最后一个元素完全删除排序只需要不再理会数组最后一个元素不用真正删除元素。
排升序建大堆的原因在把堆顶元素与最后一个元素进行交换之后堆中的中最大的值被放置在物理结构的最右边如此循环即可完成结构的升序。降序同理 把堆中元素进行升序排序 我们使用上述大堆的例子创建有序的物理结构物理结构[9570821534691] 首先交换堆顶与最后一个元素(如下图) 在交换完成后逻辑结构上不再把95结点当作堆的结点之后进行向下调整(如下图) 此时物理结构为[7021895346195]。这样就把最大值放置在物理结构最右边并且忽略最后一个结点后其他结点依旧保持着大堆结构。(与删除堆顶逻辑完全相同)
循环上述操作可得下图 一定次数的循环后会得到下图 观察上图可以看到此时物理结构:[8631549217095]只要循环次数足够就可以把物理结构排为升序
最终可得下图 此时我们就完成了堆中元素的升序排序。物理结构为[1345689217095]。
5.1、堆排序的代码实现
void HeapSort(HPDataType* arr, int capacity, int farent) {assert(arr); // 确保传入的数组指针不为空int cp capacity; // 存储堆的初始容量// 当堆中还有元素时进行排序while (cp ! 0) {// 将堆顶元素最大或最小元素与当前堆的最后一个元素交换HeapSwap(arr, 0, cp - 1); // 减少堆的有效大小去除已排序的最大元素--cp;// 调整堆结构确保堆的性质依然保持AdjustDown(arr, cp, farent);}
}
首先把堆顶元素与最后一个叶子节点的元素进行交换。之后--元素个数把已经交换完成的最大值(最小值)忽略。完成后再向下调整。把交换完成后的顺序表重新调整为大堆(小堆)。 六、堆的实现
在堆的实现中不管是大堆还是小堆代码的逻辑是相同的。这里以大堆为例
6.1、堆的结构体定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;//顺序表的大小int _capacity;//当前元素个数
}Heap;创建顺序存储的二叉树。堆的物理结构使用顺序表的结构实现
6.2、堆的初始化
void HeapInit(Heap* php) {HPDataType* p1 (HPDataType*)malloc(sizeof(HPDataType) * 4);assert(p1);php-_a p1;php-_size 4;php-_capacity 0;
}初始化是创建物理结构所以与初始化顺序表相同。
6.3、堆的数据插入
void HeapPush(Heap* hp, HPDataType x) {assert(hp); // 确保堆指针不为空// 检查堆是否已满若满则扩展堆的容量if (hp-_capacity hp-_size) {// 重新分配内存将堆数组的大小扩大为原来的两倍HPDataType* p1 (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * hp-_size * 2);assert(p1); // 确保内存分配成功hp-_a p1; // 更新堆数组指针hp-_size * 2; // 更新堆的总容量}// 将新元素添加到堆的末尾hp-_a[hp-_capacity] x;hp-_capacity; // 增加堆中元素的个数// 调整堆结构确保堆的性质得到维护AdjustUp(hp-_a, hp-_capacity - 1);
}
只需要把数据插入到顺序表的最后一个元素的下一个位置后进行向上调整即可完成数据的插入。
6.4、堆的删除
void HeapPop(Heap* hp) {assert(hp);HeapSwap(hp-_a, hp-_capacity - 1, 0);//交换--hp-_capacity;int farent 0;AdjustDown(hp-_a, hp-_capacity,farent);//向下调整}把树顶元素与最后的叶子结点交换后--capacity把保存元素个数的数据-1做到删除效果之后向下调整维持大堆结构。
6.5、取堆顶的数据
HPDataType HeapTop(Heap* hp) {assert(hp);return hp-_a[0];
}直接返回顺序表头元素即可
6.6、堆的数据个数
int HeapSize(Heap* hp) {assert(hp);return hp-_capacity;
}直接返回元素个数即可
6.7、堆的判空
bool HeapEmpty(Heap* hp) {return hp-_capacity 0;
}把保存元素个数的变量与0判断即可
6.8、堆的销毁
void HeapDestory(Heap* hp) {while (!HeapEmpty(hp)) {HeapPop(hp);}}循环删除直到为空即可
七、TOPK问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 在数据量大的情况下排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 保存前k个最大的元素则建小堆这样可以把堆中最小元素作为堆顶用来判断是否适合入堆。保存前k个最小的元素则建大堆这样可以把堆中最大元素作为堆顶用来判断是否适合入堆。 用剩余的N-K个元素依次与堆顶元素来比较满足条件则替换堆顶元素
代码实现
void HeapTopK(HPDataType* arr, int N, int K) {assert(arr); // 确保数组指针不为空int child K - 1; // 设置子节点为第K个元素的索引从0开始int farent (child - 1) / 2; // 计算最后一个非叶子节点的索引// 通过调整堆结构将前K个元素构建成一个堆for (int i farent; i 0; i--) {AdjustDown(arr, K, i); // 从最后一个非叶子节点开始向下调整维护堆性质}// 遍历剩余的元素for (int i K; i N; i) {// 如果当前元素大于堆顶元素第一个元素if (arr[i] arr[0]) {arr[0] arr[i]; // 将当前元素放到堆顶AdjustDown(arr, K, 0); // 重新调整堆保持堆的性质}}
}随机生成一万个小于一百万的元素找出其中最大的前5个元素。 void AdjustDown(HPDataType* a, int capacity, int farent) {assert(a); // 确保数组指针不为空// 计算当前父节点的左子节点索引HPDataType child farent * 2 1; // 当左子节点的索引小于堆的容量时进行调整while (child capacity) {// 如果右子节点存在且小于左子节点选择右子节点if (child capacity - 1 a[child 1] a[child]) {child child 1; // 调整child为右子节点}// 如果当前父节点大于最小的子节点此处是小堆则进行交换if (a[child] a[farent]) { // 小堆调整HeapSwap(a, child, farent); // 交换父节点和子节点的值farent child; // 更新父节点为被交换的子节点child farent * 2 1; // 重新计算新的左子节点索引}else {break; // 如果父节点不大于子节点则结束调整}}
}void test3() {int N 10000; // 定义数组的大小int K 5; // 我们要找的前K个最大值HPDataType* arr (HPDataType*)malloc(sizeof(HPDataType) * N); // 动态分配内存创建大小为N的数组// 使用随机数填充数组范围为0到999999for (int i 0; i N; i) {arr[i] rand() % 1000000; // 随机生成一个数并赋值给数组元素}// 手动设置一些特定位置的值使其比随机生成的数更大arr[50] 1100000; arr[500] 1200000; arr[7000] 1300000; arr[9000] 1400000; arr[9999] 1500000;// 调用HeapTopK函数从数组中找出前K个最大值HeapTopK(arr, N, K);// 对前K个元素进行排序以便按降序输出HeapSort(arr, K, 0);// 输出前5个最大值for (int i 0; i 5; i) {printf(%d , arr[i]); // 打印前K个最大值}// 释放动态分配的内存free(arr);
}以上就是本章所有内容。若有勘误请私信不才。万分感激 如果对大家有帮助的话就请多多为我点赞收藏吧~~~
ps:表情包来自网络侵删
