【数据结构—二叉树的基础知识介绍和堆的实现（顺序表）】

有一个特殊的结点，称为根结点，根节点没有前驱结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。

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

1.2 树的相关概念

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。

1.4 树在实际中的运用（表示文件系统的目录树结构）

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空。
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树是一个特殊的树，度最大为2。

从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

2.2 特殊的二叉树：

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

每一层都是满的。

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

前h-1层是满的，最后一层不一定满，但是从左到右必须连续。

2.3 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

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

2. 链式存储

这个我们下篇文章再讲！

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

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

3.2 堆的分类、性质与结构

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

堆的分类：

大堆：任意一个父亲节点 >= 孩子节点。

小堆：任意一个父亲节点 <= 孩子节点。

堆不一定是有序的。

二叉搜索树，左子树的值要比根要小，右子树的值要比根要大。我们用来查找数据，最多查找高度次。
堆永远只考虑父亲和孩子的关系，而不考虑兄弟和叔侄之间的关系。

4.堆的实现

4.1头文件的实现——（Heap.h）

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//这个代码是针对小堆的
typedef int HPDataType;

//底层看上去是顺序表，但其实不是，因为从逻辑上，我们把它看成是二叉树，并且把它调整成大堆或小堆的顺序
//顺序表中进来的值没有要求，但是堆是对值有顺序要求的
typedef struct Heap
{
	HPDataType* a;
	int size;//数组有效的元素个数 == 数组最后一个元素的下一个位置的下标
	int capacity;
}HP;

//初始化
void HeapInit(HP* php);
//销毁
void HeapDestroy(HP* php);
//插入数据
void HeapPush(HP* php, HPDataType x);

//规定删除的是堆顶（根节点）
void HeapPop(HP* php);
//获取堆顶元素
HPDataType HeapTop(HP* php);
//堆中的元素个数
size_t HeapSize(HP* php);
//判空
bool HeapEmpty(HP* php);

//向上调整法：
void AdjustUp(HPDataType* a, int child);
//向下调整法：
void AdjustDown(int* a, int size, int parent);

void Swap(HPDataType* p1, HPDataType* p2);

4.2源文件的实现——（Heap.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

//初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
//销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	//free()的是空，也没有任何问题，free会对空进行检查的
	php->a = NULL;
	php->capacity = php->size = 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;
		}
	}
}

//插入一个数据的前提是：整棵树本身是堆的形式。
//插入一个数据之后，还要保持堆的形式：
//1、相当于顺序表的尾插；2、然后我们需要把插入的数据向上调整（调整数据可以用递归、也可以用循环）
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, newcapacity * sizeof(HPDataType));
		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 AdjustDown(int*a,int size,int parent)
{
	int child = parent * 2 + 1;
	//如何判断叶节点呢？
    //最后一个数据的下一个位置下标就是size，想判断一个节点是否是叶节点，就看这个节点有没有左孩子节点，
    //这个节点的下标乘2加1，看有没有超出size的范围
	while (child < size)
	{
		//小堆：任意一个父亲的值都要<=孩子节点的值
		//假设左孩子小，让左孩子与右孩子比较，若右孩子更小，那就孩子下标+1
		//但是有的子树有左孩子，但是不一定有右孩子，那么当比较右孩子时，访问右孩子的下标会造成越界访问
		if (child+1 <size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//规定删除的是堆顶（根节点）
//我们之前对顺序表(底层结构是数组)中传统的删除数据的方式：挪动数据覆盖，删除根（O(N)）,
//(这样会造成整棵树的父子关系全乱了，大小关系乱了)
//我们使用另一种方式删除数据：1、首尾交换；2、尾删
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];
}
//堆中的元素个数
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.3测试文件的实现——（test.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//逻辑结构：想象出来的
//物理结构：内存中实际存在的结构
//树的高度或深度：我们从1开始计算，因为空树时，为0，只有根节点时，高度为1；
//如果从0开始计算，那空树时，为-1，只有根节点时，高度为0.
//堆不一定是有序的。
//不是完全二叉树和满二叉树的话，适合用链式结构存储

//完全二叉树或满二叉树会演化出一个堆；堆有两个含义：1、堆排序；2、top k问题
//普通的二叉树没有必要用堆进行存储，没有意义

//二叉搜索树，左子树的值要比根要小，右子树的值要比根要大。我们用来查找数据，最多查找高度次
//堆永远只考虑父亲和孩子的关系，而不考虑兄弟和叔侄之间的关系。

//size：是最后一个有效数据的下一个位置，因为数组的下标是从0开始的

//向上和向下调整的时间复杂度最多是高度次，是O(logN)

//数据结构的第一要务：在内存当中管理数据
int main()
{
	int a[] = { 5,4,7,4,9,1,0,3 };
	HP hp;
	HeapInit(&hp);
	//我们在这个地方没有排序，排序的本质，是要在数组这个地方排序
	//我们只是把数组里的值插入到堆里面去，然后有序的从堆里走出来（小堆或大堆）
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
	/*int k = 3;
	while (k--)
	{
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}*/

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	//实现数组的排序：我们可以用数据结构，把堆里面的值一个个的放回数组里（前提是有实现好的堆）
  
	return 0;
}