树基本概念及堆的各种接口的实现|二叉树|完全二叉树|向上调整|向下调整(C)

线性表的优缺点

顺序表：数组
缺点：

1. 中间或者头部插入删除数据要挪动数据，效率低
2. 空间不够，只能扩容，扩容有消耗
3. 倍数扩容，用不完，存在空间浪费
   优点：
4. 下标随机访问，排序，二分查找适合
5. CPU高速缓存命中率比较高

链表：
优点：

1. 任意位置插入删除效率高
2. 按需申请释放，不存在扩容
   缺点：
3. 不能下标随机访问
4. CPU高速缓存命中率低

树的概念及结构

树的概念

树是一种非线性的数据结构，它是由$n(n\ge 0)$个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点除根节点外，其余结点被分成$M(M>0)$个互不相交的集合 { T 1 , T 2 , … , T m } \left\{ T_{1},T_{2},\dots,T_{m} \right\} {T1​,T2​,…,Tm​}，其中每一个集合$T_i(1\le i\le m)$又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 因此，树是递归定义的。
  树形结构中，子树之间不能有交集，否则就不是树形结构

树的相关概念

1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
7. 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
11. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
13. 森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示

孩子兄弟表示法

typedef int DataType;
struct Node
{struct Node* _firstChild1;     //第一个孩子节点struct Node* _pNextBrother;    //指向其下一个兄弟节点DataType _data;                //节点中的数据域
}

二叉树的概念及结构

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
   

从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
   最多两个孩子，也可以是1个或0个

对于任意的二叉树都是由以下几种情况复合而成的：

特殊的二叉树

1. 满二叉树
   一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

假设满二叉树的高度是h，每一层的结点都是满的，每一层是$2^{i-1}$个结点，总共有
$$F(h)=2^0+2^1+\cdots +2^{h-2}+2^{h-1}=2^h-1$$
假设这棵满二叉树的结点是N个
$$N=2^h-1,h={\log }_2(N+1)$$

2. 完全二叉树
   完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

假设它的高度是h，前h-1层是满的，最后一层不一定满，从左到右是连续的。
高度是h，结点范围是
$$[2^{h-1},2^h-1]$$

二叉树的存储结构

1. 顺序存储
   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
   

规律：
$$leftchild=parent\ast 2+1$$
$$rightchild=parent\ast 2+2$$
$$parent=(child-1)/2$$
任意位置通过下标可以找父亲或者孩子

非完全二叉树不适合用数组存储
满二叉树或完全二叉树适合用数组存储

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储
这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

如果有一个关键码的集合 K = { k 0 , k 1 , k 2 , … , k n − 1 } K=\left\{ k_{0},k_{1},k_{2},\dots,k_{n-1} \right\} K={k0​,k1​,k2​,…,kn−1​}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：$K_i\le K_{2\cdot i+1}且K_i\le K_{2\cdot i+2}(K_i\ge K_{2\cdot i+1}且K_i\ge K_{2\cdot i+2})i=0,1,2,\dots$，则称为小堆(或大堆)。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

非线性结构，完全二叉树
适合用数组存储
小堆：树中任意一个父亲都小于等于孩子
大堆：树中任意一个父亲都大于等于孩子

可以把一个数组看作完全二叉树，

底层：

• 物理结构，数组
• 逻辑结构：完全二叉树

小堆，底层数组不一定升序；大堆不一定降序
小堆的根是整棵树的最小值；大堆的根是整棵树的最大值

应用：

1. topk问题
2. 堆排序 $O(n\ast {\log }_{2}N)$

堆的实现

堆的定义

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

• 有一个指针，作为数组的地址
• size表示数据个数
• capacity表示容量

堆的初始化

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

• assert判断传给的php是否为空
• 把a指针置为空
• size和capacity置为0

用数组初始化堆

直接给一个数组，把数组插入到堆里

int a[] = {1,5,3,8,7,6};

void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);if (tmp == NULL){perror("realloc fail");exit(-1);}php->size = 0;php->capacity = 0;memcpy(php->a, a, sizeof(HPDataType) * n);for (int i = 0; i < n; i++){AdjustUp(php->a, i);}
}

