免费网站建设免费咨询,建网站找那家企业好,如何管理网站,罗湖微信网站制作文章目录 一、树 1.1 树的概念与结构 1.2 树的相关术语 1.3 树的表示 二、二叉树 2.1 二叉树的概念与结构 2.2特殊的二叉树 满二叉树 完全二叉树 2.3 二叉树的存储结构 三、实现顺序结构二叉树 3.1 堆的概念与结构 3.2 堆的实现 Heap.h Heap.c 默认初始化堆 堆的销毁 堆的插入 … 文章目录 一、树 1.1 树的概念与结构 1.2 树的相关术语 1.3 树的表示 二、二叉树 2.1 二叉树的概念与结构 2.2特殊的二叉树 满二叉树 完全二叉树 2.3 二叉树的存储结构 三、实现顺序结构二叉树 3.1 堆的概念与结构 3.2 堆的实现 Heap.h Heap.c 默认初始化堆 堆的销毁 堆的插入 删除堆顶数据 一、树
1.1 树的概念与结构
树是⼀种⾮线性的数据结构它是由 nn0 个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上⽽叶朝下的。 有⼀个特殊的结点称为根结点根结点没有前驱结点。 除根结点外其余结点被分成 M(M0) 个互不相交的集合 T1、T2、……、Tm 其中每⼀个集合 Ti(1 i m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有 0 个或多个后继。因此树是递归定义的。 树形结构中⼦树之间不能有交集否则就不是树形结构 ⼦树是不相交的如果存在相交就是图了图以后得课程会有讲解 除了根结点外每个结点有且仅有⼀个⽗结点 ⼀棵N个结点的树有N-1条边 1.2 树的相关术语 ⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点 如上图A是B的⽗结点 ⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 如上图B是A的孩⼦结点 结点的度⼀个结点有⼏个孩⼦他的度就是多少⽐如A的度为6F的度为2K的度为0 树的度⼀棵树中最⼤的结点的度称为树的度 如上图树的度为 6 叶⼦结点/终端结点度为 0 的结点称为叶结点 如上图 B、C、H、I... 等结点为叶结点 分⽀结点/⾮终端结点度不为 0 的结点 如上图 D、E、F、G... 等结点为分⽀结点 兄弟结点具有相同⽗结点的结点互称为兄弟结点(亲兄弟) 如上图 B、C 是兄弟结点结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推 树的⾼度或深度树中结点的最⼤层次 如上图树的⾼度为 4 结点的祖先从根到该结点所经分⽀上的所有结点如上图 A 是所有结点的祖先 路径⼀条从树中任意节点出发沿⽗节点-⼦节点连接达到任意节点的序列⽐如A到Q的路径为A-E-J-QH到Q的路径H-D-A-E-J-Q ⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图所有结点都是A的⼦孙 森林由 mm0 棵互不相交的树的集合称为森林 1.3 树的表示 孩⼦兄弟表⽰法
struct TreeNode{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域}; 二、二叉树
2.1 二叉树的概念与结构 在树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。 从上图可以看出⼆叉树具备以下特点 ⼆叉树不存在度⼤于 2 的结点 ⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树 注意对于任意的⼆叉树都是由以下⼏种情况复合⽽成的 2.2特殊的二叉树
满二叉树 ⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀个⼆叉树的层数为 K 且结点总数是 2 k − 1 则它就是满⼆叉树。 完全二叉树 完全⼆叉树是效率很⾼的数据结构完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的有 n 个结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
假设二叉树层次为 k 除了第 k 层外每层结点的个数达到最大结点数第 k 层结点个数不一定达到最大结点数 ⼆叉树性质 根据满⼆叉树的特点可知 1若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2 i −1 个结点 2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2 h − 1 3若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 ( log 以2为底 n1 为对数) 2.3 二叉树的存储结构 ⼆叉树⼀般可以使⽤两种结构存储⼀种顺序结构⼀种链式结构。 下面我们先来使用顺序结构实现二叉树。 顺序结构存储就是使⽤数组来存储⼀般使⽤数组只适合表⽰完全⼆叉树因为不是完全⼆叉树会有空间的浪费完全⼆叉树更适合使⽤顺序结构存储。 现实中我们通常把堆⼀种⼆叉树使⽤顺序结构的数组来存储需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事⼀个是数据结构⼀个是操作系统中管理内存的⼀块区域分段。 三、实现顺序结构二叉树 ⼀般堆使用顺序结构的数组来存储数据堆是⼀种特殊的⼆叉树具有⼆叉树的特性的同时还具备其他的特性。 3.1 堆的概念与结构 如果有⼀个关键码的集合 把它的所有元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中并满⾜ 且 i 0、1 、 2... 则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆根结点最⼩的堆叫做最⼩堆或⼩根堆。 小根堆 大根堆 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值 堆总是⼀棵完全⼆叉树。 ⼆叉树性质 对于具有 n 个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号则对于序号为 i 的结点有 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号⽆双亲结点 若 2i1n 左孩⼦序号 2i1 2i1n 否则⽆左孩⼦ 若 2i2n 右孩⼦序号 2i2 2i2n 否则⽆右孩⼦ 3.2 堆的实现
以小根堆为例子
Heap.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//定义堆的结构---数组typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;//有效的数据个数int capacity;//空间大小
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestroy(HP* php);//堆的插入
void HPPush(HP* php, HPDataType x);//出堆删除堆顶数据
void HPPop(HP* php);//返回堆顶数据
HPDataType HPTop(HP* php);// 判空
bool HPEmpty(HP* php); Heap.c
默认初始化堆
void HPInit(HP* php)
{assert(php);php-arr NULL;php-capacity php-size 0;
} 堆的销毁
void HPDestroy(HP* php)
{assert(php);if (php-arr){free(php-arr);php-arr NULL;php-capacity php-size - 0;}
} 堆的插入 如果要在下一个数据 “50” 到 arr【6】的位置上就不满足小堆的特性
此时我们就要用到堆的向上调整算法 向上调整算法 • 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后 • 插⼊之后如果堆的性质遭到破坏将新插⼊结点顺着其双双亲往上调整到合适位置即可 void swap(int* x, int* y)
{int z *x;*x *y;*y z;
}void Adjustup(HPDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0){if (arr[child] arr[parent]) //如果插入的数据大小小于他的父节点{swap(arr[child], arr[parent]); //交换child parent; //交换后的孩结点来到原来他的父节点的位置 parent 2 * child - 1;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php-size php-capacity){//扩容int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-arr, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail!);exit(1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;php-size;Adjustup(php-arr, php-size - 1);
} 删除堆顶数据 如果直接删除 arr【0】就会改变原先堆的结构所以我么可以先先将头和尾的数据交换在删除 arr【5】但是又有问题出现。交换删除后的数据有可能不满足小堆的特性此时就要用到:堆的向下调整算法 向下调整算法 • 将堆顶元素与堆中最后⼀个元素进⾏交换 • 删除堆中最后⼀个元素 • 将堆顶元素向下调整到满⾜堆特性为⽌ void AdjustDown(HPDataType* 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(HP* php)
{assert(php php-size);//arr[0] arr[size-1]swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr, 0, php-size);} test.c
最后测试一下代码的实现
#includeHeap.hvoid Hptest()
{HP hp;HPInit(hp);int arr[] { 17,25,60,54,30,70 };for (int i 0; i 6; i){HPPush(hp, arr[i]);}HPPop(hp);
}int main()
{Hptest();return 0;
} 未完待续~
