在线做头像网站有哪些,个人网站备案简介,网站建设专业工资,网站建设与管理2018文章目录 堆一. 树概念及结构1. 树的概念2. 树的相关概念3. 树的表示4. 树在实际中的运用#xff08;表示文件系统的目录树结构#xff09; 二. 二叉树概念及结构1. 概念2. 特殊的二叉树3. 二叉树的性质4. 二叉树的存储结构 三. 二叉树的顺序结构及实现1. 二叉树的顺序结构2.… 文章目录 堆一. 树概念及结构1. 树的概念2. 树的相关概念3. 树的表示4. 树在实际中的运用表示文件系统的目录树结构 二. 二叉树概念及结构1. 概念2. 特殊的二叉树3. 二叉树的性质4. 二叉树的存储结构 三. 二叉树的顺序结构及实现1. 二叉树的顺序结构2. 堆的概念及结构3. 建堆时间复杂度4. 堆的实现4.1 结构体部分4.2 初始化 HPInit4.3 销毁 HPDestroy4.4 交换 Swap4.5 堆的插入 HPPush4.6 堆底元素向上调整 AdjustUp4.7 堆的删除 HPPop4.8 堆顶元素向下调整算法 AdjustDown4.9 返回堆顶元素 HPTop4.10 判空 HPEmpty4.11 堆排序 HeapSort 5. 堆的应用5.1 堆排序5.2 TOP-K问题 四. 参考代码Heap.hHeap.ctest.c 堆
一. 树概念及结构
1. 树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合 T 1 、 T 2 、 … … 、 T m T_1、T_2、……、T_m T1、T2、……、Tm其中每一个集合 T i ( 1 i m ) T_i(1 im) Ti(1im)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有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 Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};4. 树在实际中的运用表示文件系统的目录树结构 二. 二叉树概念及结构
1. 概念
一棵二叉树是结点的一个有限集合该集合:
或者为空由一个根结点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出
二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的
2. 特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 2 k − 1 2^k -1 2k−1 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3. 二叉树的性质
若规定根结点的层数为1则一棵非空二叉树的第 i i i层上最多有 2 ( i − 1 ) 2^{(i-1)} 2(i−1)个结点.若规定根结点的层数为1则深度为 h h h的二叉树的最大结点数是 2 h − 1 2^h-1 2h−1.对任何一棵二叉树, 如果度为0其叶结点个数为 n 0 n_0 n0, 度为2的分支结点个数为 n 2 n_2 n2,则有 n 0 n 2 1 n_0n_21 n0n21
/*
* 假设二叉树有N个结点
* 从总结点数角度考虑N n0 n1 n2 ①
*
* 从边的角度考虑N个结点的任意二叉树总共有N-1条边
* 因为二叉树中每个结点都有双亲根结点没有双亲每个节点向上与其双亲之间存在一条边
* 因此N个结点的二叉树总共有N-1条边
* 因为度为0的结点没有孩子故度为0的结点不产生边; 度为1的结点只有一个孩子故每个度
* 为1的结点产生一条边; 度为2的结点有2个孩子故每个度为2的结点产生两条边所以总边
* 为n12*n2
* 故从边的角度考虑N-1 n1 2*n2 ②
* 结合① 和 ②得n0 n1 n2 n1 2*n2 - 1
* 即n0 n2 1
*/若规定根结点的层数为1具有n个结点的满二叉树的深度 h l o g 2 ( n 1 ) h log_2(n 1) hlog2(n1). (ps h l o g 2 ( n 1 ) h log_2(n 1) hlog2(n1)是log以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有 若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199下列数据结构中不适合采用顺序存储结构的是 A 非完全二叉树 B 堆 C 队列 D 栈在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2一棵完全二叉树的结点数位为531个那么这棵树的高度为 A 11 B 10 C 8 D 12一个具有767个结点的完全二叉树其叶子结点个数为 A 383 B 384 C 385 D 386 答案 1.B 2.A 3.A 4.B 5.B 4. 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面学到高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* parent; // 指向当前结点的双亲struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}三. 二叉树的顺序结构及实现
1. 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
2. 堆的概念及结构
如果有一个关键码的集合K { k 0 k_0 k0 k 1 k_1 k1 k 2 k_2 k2… k n − 1 k_{n-1} kn−1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 k i k 2 i 1 k_ik_{2i 1} kik2i1 且 k i k 2 i 2 k_ik_{2i 2} kik2i2 ( k i k 2 i 1 k_ik_{2i 1} kik2i1 且 k i k 2 i 2 k_ik_{2i 2} kik2i2 ) i 012…则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树 3. 建堆时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果)
因此建堆的时间复杂度为O(N)。 选择题 1.下列关键字序列为堆的是 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32 2.已知小根堆为8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是。 A 1 B 2 C 3 D 4 3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 A(11 5 7 2 3 17) B(11 5 7 2 17 3) C(17 11 7 2 3 5) D(17 11 7 5 3 2) E(17 7 11 3 5 2) F(17 7 11 3 2 5) 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是 A[3257468] B[2357468] C[2345786] D[2345678] 选择题答案 ACCC 4. 堆的实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);4.1 结构体部分
堆的实现我们按照动态顺序表为物理结构即顺序存储结构以完全二叉树为逻辑结构。
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;4.2 初始化 HPInit
下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根结点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子结点的子树开始调整一直调整到根结点的树就可以调整成堆。
int a[] {1,5,3,8,7,6};void HPInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}4.3 销毁 HPDestroy
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}4.4 交换 Swap
这里我们实现一个交换函数方便我们后续对堆的元素进行调整。
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}4.5 堆的插入 HPPush
先插入一个10到数组的尾上再进行向上调整算法直到满足堆。
void HPPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* newa (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (newa NULL){perror(realloc failed!\n);exit(1);}php-a newa;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}现在我们只是把一个元素插入到了数组之中接下来我们要对该元素进行向上调整。
4.6 堆底元素向上调整 AdjustUp void AdjustUp(HPDataType* a, int child)//向上调整
{int parent (child - 1) / 2;//小堆//while (parent 0)while(child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);//交换child parent;parent (child - 1) / 2;}else{break;}}
}4.7 堆的删除 HPPop
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。
//时间复杂度O(logN)
void HPPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}现在我们也同样只是把堆顶元素根位置元素从数组中删除接下来的向下调整算法才是堆的核心算法也是堆排序的核心算法。
4.8 堆顶元素向下调整算法 AdjustDown
现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37};void AdjustDown(HPDataType* a,int n, int parent)//堆顶元素向下调整
{//假设左孩子小int child parent * 2 1;while (child n)//如果child n说明孩子不存在调整到叶子了{//找出小的那个孩子if (child 1 n a[child 1] a[child])//防止越界{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}4.9 返回堆顶元素 HPTop
HPDataType HPTop(HP* php)
{assert(php);return php-a[0];
}4.10 判空 HPEmpty
_Bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}4.11 堆排序 HeapSort
void HeapSort(HPDataType* a, int n)
{//建堆//降序 -- 建小堆//升序 -- 建大堆//for (int i 1; i n; i)//{// AdjustUp(a, i);//}//建堆//从最后一个父亲节点开始依次向上执行向下调整算法for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);//将排列好的元素放在最后面AdjustDown(a, end, 0);--end;}
}5. 堆的应用
5.1 堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
建堆 升序建大堆 降序建小堆利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
5.2 TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(int* a, int n, int k)
{// 1. 建堆--用a中前k个元素建堆// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int* kminheap (int*)malloc(sizeof(int) * k);if (kminheap NULL){perror(malloc fail);return;}// 读取数组中前k个数for (int i 0; i k; i){kminheap[i] a[i];}// 建K个数的小堆for (int i (k-1-1)/2; i0 ; i--){AdjustDown(kminheap, k, i);}// 读取剩下的N-K个数int x k;while (x n){if (x kminheap[0]){kminheap[0] x;AdjustDown(kminheap, k, 0);}}printf(最大前%d个数, k);for (int i 0; i k; i){printf(%d , kminheap[i]);}printf(\n);
}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int)*n);srand(time(0));//造数据for (size_t i 0; i n; i){a[i] rand() % 1000000;}//人为创造最大的大数a[5] 1000000 1;a[1231] 1000000 2;a[531] 1000000 3;a[5121] 1000000 4;a[115] 1000000 5;a[2335] 1000000 6;a[9999] 1000000 7;a[76] 1000000 8;a[423] 1000000 9;a[3144] 1000000 10;PrintTopK(a, n, 10);
}四. 参考代码
Heap.h
#pragma once#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;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);//堆底元素向上调整
void AdjustUp(HPDataType* a, int child);//堆顶元素向下调整
void AdjustDown(HPDataType* a, int n, int parent);//交换
void Swap(HPDataType* p1, HPDataType* p2);Heap.c
#include Heap.hvoid HPInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)//向上调整
{int parent (child - 1) / 2;//小堆//while (parent 0)while(child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);//交换child parent;parent (child - 1) / 2;}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* newa (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (newa NULL){perror(realloc failed!\n);exit(1);}php-a newa;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}void AdjustDown(HPDataType* a,int n, int parent)//堆顶元素向下调整
{//假设左孩子小int child parent * 2 1;while (child n)//如果child n说明孩子不存在调整到叶子了{//找出小的那个孩子if (child 1 n a[child 1] a[child])//防止越界{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//时间复杂度O(logN)
void HPPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}HPDataType HPTop(HP* php)
{assert(php);return php-a[0];
}_Bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}test.c
#include Heap.h
#include vld.hvoid TestHeap01()
{int a[10] { 2,3,4,1,6,5,9,8,7,0 };HP hp;HPInit(hp);size_t sz sizeof(a) / sizeof(int);for (size_t i 0; i sz; i){HPPush(hp, a[i]);}int i 0;while (!HPEmpty(hp)){//printf(%d , HPTop(hp));a[i] HPTop(hp);HPPop(hp);}HPDestroy(hp);
}void HeapSort(HPDataType* a, int n)
{//建堆//降序 -- 建小堆//升序 -- 建大堆//for (int i 1; i n; i)//{// AdjustUp(a, i);//}//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}//排序
//void HeapSort(HPDataType* a, int n);void TestHeap02()
{int a[10] { 2,3,4,1,6,5,9,8,7,0 };size_t sz sizeof(a) / sizeof(int);HeapSort(a, sz);for (int i 0; i sz; i){printf(%d , a[i]);}printf(\n);}int main()
{//TestHeap01();TestHeap02();return 0;
}
