如何建设物流网站,网站开发和浏览器兼容问题,中关村在线对比,网站维护中是怎么回事提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、树1、树的概念2、树的相关概念3、树的表示 二、二叉树1、二叉树概念2、特殊的二叉树3、二叉树的性质4、二叉树的顺序结构5、二叉树的链式结构 三、堆(二叉树… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、树1、树的概念2、树的相关概念3、树的表示 二、二叉树1、二叉树概念2、特殊的二叉树3、二叉树的性质4、二叉树的顺序结构5、二叉树的链式结构 三、堆(二叉树的顺序结构)1、堆(二叉树的顺序结构)的介绍2、堆(二叉树的顺序结构)的概念及结构3、堆的实现4、堆排序5、计算堆排序中向上调整建堆和向下调整建堆的时间复杂度 前言
一、树
1、树的概念
在学习堆之前我们需要对数据结构中的树结构先有一定的了解。数据结构中的树结构就像一棵真正的倒置的树一样。树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点。 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。 因此树是递归定义的。
2、树的相关概念
节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林
3、树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间 的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
下面为左孩子右兄弟表示法即结点只存储它的第一个孩子和它的右兄弟。这样就可以将一棵树的结构用代码表示出来。
typedef int DataType;
struct TreeNode
{struct TreeNode* firstChild1; //存储第一个孩子结点的地址struct TreeNode* pNextBrother; //指向其下一个兄弟结点DataType data; //结点中的数据域
};二、二叉树
1、二叉树概念
一棵二叉树是结点的一个有限集合该集合: 1.或者为空。 2. 由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。 从上图可以看出 1.二叉树不存在度大于2的结点。 2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的
2、特殊的二叉树
1.满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。
2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3、二叉树的性质
1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h - 1。 3. 对任何一棵二叉树, 如果度为0的结点即叶结点个数为m, 度为2的结点个数为n,则有m n1 4. 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog(n1)。(ps log(n1)是log以2为底n1为对数) 5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 (1).若i0i位置节点的双亲序号(i-1)/2若i0i为根节点编号无双亲节点 (2).若2i1n左孩子序号2i1若2i1n则无左孩子 (3). 若2i2n右孩子序号2i2若2i2n则无右孩子
4、二叉树的顺序结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
5、二叉树的链式结构
本篇文章讲解的为用数组来实现完全二叉树即堆的实现。二叉树的详细介绍可以点击下面链接进入二叉树文章。
三、堆(二叉树的顺序结构)
1、堆(二叉树的顺序结构)的介绍
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
2、堆(二叉树的顺序结构)的概念及结构 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 小根堆如图所示。其每个结点的值都大于双亲结点的值。 大根堆如图所示。其每个结点的值都小于双亲结点的值。
3、堆的实现
堆就是使用顺序结构的的数组来存储的树所以定义堆时就是定义一个动态申请大小的数组。下面我们以建立一个小堆为例。
typedef int HPDataType;
typedef struct Heap
{HPDataType* data;int size;int capacity;
}HP;然后在使用堆时创建一个HP结构体就代表创建了一个堆。堆的初始化就是将堆中用来存储数据的数组先指向NULL然后将size和capacity置为0。
void HeapInit(HP* php)
{assert(php);php-data NULL;php-size 0;php-capacity 0;
}当需要向堆中插入数据时要先检查堆中存储数据的数组是否已满如果满了就要进行扩容。
void HeapPush(HP* php,HPDataType x)
{assert(php);if (php-size php-capacity){int newCapacity (php-capacity 0) ? 4 : (php-capacity) * 2;HPDataType* tmp (HPDataType*)realloc(php-data, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-data tmp;php-capacity newCapacity;}php-data[php-size] x;php-size;//新插入的元素可能不符合堆所以需要向上调整。AdjustUp(php-data, php-size - 1);
}在我们向数组中插入数据时可能新插入的数据已经不满足小根堆的要求这时我们就要将新插入的元素进行向上调整即通过新插入元素在数组中的下标找到其双亲结点然后与双亲结点的值进行比较如果新插入结点的值小于双亲结点的值的话就让这两个结点的值进行比较。例如有如下图所示的一个堆。此时该堆为小根堆。 当要向数组中再插入一个5时此时将数组中的值按堆的逻辑结构表示出来则可以看到堆已经不满足小根堆了这时就需要将新插入的元素5进行向上调整使其满足小根堆的定义 值为5的结点向上调整就是通过5的下标算出其双亲结点值为56因为小根堆中双亲结点的值要小于子结点的值所以要将该组父子结点的值交换。 此时交换后的数组数据变为如下图所示。 可以看到交换一次后值为5的结点还是小于它的双亲结点的值所以还需要将5进行向上调整即将5变为根节点。此时数组表示的小根堆才正确。到此就完成了堆中插入一个新元素然后将该元素向上调整直到该元素到达满足小根堆的位置。 上面的向上调整的代码如下所示。
void Swap(HPDataType* parent, HPDataType* child)
{assert(parent child);//交换内存中两个地址中的值。HPDataType tmp *parent;*parent *child;*child tmp;
}void AdjustUp(HPDataType* arr, int child)
{assert(arr);//如果该结点还不是根结点就一直判断该结点与其父节点值的大小while (child 0){//先求出该结点的父结点int parent (child - 1) / 2;//如果该结点的值小于其父结点的值就让这两个元素交换位置。if (arr[child] arr[parent]){//让这组父子结点交换位置Swap(arr[parent], arr[child]);//然后将新的父节点作为孩子再次与它的父结点比较大小。child parent;}//如果该结点的值大于其父节点说明满足小根堆的要求则不需要处理直接跳出循环else{break;}}
}因为小根堆中每次新结点插入都要进行向上调整所以小根堆中根结点的值是最小的当我们要删除堆中的值时就是删除堆的根结点。此时如果直接将数组中的数据都向前移一位的话则处理完后的数组的值转换为二叉树后不满足小根堆了。此时我们可以将数组中最后一个元素与下标为0的元素进行交换然后将数组中下标为0的元素进行向下调整。如图此时为一个存储小根堆的数组。 当我们需要将堆的根节点进行删除时就先将数组中下标为0的元素和最后一个元素进行交换。 此时将数组的长度-1则值为5的结点就被删除了可以看到此时数组并不能正确表示一个小根堆所以此时要将根结点进行向下调整即将根结点与它的两个孩子中最小的孩子进行比较如果大于它的最小孩子的值就将该对父子结点进行位置交换。交换过后就可以看到此时数组中存储的元素转换为堆后符合小根堆的定义。
void HeapPop(HP* php)
{assert(php);//先将数组中下标为0的元素与数组中最后一个元素交换Swap((php-data[0]), (php-data[php-size - 1]));//然后此时数组中最后一个元素即为堆中最小的元素数组长度-1即代表删除了最后一个元素php-size--;//然后将此时数组中下标为0的元素进行向下调整以使数组满足小根堆的定义AdjustDown(php-data, php-size, 0);
}void AdjustDown(HPDataType* arr, int size, int parent)
{assert(arr);//先求出该父结点的左孩子int child 2 * parent 1;//如果该父结点的孩子结点的在数组中则将该父结点与孩子结点进行比较while (childsize){//上面求的是父节点的左孩子但是父节点要与最小的孩子结点进行比较所以当父结点有右孩子//且右孩子小于左孩子时就将该父节点与右孩子进行比较if (child1sizearr[child 1] arr[child]){child;}//如果该父节点大于其最小的孩子就让这两个结点交换位置if (arr[child] arr[parent]){//该组父子结点交换位置Swap(arr[child], arr[parent]);//然后让孩子结点的位置作为父结点位置parent child;//再次求出新父节点的孩子结点的位置child 2 * parent 1;}else{break;}}}返回堆顶元素就是将小根堆中最小的值返回即将数组下标为0的元素返回。
HPDataType HeapTop(HP* php)
{assert(php);if (!HeapEmpty(php)){return php-data[0];}
}判断堆是否为空和返回堆的大小直接使用size就可以判断。
bool HeapEmpty(HP* php)
{assert(php);if (php-size 0){return true;}else{return false;}
}int HeapSize(HP* php)
{assert(php);return php-size;
}销毁堆就是将动态申请的数组的空间都释放。
void HeapDestroy(HP* php)
{assert(php);free(php-data);php-data NULL;php-size 0;php-capacity 0;
}当我们建立好一个堆然后实现了堆的上述操作后我们就可以使用堆的一些操作来完成数组的升序或降序打印值得注意的是当我们要升序打印时我们需要建立小堆然后打印堆顶的最小元素然后将堆顶元素删除此时剩余元素中最小值会被处理为堆顶。这样我们每次打印的都是堆中最小的元素。当需要降序打印时需要建立大堆这样每次打印出来的元素都是最大值。
void TestHeapSort()
{//升序打印 -- 小堆//降序打印 -- 大堆HP hp;HeapInit(hp);int a[] { 27,15,19,18,28,34,65,49,25,37 };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);
}4、堆排序
当我们实现了一个堆后我们就可以利用堆来写堆排序我们可以使用堆的返回堆顶操作来得到堆中的最大值/最小值。我们先将目标数组中的元素都存入到堆中然后将堆中的堆顶元素即最大值/最小值依次存到目标数组中。但是这样实现的堆排序在使用之前还要先写一个堆数据结构然后实现堆的一系列操作之后才能调用该堆排序函数。并且该堆排序因为在堆中建立了一个新数组所以有O(N)的空间复杂度。
void HeapSort(int* arr, int size)
{//先建立一个堆结构;HP hp;HeapInit(hp);//然后将目标数组arr中的元素都存入堆中for (int i 0; i size; i){HeapPush(hp, arr[i]);}int i 0;//然后将堆中的堆顶元素都出来再存入目标数组中。while (!HeapEmpty(hp)){arr[i] HeapTop(hp);//堆中最大值/最小值存到目标数组后将堆顶元素删除以便找到新的堆顶元素HeapPop(hp);}HeapDestroy(hp);
}上述的堆排序在使用前还需要写出堆的一系列操作真正的堆排序不要借用堆的操作所以不使用上面的方法来写堆排序。我们可以在main函数中建立一个数组然后将数组传入HeapSort()函数中通过HeapSort()函数将该数组排序为升序数组或降序数组。在HeapSort()函数中我们需要先将传进来的目标数组用向上调整或向下调整变为一个堆然后通过将堆中最大的元素或最小的元素放入数组最后一个次大的元素或次小的元素放入数组倒数第二个这样的方式将数组变为升序数组或者降序数组。 此时堆排序中如果要将数组变为降序数组则需要将数组建为小堆。如果要将数组变为升序数组则需要将数组建为大堆。
void HeapSort(int* arr, int size)
{//当要给一个数组进行堆排序时首先我们要先将该数组变为一个堆。//利用向上调整来建堆//时间复杂度为O(N*logN)//int i 0;//for (i 1; i size; i)//{// //从该数组下标为1的元素开始依次进行向上调整依次来将arr数组变为一个堆// AdjustUp(arr, i);//}//利用向下调整来建堆//时间复杂度为O(N)int i 0;for (i (size - 1 - 1) / 2; i 0; --i){AdjustDown(arr, size, i);}//此时的arr已经为一个堆因为此时为小根堆所以堆顶为数组中最小值//此时我们将数组下标为0的元素即最小值与数组最后一个元素交换则数组最后一个元素存的就为最小值//然后我们再将此时下标为0的元素向下调整恢复数组为一个小根堆此时数组的最后一个元素就是最小值//依次循环得到数组的次小值存入数组倒数第二个位置中就这样一直循环直到剩下数组中下标为0的元素此时下标为0的元素为最大值。int end size - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);--end;}
}5、计算堆排序中向上调整建堆和向下调整建堆的时间复杂度
