淄博市建设业协会网站,广州网站设计制作公司,网站的运营维护,佛山百度网络推广文章目录 一、树1、树的结构与概念2、树相关术语 二、二叉树1、概念与结构2、满二叉树3、完全二叉树 三、顺序二叉树存储结构四、实现顺序结构二叉树1、堆的概念与结构2、堆的实现3、堆的排序 一、树
1、树的结构与概念 树是一种非线性的数据结构#xff0c;它是由n#xff… 文章目录 一、树1、树的结构与概念2、树相关术语 二、二叉树1、概念与结构2、满二叉树3、完全二叉树 三、顺序二叉树存储结构四、实现顺序结构二叉树1、堆的概念与结构2、堆的实现3、堆的排序 一、树
1、树的结构与概念 树是一种非线性的数据结构它是由nn0个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根结点没有前驱结点。除根结点外其余结点被分成 M(M0)个互不相交的集合其中每个集合又是一颗结构与树类似的子树。每颗自树的根结点有且只有一个 前驱可以有0个或多个后继。因此树是递归定义的。 树形结构中⼦树之间不能有交集否则就不是树形结构 非树形结构 子树是不相交的除根结点外每个结点有且仅有一个父节点一颗N个结点的树有N - 1条边 2、树相关术语 ⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点 如上图A是B的⽗结点⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 如上图B是A的孩⼦结点结点的度⼀个结点有⼏个孩⼦他的度就是多少⽐如A的度为6F的度为2K的度为0树的度⼀棵树中最⼤的结点的度称为树的度 如上图树的度为 6叶⼦结点/终端结点度为 0 的结点称为叶结点 如上图 B、C、H、I… 等结点为叶结点分⽀结点/⾮终端结点度不为 0 的结点 如上图 D、E、F、G… 等结点为分⽀结点分⽀结点/⾮终端结点度不为 0 的结点 如上图 D、E、F、G… 等结点为分⽀结点结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推树的⾼度或深度树中结点的最⼤层次 如上图树的⾼度为 4结点的祖先从根到该结点所经分⽀上的所有结点如上图 A 是所有结点的祖先路径⼀条从树中任意节点出发沿⽗节点-⼦节点连接达到任意节点的序列⽐如A到Q的路径为A-E-J-QH到Q的路径H-D-A-E-J-Q⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图所有结点都是A的⼦孙森林由 mm0 棵互不相交的树的集合称为森林 二、二叉树
1、概念与结构 树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。 二叉树具备以下特点 1.⼆叉树不存在度⼤于 2 的结点 ⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树 注意对于任意的⼆叉树都是由以下⼏种情况复合⽽成的 2、满二叉树 ⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀个⼆叉树的层数为 K 且结点总数是 2k − 1 则它就是满⼆叉树。 3、完全二叉树 完全⼆叉树是效率很⾼的数据结构完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的有 n 个结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。 二叉树性质 1若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2i−1 个结点2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2h − 13若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 h log 2 ( n 1 ) \log_2 (n1) log2(n1) ( log以2为底 n1 为对数) 三、顺序二叉树存储结构 顺序结构存储就是使⽤数组来存储⼀般使⽤数组只适合表⽰完全⼆叉树因为不是完全⼆叉树会有空间的浪费完全⼆叉树更适合使⽤顺序结构存储。 现实中我们通常把堆⼀种⼆叉树使⽤顺序结构的数组来存储需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事⼀个是数据结构⼀个是操作系统中管理内存的⼀块区域分段。 四、实现顺序结构二叉树 ⼀般堆使⽤顺序结构的数组来存储数据堆是⼀种特殊的⼆叉树具有⼆叉树的特性的同时还具备其他的特性。 1、堆的概念与结构 如果有⼀个关键码的集合K{ k 0 , k 1 , ⋯ , k n − 1 k_0, k_1, \cdots, k_{n-1} k0,k1,⋯,kn−1把它的所有元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中并满⾜ K i K_i Ki K 2 ∗ i 1 K_{2*i1} K2∗i1i 0、1、2… 则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆根结点最⼩的堆叫做最⼩堆或⼩根堆。 堆具有以下性质 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值堆总是⼀棵完全⼆叉树。 顺序二叉树性质 对于具有 n 个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号则对于序号为 i 的结点有 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号⽆双亲结点 若 2i1n 左孩⼦序号 2i1 2i1n 否则⽆左孩⼦ 若 2i2n 右孩⼦序号 2i2 2i2n 否则⽆右孩⼦ 2、堆的实现
堆的底层结构为数组因此定义堆的结构为
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDateType;typedef struct Heap
{HPDateType* arr;int capacity;int size;
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDesTroy(HP* php);//堆尾插入数据
void HPPush(HP* php, HPDateType x);//向上调整
void AdjustUp(HPDateType* arr, int child);//删除堆顶数据
void HPPop(HP* php);//向下调整
void AdjustDown(HPDateType* arr, int parent,int n);//取堆顶数据
HPDateType HPTop(HP* php);//判断堆是否为空
bool HPEmpty(HP* php);堆的函数实现
#includeHeap.h//初始化
void HPInit(HP* php)
{assert(php ! NULL);php-arr NULL;php-capacity php-size 0;
}//销毁
void HPDesTroy(HP* php)
{assert(php ! NULL);free(php-arr);php-arr NULL;php-capacity php-size;
}//交换
void swap(HPDateType* x, HPDateType* y)
{HPDateType tmp *x;*x *y;*y tmp;
}//向上调整
void AdjustUp(HPDateType* arr, int child)
{assert(arr ! NULL);int parent (child - 1) / 2;while (arr[parent] arr[child] child 0){swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}
}//插入数据
void HPPush(HP* php, HPDateType x)
{assert(php ! NULL);//判断空间够不够if (php-capacity php-size){//增容int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDateType* tmp (HPDateType*)realloc(php-arr, newcapacity*sizeof(HPDateType));if (tmp NULL){perror(realloc fail);exit(1);}php-arr tmp;tmp NULL;php-capacity newcapacity;}php-arr[php-size] x;AdjustUp(php-arr, php-size - 1);
}//删除数据
void HPPop(HP* php)
{assert(php ! NULL);assert(php-size 0);swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr, 0,php-size);
}//向下调整
void AdjustDown(HPDateType* arr, int parent,int n)
{assert(arr ! NULL);int child (parent * 2) 1;while (child n){if (child 1 n arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}//取堆顶数据
HPDateType HPTop(HP* php)
{assert(php ! NULL);assert(php-size 0);return php-arr[0];
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php ! NULL);return php-size 0;
}3、堆的排序 运用堆排序时间复杂度大大减小 void HeapSort(int* arr, int n)
{//µint i 0;int parent 0;int child 0;for (i (n - 1) / 2; i 0; i--){parent i;child parent * 2 1;while (child n){if (child 1 n arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){int tmp arr[child];arr[child] arr[parent];arr[parent] tmp;parent child;child parent * 2 1;}else{break;}}}for (i n - 1; i 0; i--){parent 0;child i;int tmp arr[child];arr[child] arr[parent];arr[parent] tmp;child parent * 2 1;while (child i){if (child 1 i arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){tmp arr[child];arr[child] arr[parent];arr[parent] tmp;parent child;child parent * 2 1;}else{break;}}}
}