• assert判断堆和数组的指针是否为空
• 给php的a指针处，malloc，动态分配n个数组元素大小的空间，正好就是数组的大小
• perror检查是否malloc成功
• 将size和capacity置为0
• 将数组的内容拷贝到php的a指针上
• 最后从根节点开始，也就是从数组首元素开始向上调整，循环直到数组末尾

堆的销毁

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

• assert判断php是否为空
• 直接free掉php的a指针
• 将size和capacity置为空

交换数据

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

• 传参是传两个数据的指针
• 直接将一个数据解引用赋给创建的临时变量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 = (parent - 1) / 2;}else{break;}}
}

• 传参给的是数组的首元素地址也就是数组的地址和一个子节点的数组下标
• 通过子节点的下标算出它的父节点的下标
• 这里是建小堆，所以如果子节点比父节点小，将它俩交换
• 将父节点设为新的子节点，再计算出父节点的位置，这样循环，直到子节点大于父节点停止
• 如果这个子节点足够小，就一直遍历到根节点处，也就是子节点的坐标等于0为止
• 如果要建大堆，将小于号改为大于号

向下调整

给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};  

最坏调整到叶子节点，因为再调整就超出了数组范围，

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;}}
}

• 传参传的是数组的地址，数组的大小和想要开始向下调整的父节点的下标
• 已知父节点的下标，算出它的左孩子的下标
• 再比较左孩子和右孩子，如果右孩子比左孩子小，++child，也就是找到比较小的那一个孩子，这里要求右孩子的下标必须小于等于数组的大小，防止越界
• 这里还是小堆，如果子节点小于父节点，将他俩交换
• 将子节点设为新的父节点，继续计算子节点的下标，找出比较小的孩子，往下遍历，直到子节点大于父节点，跳出循环
• 或者直到child下标超出n，即遍历完整个数组

插入数据

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){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);
}

• assert判断php是否为空
• 如果size等于capacity，需要扩容
• 先算出新的容量的大小，如果旧容量是0，就设为4，否则将旧容量乘2
• 创建一个临时指针tmp，动态申请新容量大小的空间
• 用perror检查内存是否申请成功
• 将申请好的空间赋给php->a，将newcapacity赋给capacity
• 如不需要扩容或扩容完毕，将x赋给数组的新元素的下标处，将size++
• 再将这个插在最后的子节点向上调整，形成新的堆

堆的打印

void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

• assert判断php是否为空
• 就像遍历数组一样从0下标开始遍历到最后

堆的删除

删除不能直接将数组往左挪动，这样变动之后不一定是小堆，因为小堆只有父节点和子节点之间的大小关系，变动之后，兄弟节点变为父子节点，叔侄节点变为兄弟节点，父子节点的关系可能会发生变动
所以把根节点的值和最后一个节点的值交换，然后删去最后一个节点，这样左右子树依旧是小堆
最后向下调整，向下调整的前提是：左右子树是小堆/大堆

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);
}

• assert判断php是否为空，堆是否为空
• 将根节点和最后一个节点交换
• 直接–size，将最后一个节点删除
• 将从根节点开始向下调整

返回堆顶

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

• assert判断php是否为空，堆是否为空
• 直接返回数组的0下标的数据，即根节点

判空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

• assert判断php是否为空
• 直接返回判断size是否为0，为0返回true，否则返回false

堆的各种接口的实现

#pragma once
#include <stdio.h>
#include <stdlib.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 HeapInitArray(HP* php, int* a, int n);
void HeapDestroy(HP* php);
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HeapPush(HP* php, HPDataType x);
void HeapPrint(HP* php);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);

#include "Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);if (tmp == NULL){perror("realloc fail");exit(-1);}php->size = 0;php->capacity = 0;memcpy(php->a, a, sizeof(HPDataType) * n);for (int i = 0; i < n; i++){AdjustUp(php->a, i);}
}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 = (parent - 1) / 2;}else{break;}}
}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 HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){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 HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}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;
}

#include "Heap.h"int main()
{int a[] = { 2,3,4,7,4,6,8 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int)){HeapPush(&hp, a[i]);}HeapPrint(&hp);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);return 0;
}