建网站用什么软件好,滨州新闻头条最新消息,wordpress isadmin,长清治做网站今天#xff0c;我们来写一篇关于数据结构的二叉树的知识。
在学习真正的二叉树之前#xff0c;我们必不可少的先了解一下二叉树的相关概念。
一#xff1a;树的概念 树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层…今天我们来写一篇关于数据结构的二叉树的知识。
在学习真正的二叉树之前我们必不可少的先了解一下二叉树的相关概念。
一树的概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的 注意树形结构中子树之间不能有交集否则就不是树形结构
除了根结点外每个结点有且仅有一个父结点
一颗N节点的树又N-1条边
下面我们来具体给出树的相关名词 节点的度一个节点含有的子树的个数称为该节点的度 如上图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棵互不相交的树的集合称为森林 标注红色的为常用的橙色为概念 有了上面的铺垫后我们来认识一下二叉树
二叉树
图 二叉树组成
由三部分根左子树左孩子右子树右孩子 从上面我们知道
1.二叉树不存在度大于2的结点 2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
3. 存在情况 接下来我们认识
特殊的二叉树
1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是2^k-1 则它就是满二叉树。
2. 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树 证明满二叉树中高度为h的有多少个结点 完全二叉树前h-1都是满的 最后一层要求从左到右是连续的 高度为h的完全二叉数节点数量的范围是[2^(h-1),2^h-1] 由上面知道满二叉树为2^h-1. 根据完全二叉树的定义 2^(h-1)-1----不算最后一层的。然后再算最后一层2^(h-1)-112^(h-1) 所以它的范围[2^(h-1),2^h-1]。 此外对任何一颗二叉树如果度为0的叶结点个数为n0度为2的分支节点为2 则由n0n21.
结论度为0的永远比度为2的多1。 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储
我们知道顺序表是都一样的实际上就是数组嘛 而链表不一样我们通常用箭头那些是想象出来的实际上并没有箭头的。
同样二叉树也是
逻辑结构 想象出来的
物理结构 实实在在内存中是如何存储的
反向过来你把这棵树的一层一层的值依次往数组里面存储
如下图
逻辑结构想象成这样 物理结构实际就是数组 另外我们平时画图的时候很麻烦画出第一张图那么标准其实我们也是可以画出这样子
简便 通过观察上面得出的规律 表示二叉树的值在数组位置中的父子下标关系 parentchild-1/2 leftchlidparent*21 rightchlidparent*22 注意这里必须是从0开始不然就乱了
有人会问了能不能在完全二叉树那里使用呢 这里用数组存储完全二叉数有局限不适合。
因为浪费很多空间数组存储表示二叉树只适合完全二叉树。 好了有了上面的铺垫后现在让我们来实现一下堆。
堆
概念
什么是堆呢
我们将堆分为大堆和小堆
小堆 大堆 在写堆时底层代码实际就是数组 注意堆不是排序堆只规定父亲的大小并没有规定它的左右孩子的大小
插入时可能会影响部分祖先。 实际控制的是数组写的时候把它想象成树 一定义结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
1.需要一个数组
2.要算出数组的大小
3.最大容量 二初始化部分
void HeapInit(HP* php)
{assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType)*4);if (php-a NULL){perror(malloc fail);return;}php-size 0;php-capacity 4;
}
这里初始化跟之前的都差不多。
1.创建数组用malloc
2.初始化size为0
3.因为上面创建了数组4个位置所以初始化时的最大容量为4。 三销毁部分
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}
1.置空置零就可以了。 四Push部分
首先我们得思考一下堆咋push的。
由于本质上是数组所以我们push在数组的最后那里插。
假如在下面数组push一个数字60. 因此我们会写成这样一个代码
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * php-capacity*2);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;调整部分下面有讲AdjustUp(php-a, php-size - 1);
}
但是呢如果是像上面一样push了一个数字的话堆就乱了
变成了 面对这种问题我们又该怎么办呢
这里我们使用一种叫向上调整法解决这种问题 我们以大堆来举例子
我们发现上面是不是将30和60的位置交换了就可以重新变成大堆了
那么我们又是怎么变成这一步的呢
不能发现你看
1.将分为左孩子和右孩子和根三部分。
2.比较左孩子和右孩子拿出大的孩子再跟根比较。
3.如果大的孩子的数字大于根就交换。反之不换。
对上述做法叫做向上调整法。
对此我们写一个函数
向上调整部分
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;}}
} 解读
除了child这个位置前面数据构成堆
1.我们是不是得找到父亲结点。上面我们已经给出了父亲与孩子之间的公式变换了
2.由于交换这个代码内容在后面也是常用到的所以我们单独封装一个函数
交换部分
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x *p1;*p1 *p2;*p2 x;
}
3.这样容易忽略的问题是
while的条件弄成 while(child 0) 而不要弄成while (parent 0)
这里看似都没有问题运行时但是会不好。
parent 0意味着parent0才会中止但是parent会小于0吗不会因为这里最差的情况就是孩子等于0.
parent (child - 1) / 2;即就是-1/2按理是0.5但是这里是整形所以还是0还是会进入循环。
但是呢这个程序不会死循环parent0时进入循环但是它不满足if (a[child] a[parent])条件所以还是会到达break。
所以能正常跑但是不好最好用child0. 删除部分
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);
}堆的删除部分有人可能会想直接这样删 但是接下来的堆就会变成这样 直接挪动删除
1.效率低下。
2.父子兄弟关系全乱了。 那么我们想到用间接的方法来解决这种问题 1.我们先把第一个和最后一个交换。
2.删除最后一个。
3.接着向下调整法。
1什么是向下调整法即从上面往下调
1.找到孩子中大的数字与父亲比较孩子大的就交换。反之不交换
向下调整部分
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){// 选出左右孩子中大的那一个if (child 1 n a[child1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
} 1.这里采用的是假设左孩子大然后再循环里面再弄个if语句如果右孩子大的话就交换变成右孩子。因为左右孩子再邻位相差1
2.接着再比较父亲结点与大的孩子大就交换再更新父亲结点和孩子结点。反之就break跳出循环。 返回顶位置
HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}
判断空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
返回大小
int HeapSize(HP* php)
{assert(php);return php-size;
}
好了最后
附上总代码
Heap.h部分
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int HPTypeData;
typedef struct Heap
{HPTypeData* a;int size;int capacity;}Heap;void HPInit(Heap* php);
void HPDestory(Heap* php);
void HPPush(Heap* php, HPTypeData x);
void HPPop(Heap* php);
HPTypeData HPtop(Heap* php);
bool HPEmpty(Heap* php);
int HPSize(Heap* php);
Heap.c部分
#define _CRT_SECURE_NO_WARNINGS 1
#include Heap.hvoid HPInit(Heap* php)
{assert(php);php-a (HPTypeData*)malloc(sizeof(HPTypeData)*4);if (php-a NULL){perror(malloc fail);return;}php-capacity 4;php-size 0;
}
void HPDestory(Heap* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}void Swap(HPTypeData* p1,HPTypeData* p2)
{HPTypeData temp *p1;*p1 *p2;*p2 temp;
}
void Adjustup(HPTypeData* 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 HPPush(Heap* php, HPTypeData x)
{assert(php);if (php-a php-capacity){HPTypeData* temp (HPTypeData*)realloc(php-a, sizeof(HPTypeData) * php-capacity * 2);if (temp NULL){perror(realloc fail);return;}php-a temp;php-capacity * 2;}php-a[php-size] x;php-size;//Adjustup(php-a,php-a[php-size-1]);Adjustup(php-a,php-size-1);}Adjustdown(HPTypeData* 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[parent],a[child]);parent child;child parent * 2 1;}else{break;}}
}
void HPPop(Heap* php)
{assert(php);assert(!HPEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;Adjustdown(php-a, php-size, 0);
}
HPTypeData HPtop(Heap* php)
{assert(php);return php-a[0];
}
bool HPEmpty(Heap* php)
{assert(php);return php-size 0;
}
int HPSize(Heap* php)
{assert(php);return php-size;
}
test.c部分
#define _CRT_SECURE_NO_WARNINGS 1
#include Heap.h//int main()
//{
// HP hp;
// HeapInit(hp);
// HeapPush(hp, 4);
// HeapPush(hp, 18);
// HeapPush(hp, 42);
// HeapPush(hp, 12);
// HeapPush(hp, 21);
// HeapPush(hp, 3);
// HeapPush(hp, 5);
// HeapPush(hp, 5);
// HeapPush(hp, 50);
// HeapPush(hp, 5);
// HeapPush(hp, 5);
// HeapPush(hp, 15);
// HeapPush(hp, 5);
// HeapPush(hp, 45);
// HeapPush(hp, 5);
//
// int k 0;
// scanf(%d, k);
// while (!HeapEmpty(hp) k--)
// {
// printf(%d , HeapTop(hp));
// HeapPop(hp);
// }
// printf(\n);
//
// return 0;
//}// 排升序 -- 建大堆
void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}// 自己先实现}int main()
{int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序HeapSort(a, 10);return 0;
}
最后到了本次鸡汤部分
小小的人有大大的梦想干
