网站的pr,微信公众平台开发模式,福建有没有网站做一件代发,沈阳做网站哪家好文章目录 目录1. 树的概念及结构1.1 树的相关概念1.2 树的表示1.3 树在实际中的运用#xff08;表示文件系统的目录树结构#xff09; 2. 二叉树的概念及结构2.1 概念2.2 特殊的二叉树2.3 二叉树的存储结构 3. 二叉树的顺序结构及实现3.1 二叉树的顺序结构3.2 堆的概念及结构… 文章目录 目录1. 树的概念及结构1.1 树的相关概念1.2 树的表示1.3 树在实际中的运用表示文件系统的目录树结构 2. 二叉树的概念及结构2.1 概念2.2 特殊的二叉树2.3 二叉树的存储结构 3. 二叉树的顺序结构及实现3.1 二叉树的顺序结构3.2 堆的概念及结构3.3 堆的实现3.4 堆的应用3.4.1 堆排序3.4.2 TOP-K问题 目录
树的概念及结构二叉树的概念及结构二叉树的顺序结构及实现二叉树链式结构的实现
1. 树的概念及结构
1.1 树的相关概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6
叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点没有孩子的节点
非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点
双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点
孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点
兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点亲兄弟
树的度一棵树中最大的节点的度称为树的度 如上图树的度为6
节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推
注数组的下标从零开始是因为要和指针更好的匹配a[i] *(a i)而在这里我们更习惯把根定义为第一层当然定义成第零层也是可以的
树的高度或深度树中节点的最大层次 如上图树的高度为4
堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点
节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先
子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙
森林由mm0棵互不相交的树的集合称为森林并查集
注 现在我们看到树就要把它进行拆分成根和n棵子树n0树是按照递归定义的也就是说子树也要按照这个方式进行拆分。 也就是说树是不能有环的有环的就称为图。
通过以上学习我们总结一下树的概念树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根节点没有前驱结点。除根节点外其余结点被分成 M(M0) 个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。因此树是递归定义的。
1.2 树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存结点和结点之间的关系。
//树的度是N#define N 6struct TreeNode
{int val;struct TreeNode* subA[N];
};但是这样定义太浪费空间了因为并不是每个节点的度都达到了N。
因此我们可以借助顺序表来解决这个问题
struct TreeNode
{int val;//顺序表struct TreeNode** subA;int size;int capacity;
};但这种表示也不是最常见的接下来我们介绍一种新的定义方式
//左孩子 右兄弟
struct TreeNode
{int val;struct TreeNode* leftChild;struct TreeNode* nextBrother;
};第一个指针永远指向从左往右数的第一个孩子第二个指针指向它自己右边的亲兄弟。
那么一个父亲如何找到他所有的孩子呢
其实还有一种表示方式这里我们先了解一下就可以 用数组存储数据数组的每个元素都是一个结构体每个结构体包含节点的值和父亲所在的下标这种表示法可以用来表示森林。
它的物理结构数组内存中如何存储
逻辑结构森林想象出来的
1.3 树在实际中的运用表示文件系统的目录树结构
数据结构分为表示形和存储形树这种数据结构就属于表示形主要是用来表示某种结构。 在Windows系统中也是一样的比如C盘作为根里面包含了很多文件夹每个文件夹中又包含了很多文件夹它们的底层就是通过树这种数据结构来实现的。
2. 二叉树的概念及结构
2.1 概念
一棵二叉树是结点的一个有限集合该集合:
或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出
二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
注 对于任意的二叉树都是由以下几种情况复合而成的 二叉树单纯存储数据是没啥价值不如顺序表/链表那我们为什么要学二叉树呢 但是它也存在不足在极端情况下可能会变成这样
因此我们后面还要学AVL树和红黑树同时还会有多叉树M阶B树多用于数据库的引擎
2.2 特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树也就是说如果一个二叉树的层数为K且结点总数是 2的k次方 - 1 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树要注意的是满二叉树是一种特殊的完全二叉树。
简单来说 满二叉树就是前 n - 1 层都是满度为2最后一层是叶子结点完全二叉树就是前 n - 1 层都是满最后一层不一定满但要求从左到右的节点是连续的。
2.3 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面我们学到高阶数据结构如红黑树等会用到三叉链。
3. 二叉树的顺序结构及实现
3.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
3.2 堆的概念及结构 3.3 堆的实现
我们先以小堆为例大堆就是 ‘’ 改成 ‘’
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;堆的插入
void Swap(HPDataType* px, HPDataType* py)
{HPDataType* tmp *px;*px *py;*py tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)//这样写是不对的parent永远都是 0 的while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){size_t newCapacity 0 php-capacity ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (NULL tmp){perror(realloc fail);return;}php-a tmp;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){//假设法选出左右孩子中小的那个孩子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;}}
}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);
}完整代码
//Heap.h#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.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);HPDataType HPTop(HP* php);//删除堆顶的数据
void HPPop(HP* php);bool HPEmpty(HP* php);//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-capacity 0;php-size 0;
}void Swap(HPDataType* px, HPDataType* py)
{HPDataType* tmp *px;*px *py;*py tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)//这样写是不对的parent永远都是 0 的while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}//时间复杂度logN
void HPPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){size_t newCapacity 0 php-capacity ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (NULL tmp){perror(realloc fail);return;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}HPDataType HPTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}void AdjustDown(HPDataType* a, int n, int parent)
{int 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 parent * 2 1;}else{break;}}
}//时间复杂度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);
}bool HPEmpty(HP* php)
{assert(php);return 0 php-size;
}//Test.c#include Heap.hint main()
{//如何把以下数组变成一个堆//int a[] { 50, 100, 70, 65, 60, 32 };int a[] { 60, 70, 65, 50, 32, 100 };HP hp;HPInit(hp);for (int i 0; i sizeof(a) / sizeof(int); i){HPPush(hp, a[i]);}//printf(%d\n, HPTop(hp));//HPPop(hp);//printf(%d\n, HPTop(hp));while (!HPEmpty(hp)){printf(%d\n, HPTop(hp));HPPop(hp);}HPDestroy(hp);return 0;
}堆插入和删除的时间复杂度 如果一开始就给了一个数组如何给它初始化成堆呢
模拟插入向上调整建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (NULL php-a){perror(malloc fail);return;}memcpy(php-a, a, sizeof(HPDataType) * n);php-capacity php-size n;//向上调整建堆 O(N*logN)for (int i 1; i php-size; i){AdjustUp(php-a, i);}
}时间复杂度
总结 节点数量越多的时候调整次数也越多
向下调整建堆
向下调整建堆的前提是它的左右子树都已经是大/小堆了所有不能从第一个节点开始向下调整而是从最后一个节点开始向下调整但是最后一层是叶子节点不需要调整就已经是堆了所有就从倒数第一个非叶子节点开始向下调整。
void HPInitArray(HP* php, HPDataType* a, int n)
{assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (NULL php-a){perror(malloc fail);return;}memcpy(php-a, a, sizeof(HPDataType) * n);php-capacity php-size n;//向下调整建堆 O(N)for (int i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, php-size, i);}
}时间复杂度
总结 节点数量多的时候调整次数少 因此直接给一个数组让它建堆比一个一个插入向上调整建堆效率要高。
int main()
{//如何把以下数组变成一个堆//int a[] { 50, 100, 70, 65, 60, 32 };int a[] { 60, 70, 65, 50, 32, 100 };HP hp;HPInitArray(hp, a, sizeof(a) / sizeof(int));while (!HPEmpty(hp)){printf(%d\n, HPTop(hp));HPPop(hp);}HPDestroy(hp);return 0;
}3.4 堆的应用
3.4.1 堆排序
根据我们上面所讲的我们可以很容易想到这种写法
void HeapSort(int* a, int n)
{HP hp;HPInitArray(hp, a, n);int i 0;while (!HPEmpty(hp)){a[i] HPTop(hp);HPPop(hp);}HPDestroy(hp);
}int main()
{int a[] { 60, 70, 65, 50, 32, 100 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}但是这样写有两个问题
需要堆的数据结构空间复杂度 O(N)
可以这样改进
void AdjustDown(HPDataType* a, int n, int parent)
{int 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 parent * 2 1;}else{break;}}
}//升序建大堆还是小堆呢大堆
//O(N * logN)
void HeapSort(int* a, int n)
{//a数组直接建堆 O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}//O(N * logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] { 3, 6, 1, 5, 8, 9, 2, 7, 4, 0 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}之前在写堆的代码时可能会存在这样的疑问为什么向下调整函数的参数不传堆的结构体指针而是只传数组的地址进去呢
这里就体现出来了因为这个函数在堆排序的时候还需要用到如果传了堆的结构体指针那这里就不好复用了。这个函数不仅仅用来服务堆这个数据结构还需要服务于堆排序
3.4.2 TOP-K问题
100亿个数据找出最大的前10个N个数据里面找最大的前K个N远大于K
注 如果N和K差不多大可以直接排序解决
最容易想到的方法就是把这100亿个数据建一个大堆每次找出最大的然后将它删掉再找次大的一直循环10次。
但是这种方法存在问题
时间复杂度N K * logN最主要的问题是空间复杂度堆底层就是个数组它开不出这么大的一个数组内存空间不够
因此我们就要换一种方法
void CreateNDate()
{//造数据int n 100000;srand((unsigned int)time(0));const char* file data.txt;FILE* fin fopen(file, w);if (NULL fin){perror(fopen error);return;}for (int i 0; i n; i){//随机数系统规定只有三万多个//i 是为了让数据的随机性更大一点//%1000000 是为了让数据在1000000以内这样我们可以手动让几个数据大于1000000以此来验证我们程序的正确性int x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}void topk()
{printf(请输入k:);int k 0;scanf(%d, k);const char* file data.txt;FILE* fout fopen(file, r);if (NULL fout){perror(fopen error);return;}int* minheap (int*)malloc(sizeof(int) * k);if (NULL minheap){perror(malloc error);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}//建k个数据的小堆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 , minheap[i]);}fclose(fout);free(minheap);minheap NULL;
}int main()
{CreateNDate();topk();return 0;
}
