数据结构——二叉树——堆（1）

今天，我们来写一篇关于数据结构的二叉树的知识。

在学习真正的二叉树之前，我们必不可少的先了解一下二叉树的相关概念。

一：树的概念

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

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

除了根结点外，每个结点有且仅有一个父结点

一颗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的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

标注：红色的为常用的，橙色为概念

有了上面的铺垫后，我们来认识一下二叉树：

二叉树

图：

二叉树组成： 

由三部分：根，左子树（左孩子），右子树（右孩子）

从上面，我们知道：

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)-1+1==2^(h-1)

所以，它的范围：[2^(h-1),2^h-1]。

此外，对任何一颗二叉树，如果度为0的叶结点个数为n0，度为2的分支节点为2 ，则由n0=n2+1.

结论：度为0的永远比度为2的多1。

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，

我们知道：顺序表是都一样的，实际上就是数组嘛
而链表不一样，我们通常用箭头那些是想象出来的，实际上并没有箭头的。

同样，二叉树也是：

逻辑结构  想象出来的

物理结构  实实在在内存中是如何存储的

反向过来，你把这棵树的一层一层的值依次往数组里面存储

如下图：

逻辑结构：（想象成这样）

物理结构：（实际就是数组） 

  

另外，我们平时画图的时候，很麻烦画出第一张图那么标准，其实，我们也是可以画出这样子

简便：

 通过观察上面得出的规律：

表示二叉树的值在数组位置中的父子下标关系

parent=（child-1）/2

leftchlid=parent*2+1
rightchlid=parent*2+2

注意，这里必须是从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，意味着parent<0才会中止，但是，parent会小于0吗？不会，因为这里最差的情况就是孩子等于0.

parent = (child - 1) / 2;即就是-1/2，按理是0.5，但是这里是整形，所以还是0，还是会进入循环。

但是呢？这个程序不会死循环，parent=0时，进入循环，但是它不满足if (a[child] > a[parent])条件，所以还是会到达break。

所以能正常跑，但是不好，最好用child>0.

删除部分

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[child+1] > 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
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef 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.h"void 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;
}

最后，到了本次鸡汤部分：

小小的人，有大大的梦想！干！