文章目录
二叉树&堆
1、概念、结构与性质
1.1二叉树定义
在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
例如下面就是一棵二叉树：
1.2二叉树的特点
- ⼆叉树不存在度⼤于 2 的结点
- ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树 注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的
1.3特殊的二叉树
**满二叉树：**⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀ 个⼆叉树的层数为 K，且节点总数是2k-1，则他就是满二叉树
**完全二叉树：**完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个 结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称 之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
1.4二叉树结构的性质
- 若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2 i−1 个结点
- 若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2 − h 1 比特就业课
- 若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 ( log 以2为底， n+1 为对数)
1.5二叉树存储结构
⼆叉树⼀般可以使⽤两种结构存储，⼀种顺序结构，⼀种链式结构。
1.5.1顺序结构
顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有 空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。
完全二叉树的顺序存储：
非完全二叉树的顺序存储：
1.5.2链式结构
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法 是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩 ⼦所在的链结点的存储地址 。
2、实现顺序结构二叉树
⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备 其他的特性
2.1堆的概念和结构
如果有⼀个关键码的集合 ，把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储，在⼀个⼀维数组中，并满⾜： （ 且 ）， i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。
2.2堆的性质
- 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值； •
- 堆总是⼀棵完全⼆叉树。
2.3二叉树性质
-
对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
- 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
- 若 2i+1=n 否则⽆左孩⼦
- 若 2i+2=n 否则⽆右孩⼦
2.4堆的实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//默认初始化堆
void HPInit(HP* php);
//利⽤给定数组初始化堆
void HPInitArray(HP* php, HPDataType* a, int n);
//堆的销毁
void HPDestroy(HP* php);
//堆的插⼊
void HPPush(HP* php, HPDataType x);
//堆的删除
HPDataType HPTop(HP* php);
// 删除堆顶的数据
void HPPop(HP* php);
// 判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
向上调整法（堆的插入
将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆
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 = (parent - 1) / 2;
}
else
{
break;
}
}
}
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);
}
- 时间复杂度为：O(n ∗ log2n)
向下调整法（堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏ 向下调整算法。向下调整有一个前提就是左右子树必须有一个是一个堆，才能调整。
调整过程：
- 将堆顶元素与堆中最后⼀个元素进⾏交换
- 删除堆中最后⼀个元素
- 将堆顶元素向下调整到满⾜堆特性为⽌
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);
}
向下调整算法建堆时间复杂度为： O(n)
标签：结点,parent,int,二叉树,child,php From： https://blog.csdn.net/TTKunn/article/details/141307782