【数据结构初阶】二叉树---堆

一、树的概念（什么是树）

    树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。那么为什么把它叫作树呢？是因为它倒挂着就是树的形状，根朝上，叶朝下。

• 树有一个特殊节点，就是根节点，也就是最顶上的没有前驱节点的那个节点
• 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i
  <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱节点，可以有0个或多个后继节点
• 因此，树是递归定义的
  
  ps:树的子树之间是不能有交集的，有交集的就不能称之为树。如下图：
  
  树的基本术语：
• 节点的度 ：一个节点含有的子树数量
• 叶节点 ：度为0的节点，即没有子节点的节点
• 根节点 ：没有父节点的节点
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
• 子结点：一个结点含有的子树的根结点称为该结点的子结点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点
• 层 ：根节点定义为第1层，其子节点为第2层，以此类推
• 高度 ：从指定节点到叶节点的最长路径的长度
• 森林 ：由多棵（两棵及以上）树组成的集合。

二、二叉树的概念及结构

2.1 二叉树的概念

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

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

2.2 二叉树的性质

    性质1：二叉树的第i层上至多有2i-1（i≥1）个节点
    性质2：深度为h的二叉树中至多含有2h-1个节点
    性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1
    性质4：具有n个节点的满二叉树深为log2(n+1)
    5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

• 若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.3 二叉树存储结构

    二叉树又可以分为顺序存储和链式存储两种：
1.顺序存储：
    顺序存储就是使用数组结构来存储，而顺序存储一般只表示完全二叉树，否则会造成空间浪费的现象。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2.链式存储：
    二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ：

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* left; // 指向当前结点左孩子
 struct BinTreeNode* right; // 指向当前结点右孩子
 BTDataType data; // 当前结点值域
}

三、二叉树的顺序结构

3.1 堆的概念及结构

    若有一个集合{k0,k1,k2…k(n-1)}，将它所有的元素以完全二叉树的顺序存储形式于一个一维数组中，并满足：{k(i)<=k(2i+1)且k(i)<=k(2i+2)};或{k(i)>=k(2i+1)且k(i)>=k(2i+2)}，则称为小堆或大堆。

堆的性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值
• 堆总是一棵完全二叉树
  

3.2 堆的向下调整算法

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

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

3.3堆的创建

    下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。

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

四、堆的代码实现

堆的底层逻辑：动态数组

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
 
// 类型定义
typedef int HPDataTpye;
 
typedef struct Heap
{
	HPDataTpye* arr;
	int size;// 元素个数
	int capacity;// 空间容量
}Heap;
//初始化
void  HPInit(HP* php);
//交换头尾
void Swap(HPDataType* p1, HPDataType* p2);
//数据向下调整
void AdjustUp(HPDataType* a, int child);
//数据向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//销毁堆
void HPDestroy(HP* php);
//向堆添加数据
void HPPush(HP* php, HPDataType x);
//删除数据
void HPPop(HP* php);
//找堆顶数据
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);

4.1 堆的初始化

    堆的初始化方式是跟顺序表的初始化是一样的，因为堆使用的是顺序存储：

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

4.2 堆的销毁

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

4.3 堆的插入

    堆的插入方式也跟顺序表的差不多，就是将新的节点插入数组的尾部，但是光插入还不行，还要继续调整节点的位置，因为插入节点后有可能使原本的堆变为数组而不是堆了：

具体的代码实现：

//数据向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//利用数组下标找到parent的位置
	while (child > 0)//while(parent>=0)属于歪打正着
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入数据
void HPPush(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");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);//将数据插入后进行向上调整
}

4.4 堆的删除

    堆的删除删的是堆顶的数据，而删除堆顶的数据就没有想象中的这么简单了。删除堆顶的数据不能直接将其释放掉，若直接释放，根就没有了，只剩下左右两个堆，又要将堆重新建好，代价太大；这时我们应该将堆尾和堆顶数据换位置，再将堆尾的数据释放掉，然后将堆顶的数据向下调整直到重新成堆：

代码实现：

//数据向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	while (child < n)  // 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->arr[0], &php->arr[php->size - 1]);
	php->size--;

	AdjustDown(php->arr, php->size, 0);
}

4.5 堆的判空及取堆顶数据

//找堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->arr[0];//直接将数组第一个数据返回即可
}
//判空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;//当size等于0时就返回空
}

4.6 测试

#include"Heap.h"
void TestHP01()
{
	
	HP hp;
	HPInit(&hp);
	int arr[] = { 4,2,8,1,5,6,9,7,3,2 };
	for (size_t i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HPPush(&hp, arr[i]);
	}
	/*while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));

		HPPop(&hp);
	}*/
	HPDestroy(&hp);
}
int main()
{
	TestHP01();
	return 0;
}

调试结果（形成小堆）：