网站不备案有什么后果,家庭装修设计软件哪个好用,seo公司是做什么的,网站建立的步骤是( )目录
树概念及结构
1.1树的概念
1.2树的表示
编辑2.二叉树概念及结构
2.1概念
2.2数据结构中的二叉树#xff1a;编辑
2.3特殊的二叉树#xff1a;
编辑
2.4 二叉树的存储结构
2.4.1 顺序存储#xff1a;
2.4.2 链式存储#xff1a;
二叉树的实现及大小堆…目录
树概念及结构
1.1树的概念
1.2树的表示
编辑2.二叉树概念及结构
2.1概念
2.2数据结构中的二叉树编辑
2.3特殊的二叉树
编辑
2.4 二叉树的存储结构
2.4.1 顺序存储
2.4.2 链式存储
二叉树的实现及大小堆排列
1功能展示
2 定义基本结构
3 初始化
4打印
5销毁
6插入
7向上调整
8交换两数组元素之间的值
9删除
10向下调整
11取堆顶的元素
12 判断二叉树是否为空
13计算该二叉树元素个数
3堆排列
1建堆
建堆方式1 时间复杂度O(N*log(N))
建堆方式2 时间复杂度O(N)
2排列数组 O(N * log(N))
成品展示
Head.h
Head.c
Test.c 树概念及结构
1.1树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集 合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以 有0个或多个后继 因此树是递归定义的。 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点树的度一棵树中最大的节点的度称为树的度 如上图树的度为6节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次 如上图树的高度为4节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙森林由mm0棵互不相交的多颗树的集合称为森林数据结构中的学习并查集本质就是一个森林 1.2树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式 如双亲表示法孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};2.二叉树概念及结构
2.1概念
一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子 树和右子树的二叉树组成。 二叉树的特点
每个结点最多有两棵子树即二叉树不存在度大于2的结点。二叉树的子树有左右之分其子树的次序不能颠倒。
2.2数据结构中的二叉树
2.3特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉 树。也就是说如果一个二叉树的层数为K且结点总数是(2^k) -1 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对 于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉 树 2.4 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 二叉树的性质
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h- 1.对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0n2 1若规定根节点的层数为1具有n个结点的满二叉树的深度hLogN
2.4.1 顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树 会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲 解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
2.4.2 链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面课程学到高阶数据结构如红黑树等会用到三叉链。
二叉树的实现及大小堆排列
本文将以写代码思路进行讲述故中间会出现代码的优化以便梳理思路渐入佳境
本文分成三个文件
Head.h//函数的声明
Head.c//函数的创建
Test.c //用于测试文件1功能展示 //用数组的方式来表示二叉树基本结构typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;//初始化void HeapInit(HP* php);//交换两数组元素之间的值void Swap(HPDataType* p1,HPDataType* p2);//打印void HeapPrint(HP* php);//销毁void HeapDestroy(HP* php);//插入void HeapPush(HP* php,HPDataType x);//向下调整void AdjustDown(HPDataType* a, int size, int paarent);//向下调整void AdjustUp(HPDataType x, int child);//删除void HeapPop(HP* php);//取堆顶的元素HPDataType HeapTop(HP* php);//判断是否为空bool HeapEmpty(HP* php);//计算该二叉树元素个数int HeapSize(HP* php);2 定义基本结构 使用数组实现二叉树相较于链表有以下优势1. 内存连续性数组在内存中是连续存储的而链表中的节点可以分布在内存的任意位置。在某些场景下数组的内存连续性可以提高访问效率尤其对于计算机的缓存机制来说连续的数组元素可以更好地利用缓存行减少缓存缺失。2. 索引访问数组可以通过索引直接访问元素而链表需要从头节点开始顺序遍历才能找到指定位置的节点。通过索引可以快速访问数组中的元素这在一些特定的操作中是非常有优势的例如查找某个特定位置的节点、根据节点索引快速更新或删除元素等。3. 空间效率相比链表数组实现二叉树可以更加节省空间。链表除了存储节点本身的数据之外还需要额外的指针来连接节点而数组只需要存储节点数据不需要额外的指针。 需要注意的是链表在插入和删除节点的操作上通常比数组更加高效因为插入和删除只需要改变相邻节点之间的指针指向而数组需要移动元素。因此在对二叉树进行频繁的插入和删除操作时链表可能更适合。而数组适合于对二叉树进行频繁的随机访问和操作的场景。 //用数组的方式来表示二叉树基本结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;3 初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}4打印
void HeapPrint(HP* php)
{assert(php);for (int i 0;i php-size;i){printf(%d , php-a[i]);}printf(\n);
}5销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-aNULL;php-size php-capacity 0;
}
6插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){//判断capacity是否为0并进行赋值int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;// 当前数组 插入数值的位置AdjustUp(php-a, php-size-1);
}7向上调整
在插入元素之时直接进行向上排序 将插入的元素与父辈元素进行比较并进行互换
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//孩子被调到顶是结束(即数组首元素)while (child0){//if (a[child]a[parent]) 小堆if (a[child] a[parent])//大堆{//孩子 小于/小于 父亲Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{//孩子 大于/小于 父亲break;}}
}
8交换两数组元素之间的值
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}9删除
将头部元素与尾部元素呼唤以防直接删除头元素倒是数据混乱 将其换到尾部进行删除在将换到同部的尾元素进行向下比较 进行替换寻找新的(最大/最小)头部元素
void HeapPop(HP* php)
{assert(php);assert(php-size0);Swap((php-a[0]), (php-a[php-size - 1]));php-size--;//向下调整AdjustDown(php-a, php-size, 0);
}10向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (childsize){//选出左右孩子中 小/大 的那个//if (child1size a[child 1] a[child])if (child 1 size a[child 1] a[child]){child;}//跟孩子父亲比较//if (a[child]a[parent])if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{//左右孩子都大于/小于父亲结束交换break;}}
}11取堆顶的元素
//取堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}12 判断二叉树是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}13计算该二叉树元素个数
int HeapSize(HP* php)
{assert(php);return php-size ;
}3堆排列
此时二叉树已近成型但进行排列时会设计到复杂度的问题之前的代码中存在问题效率低下此时的问题 1,你得先写一个Hp数据结构反而复杂 2有o(N)空间复杂度 每次使用建堆选数据 整体时间复杂度O(N^2) 效率太低没有使用到堆的优势 每次使用堆排列时都要重新创建一个数据结构并依次插入进行排序无疑是增加了时间复杂度 应该直接利用本身的数组进行堆排列
1建堆
建堆方式1 时间复杂度O(N*log(N))
一共N个数每个数向上调整log(N)次(层数依次对父辈进行交换) 故为 O(Nlog(N))
for (int i 1; i n; i){//每插入一个进行一次向上调整AdjustUp(a, i);}这段代码使用了一个循环其中执行了n-1次迭代从i1到in。每次循环内部都会调用AdjustUp(a, i)进行向上调整的操作。 在循环内部执行向上调整的操作的时间复杂度是O(log(i))其中i是当前循环的迭代次数。因为每次执行向上调整时需要比较和交换的次数与当前节点所在二叉树的高度有关而二叉树的高度是随着节点的插入逐渐增加的即高度与插入的节点数量有关。 根据每次迭代的时间复杂度为O(log(i))加上n-1次的循环总的时间复杂度为: O(log(1) log(2) … log(n-1)) 对于这个求和过程并没有一个简单的封闭解析解。但根据级数求和的性质可以得到这个求和结果的上界为O(n * log(n))。因此可以将上述代码的时间复杂度近似地表示为O(n * log(n))。 需要注意这个时间复杂度是在假设AdjustUp的时间复杂度为O(log(i))的情况下得到的。如果AdjustUp的时间复杂度比O(log(i))更高那么整个代码块的时间复杂度将会增加。 建堆方式2 时间复杂度O(N)
从最后一个非叶节点进行插入
for (int i (n - 1) / 2; i 0; i--){//最后一个非叶节点(n - 1) / 2//向下调整前提是字树必须是大/小堆AdjustDown(a, n, i);}这段代码使用了一个循环其中执行了(n-1)/21次迭代从i(n-1)/2到i0。 每次循环内部都会调用AdjustDown(a, n, i)进行向下调整的操作。 在循环内部执行向下调整的操作的时间复杂度是O(log(n))其中n是当前二叉树的节点数量。因为每次执行向下调整时需要比较和交换的次数与当前节点所在的子树的节点数量有关而每个节点至多有两个子节点所以向下调整的时间复杂度是与当前节点所在的子树高度相关即O(log(n))。 根据每次迭代的时间复杂度为O(log(n))加上(n-1)/21次的循环总的时间复杂度为: O(log(n) log(n) … log(n)) 展开求和后得到 (n-1)/21 次 log(n) 相加。根据级数求和的性质这个求和结果为 O(n)。因此可以将上述代码的时间复杂度近似地表示为 O(n)。 2排列数组 O(N * log(N))
此时二叉树已经排列完成在二叉树图像中元素已经按照 大堆/小堆 排好 但在数组中依旧是混乱排列要做到像堆排列就需要将数组进行排列 升序打印数组大堆 降序打印数组小堆 这里似乎与之前相反 之前 升序/降序 打印是要将首元素置换到末元素并进行打印删除被置换的元素向下调整 故为升序打印为小堆降序为大堆 而此处我们要将数组按照大小堆的形式排列 while (end0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;//--end缩小范围保证是按照数组 大/小 堆排序}若原本二叉树排列为大堆该代码就将数组排列成大堆 故 升序建大堆降序建小堆
成品展示
Head.h
#pragma once
#include stdlib.h
#include stdio.h
#include assert.h
#include stdbool.h//用数组的方式来表示二叉树基本结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HeapInit(HP* php);//交换两数组元素之间的值
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//销毁
void HeapDestroy(HP* php);//插入
void HeapPush(HP* php, HPDataType x);//向上调整
void AdjustUp(HPDataType x, int child);//向下调整
void AdjustDown(HPDataType* a, int size, int paarent);//删除
void HeapPop(HP* php);//取堆顶的元素
HPDataType HeapTop(HP* php);//判断是否为空
bool HeapEmpty(HP* php);//计算该二叉树元素个数
int HeapSize(HP* php);Head.c
#include Head.h//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}//打印
void HeapPrint(HP* php)
{assert(php);for (int i 0;i php-size;i){printf(%d , php-a[i]);}printf(\n);
}//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 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 (child 0){if (a[child]a[parent]) //小堆{//孩子 小于/小于 父亲Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{//孩子 大于/小于 父亲break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){//判断capacity是否为0并进行赋值int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;// 当前数组 插入数值的位置AdjustUp(php-a, php-size - 1);}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){//选出左右孩子中 小/大 的那个if (child1size 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 HeapPop(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 HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}//判断是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}//计算该二叉树元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}Test.c
Test.c只是用于测试代码菜单的写法本文将不进行讲解。 但Test.c中含有对查找and销毁and存储链元素个数的使用方法进行了示例可以当参考。
#include Head.hvoid test1()
{//升序打印--小堆//降序打印--大堆HP hp;HeapInit(hp);int a[] { 27,15,19,18,28,34,65,49,25,37 };int sz sizeof(a) / sizeof(a[0]);//将数组插入新的堆for (int i 0;i sz;i){HeapPush(hp, a[i]);}while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}
}void test2()
{HP hp;HeapInit(hp);int a[] { 27,15,19,18,28,34,65,49,25,37 };int sz sizeof(a) / sizeof(a[0]);//将数组插入新的堆for (int i 0;i sz;i){HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)){a[i] HeapTop(hp);HeapPop(hp);}HeapDestroy(hp);
}void test3()
{HP hp;HeapInit(hp);int a[] { 27,15,19,18,28,34,65,49,25,37 };int sz sizeof(a) / sizeof(a[0]);//将数组插入新的堆for (int i 0;i sz;i){HeapPush(hp, a[i]);}HeapPrint(hp);
}
//此时的问题
//1,你得先写一个Hp数据结构反而复杂
//2有o(N)空间复杂度
/*每次使用建堆选数据整体时间复杂度O(N^2)效率太低没有使用到堆的优势
*/
void test4(int*a ,int n)
{//本生就是一个数组直接利用自身建堆//建堆// 建堆方式1 时间复杂度O(N*log(N))//for (int i 1; i n; i)//{// //每插入一个进行一次向上调整// AdjustUp(a, i);//}// 建堆方式2 时间复杂度O(N)for (int i (n - 1) / 2; i 0; i--){//最后一个非叶节点(n - 1) / 2//向下调整前提是字树必须是大/小堆AdjustDown(a, n, i);}}/*1.将 最大的数/最小的数 换到 最小的数/最大的数并删除被换的数(最后的数)2.然后对 头部进行降序(将 最小的数/最大的数 下移重新找到 最大/最小 的数换到头部) 将效率提升至O(N*log(N))
*/
//升序 --建大堆
//降序 --建小堆
void test5(int* a, int n)
{//时间复杂度O(N)for (int i (n - 1) / 2; i 0; i--){//最后一个非叶节点(n - 1) / 2//向下调整前提是字树必须是大/小堆AdjustDown(a, n, i);}int end n - 1;//O(N * log(N))-O(N)O(N * log(N))O(N * log(N))while (end0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] { 5, 3, 2, 9, 7, 4, 1, 10, 8, 6};int sz sizeof(a) / sizeof(a[0]);test5(a,sz);return 0;
}本文到这就结束啦本文为万字解读创作不易若喜欢请留下免费的赞吧 感谢阅读
