二叉树的顺序结构

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

堆的概念及结构

在这里我们先学习一下堆，堆是一种特殊的二叉树形式

如果有一个关键码的集合K = { N1，N2 ，N3 ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： Ni<= N(2i+1)且 Ni<= N(2i+2)( Ni>= N(2i+1)且Ni >=N(2i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

★堆中某个节点的值总是不大于或不小于其父节点的值；

★堆总是一棵完全二叉树。

堆的实现

1、堆向下调整算法

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

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

后面在讲到堆的插入接口函数时，还会提到向上调整算法

2、堆的创建

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

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

此时调换1和8的位置时，8的左子树堆结构被破坏，所以在每一次发生元素交换的时候，都需要递归调用重新构造堆的结构

最后构造的大堆：8，7，6，5，1，3

3、堆的插入

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

★将堆顶元素和堆中最后一个元素进行交换

★删除最后一个元素

★将堆顶的元素向下调整，直到满足堆特性为止

4、堆的实现

这里堆的实现我们使用的是顺序表结构

堆的结构体及接口定义

// 大堆
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void AdjustUp(int* a, int child);//向上调整
void AdjustDown(int* a, int n, int parent);//向下调整
void Swap(HPDataType* px, HPDataType* py);//交换函数
void HeapInit(HP* hp);//堆的初始化
void HeapDestroy(HP* hp);// 堆的销毁
void HeapPush(HP* hp, HPDataType x);// 堆的插入
void HeapPop(HP* hp);// 堆的删除
HPDataType HeapTop(HP* hp);// 取堆顶的数据
void HeapPrint(HP* hp);//堆的打印
bool HeapEmpty(HP* hp);// 堆的判空
int HeapSize(HP* hp);// 堆的数据个数

堆的接口实现

交换函数(Swap)

代码如下：

void Swap(HPDataType* px, HPDataType* py)
{
  HPDataType tmp = *px;
  *px = *py;
  *py = tmp;
}

这里的交换函数不是接口函数，仅为了方便其他接口函数调用