怎样设计网站,庄河建网站,绵阳 网站,重庆旅游景点文章目录 树概念相关的基本概念树的表示 二叉树概念特殊二叉树性质 堆二叉树的顺序结构堆的概念 堆的实现初始化数组初始化为堆向上调整向下调整插入删除打印、摧毁、判空、获取堆顶数据验证 堆的应用堆排序TopK问题 树
概念
树是一种常见的非线性的数据结构#xff0c;它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
相关的基本概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图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棵互不相交的树的集合称为森林 一些概念类似于祖辈关系 起始结点称为根节点也就是图中的A 树可以分为很多种子树子树部分可以也有自己的根节点 树是递归定义的。 树的表示
对于树来说结构比较复杂存储起来比较困难既要保存数据又要保证节点与节点之间的联系在实际中有这几种表示方法双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
这里介绍其中的一种孩子兄弟表示法
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};二叉树
概念
二叉树是一种特殊的树结构每个节点最多可以有两个子节点。且这两个节点分别称之为左子树和右子树左孩子和右孩子节点也可以没有子节点和只有一个子节点 二叉树是有左右之分的是一种有序树
特殊情况
特殊二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 .
性质
1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n2 n01.
看下面一道例题
堆
二叉树的顺序结构
一般的二叉树是不适合用数组的存储结构来表示的只有完全二叉树这种连续性的树结构才适合在现实中堆就是用这种结构来存储的。 注意这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
堆的概念
堆其实就是一颗完全二叉树除最后一层的叶节点其他层的节点全是满的。堆又分为大堆和小堆。在小堆中对于任意节点i父节点的值小于等于子节点的值在大堆中对于任意节点i父节点的值大于等于子节点的值。实际中堆还是数组只是存储的逻辑顺序是完全二叉树的从上到下的顺序。 堆的实现
这是堆结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* a; //存储的数组int size; //存储的大小int capacity; //数组的大小
}HP;初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}将数组初始化为空存储量和容量都设为0即可
数组初始化为堆
有时我们会将一个数组变成堆的存储结构
void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);//先将堆的数组创建空间php-a (HPDataType*)malloc(sizeof(HPDataType)*n);if (php-a NULL){perror(HeapInit Fail);exit(-1);}php-capacity php-size n;//复制过去memcpy(php-a, a,sizeof(HPDataType)* n);//建堆for (int i 1; i n; i){AdjustUp(php-a, i);//向上调整}
}
向上调整是孩子可能会变化为父亲所以从第1个下标开始而不是第0个
向上调整
这里先说一下父亲与孩子下标的关系
由于堆的概念当我们插入一个数据进去或者想将数组变化为数组时需要对这个存储的数据进行调整而我们调整的逻辑就是根据堆的结构去调整的。
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp(HPDataType* a, int child)
{assert(a);//父亲节点HPDataType parent (child - 1) / 2;while (child 0){//孩子节点的值比父亲节点的值小就交换if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}利用循环来进行调整这种调整前提是前面的结构是堆时间复杂度为OlogN
向下调整
有向上调整自然有向下调整对于堆顶的值的插入就需要进行向下调整。
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);HPDataType child parent * 2 1;while (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 child * 2 1;}else{break;}}}这里以左孩子为主当右孩子比左孩子大时就将右孩子与父亲节点进行比较
插入
我们会在数组的size的后面进行插入也就是堆底
void HeapPush(HP* php, HPDataType x)
{assert(php);//满扩容if (php-capacity php-size){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(Realloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}//插入php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size - 1);
}删除
我们删除的是堆顶的数据如果按常规想法删除堆顶数据然后进行移动可不可行呢 显然是不行的解决方法是先将最后一个数据与堆顶数据交换然后对交换后的堆顶值进行向下调整。因为调换删除后除了堆顶下面的数据都满足堆的条件。
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));//堆顶与删除数据交换Swap(php-a[0], php-a[php-size - 1]);//删除php-size--;//向下调整AdjustDown(php-a, php-size, 0);}打印、摧毁、判空、获取堆顶数据
//打印
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}
//摧毁
void HeapDestory(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}验证
接下来就来进行验证 先验证数组初始化为堆
int main()
{int a[] { 65,100,70,32,50,60 };HP heap;HeapInitArray(heap, a, 6);HeapPrint(heap);return 0
} 接着依次验证插入删除和获取堆顶数据
int main()
{HeapInit(heap);for (int i 0; i 6; i){HeapPush(heap, a[i]);}HeapPrint(heap);HeapPop(heap);HeapPrint(heap);printf(%d, HeapTop(heap));HeapDestory(heap);return 0;
}堆的应用
接着说堆比较常用的两个应用堆排序和TopK问题。
堆排序
第一种方法我们的思路是先建立一个堆结构然后利用堆的删除思想进行排序。
//小堆
void HeapSort(int* a, int n)
{//建堆HP hp;HeapInit(hp);for (int i 0; i n; i){HeapPush(hp, a[i]);}//利用堆删除原理来进行排序int i 0;while (!HeapEmpty(hp)){a[i] HeapTop(hp);HeapPop(hp);}HeapDestory(hp);
}
int main()
{int a[] { 2,3,5,7,4,6,8 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}这种方法小堆对应的是升序利用堆顶是最小的然后对它取值后删除的原理进行排序时间复杂度为O(N* logN * N);
还有一种方法先对数组进行建堆将堆顶与最后一个数据进行替换以升序建大堆为例最大的值与堆底替换后那么最大的值就放在了最后的空间里了再对数组长度做限制那就可以完成排序了
//小堆
void HeapSort(int* a, int n)
{//升序大堆 降序小堆for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] { 2,3,5,7,4,6,8 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}时间复杂度O(N)N*logN 显然下面方法排序的更快。
TopK问题
即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopk(const char* filename, int k)
{//建堆FILE* fout fopen(filename, r);if (fout NULL){perror(fout fail);exit(-1);}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(minheap fail);exit(-1);}//数据输入for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}//建堆/*for (int i 1; i k; i){AdjustUp(minheap, i);}*/for (int i (k - 1-1) / 2; i 0; i--){AdjustDown(minheap, k, i);}//交换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minheap[0]){minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d\n, minheap[i]);}fclose(fout);
}//数据创建
void CreateNDate()
{int n 1000000;srand(time(NULL));const char* file data.txt;FILE* bin fopen(file, w);if (bin NULL){perror(FILE Fail);exit(-1);}for (int i 0; i n; i){int x (rand() i) % 1000000;fprintf(bin, %d\n, x);}fclose(bin);}int main()
{//CreateNDate();PrintTopk(data.txt, 5);return 0;
}先利用随机数创建一个数据文件然后先将k个数据存储进数组中接着建堆最后将n-k个数据与堆顶进行比较大于堆顶就进堆 这里有两种建堆方法一种是向上调整的建堆另一种是向下调整的建堆
向上调整的建堆
向下调整的建堆 时间复杂度T(N)N; 从简单的角度来看向上调整时堆底的最底层数据几乎是堆的一半都需要向上调整而向下调整堆顶只有一个相比之下向下调整肯定所用时间比较少。
