【C】初阶数据结构7 -- 树与顺序结构的二叉树(堆)

这篇文章将会介绍一个新的数据结构 -- 树，以及一种特殊的树 -- 二叉树，并用数组来实现二叉树，用数组实现的二叉树也叫做堆。

1 树

1）树的概念

2）树的结构

（1）逻辑结构

（2）物理结构

a. 双亲表示法

b. 孩子兄弟表示法

2 二叉树

1）二叉树的概念

2）二叉树的结构

（1）逻辑结构

（2）几种特殊的二叉树

a. 满二叉树

编辑b. 完全二叉树

（3）二叉树的性质

（4）物理结构

a. 链式结构

b. 顺序结构

3 数据结构堆

1）堆的概念

2）堆的分类与结构

（1）堆的分类

a. 大根堆

b. 小根堆

（2）逻辑结构

（3）物理结构

3）堆的实现

（1）堆的初始化、销毁、求有效元素的个数、判空

（2）向上调整算法

（3）向下调整算法

（4）堆数据的插入、取堆顶元素、删除堆顶元素

4）代码

重点一  树的概念与结构

1 树

1）树的概念

不同于之前的顺序表、链表以及栈和队列，树是一种非线性的数据结构，它是由 n (n >= 0) 个有限节点组成的具有层次关系的集合。

2）树的结构

（1）逻辑结构

树之所以叫做树，就是因为其逻辑结构看起来就像一棵倒着的树，其有一个根节点在最上方，底下连着他的分支。我们可以把数想象成以下的这个结构：

要想一个数据结构成为一棵树，只有一些要求的：

a. 树有空树和非空树之分，空树就是树中没有节点；在非空树中
   有且仅有一个特殊的节点叫做根节点，根节点是没有前驱的。

b. 除根节点外，其余节点被分成 M 个互不相交的集合 Ti(T1, T2...)
   ，这些集合中的节点又构成一棵与整棵树结构相似的子树。如：图中的
   B、E、F 是一棵子树， C、G、J、K、L 也是一棵子树，而G、J、K、L
   又构成了一棵子树。

c. 在树形结构中，子树之间不能有交集。

d. 除了根节点以外。每一个节点有且仅有一个直接前驱。

e. 一棵有 N 个节点的树有 N - 1 条边。

通过其结构来看，其实树是一种递归定义的数据结构，树中包含相同结构的子树，所以树的大部分操作都可以通过递归算法来解决。

底下的这个结构就不是一棵树：

如果子树之间有交集的话，那么这个数据结构就会变成图（以后会讲解的，其是比树更为复杂的数据结构）。

（2）物理结构

在介绍物理结构之前，我们先介绍一下树中常用的专业术语，依照此图进行举例：

a. 父节点/双亲节点：是指树中一个节点的直接前驱（根节点除外，根节点没有父节点）。如：A

就是 B 的父节点，C 是 G 的父节点；但注意，A 不是 G 的父节点，因为 A 并不是 G 的直接前驱。

b. 子节点/孩子节点：一个节点的直接后继称为子节点。如：C 是 A 的子节点，H 是 D 的子节点。

c. 节点的度：一个节点的孩子节点的个数成为该节点的度。如：A 节点的度为 3，C 节点的度为 1。

d. 树的度：一棵树里，最大节点的度称为树的度。如：上面那棵树的度为 3。

e. 叶子结点/终端节点：度为 0 的节点成为叶子节点。如：图中的 E、F、J、K、L、H、M 节点都是叶子结点。

f. 分支节点/非终端节点：度不为 0 的节点成为分支节点。如：A、B、C、D 节点。

g. 兄弟节点：拥有同一个父亲的节点称为兄弟节点。如：B、C、D 节点就是兄弟节点。

h. 节点的层次：根节点的层次为 1，根节点的孩子的层次为 2，依次类推。如：E、F、G、H、I 所处层次就为 3。

i. 树的高度或者深度：树中节点的最大层次。如：上面那棵树的高度就是 4。

j. 节点的祖先：从一个节点出发，其到根节点上所以节点。如：A 是所有节点的祖先；G、C、A 是 J、K、L 的祖先。

k. 路径：从一个节点出发，沿父节点 - 祖先 - 子节点到达另一个任意节点的序列。如：G 到 H 的路径为 G - C - A - D - H。

l. 子孙：以某节点为根的子树中的任一节点都叫做这个节点的子孙。如：树中的除 A 以外的所有节点都是 A 的子孙。

m. 森林：由 m 课互不相交的树的集合成为森林。如底下这两棵树就构成森林：

由于树的结构比较复杂，所以表示其节点结构的方法不止一种，下面介绍三种常用的用来表示树的节点的结构

a. 双亲表示法

是一段连续的空间（数组）来存储每个节点的数据以及其双亲节点在这个数组中的下标：

typedef int TNDataType;
//节点的结构
typedef struct TreeNode
{
  TNDateType data;//存储数据
  size_t     parent;//双亲节点在数组中的下标
}TreeNode;

//树的结构
typedef struct Tree
{
  TreeNode* arr;//存储树的节点的数组
  int root;//根节点在数组中的下标
  int size;//树中节点的个数
}Tree;

如上面那棵树用双亲表示法如图所示：

在Tree结构中添加 root 和 size 主要是为了方便进行树的遍历以及返回树中元素个数的。

该结构适合于频繁查找某一个节点的双亲节点，直到节点的里存储的数据就可直接查找到其双亲是谁，但是查找一个节点的孩子就需要遍历整个数组，因为只有遍历完整个数组才能知道哪个节点是以该节点所在下标作为双亲的。

b. 孩子兄弟表示法

孩子兄弟表示法是指结构中有一个指向第一个孩子节点（最左边的孩子）的指针域，有一个指向其兄弟节点的指针域，还有一个表示其存储数据的数据域。结构如下：

typedef int TreeDataType;
//节点的结构
typedef struct TreeNode
{
  struct TreeNode* firstchild;//指向第一个孩子
  struct TreeNode* brother;//指向其兄弟节点
  TreeDataType     data;//存储的数据
}TreeNode;

孩子兄弟表示法就是用链表作为底层结构，然后让其节点链接起来，所以只需要节点的结构就可以了，不需要树的结构，如以上那个树用孩子兄弟表示法如图：

树还有别的表示法，比如孩子表示法等等，在这里就不一一列举了。

重点二  二叉树的概念与结构

2 二叉树

1）二叉树的概念

二叉树是在树形结构中最常用的树，比如二叉搜索树（二叉排序树）、AVL树（二叉平衡树）、红黑树等等。二叉树是一种特殊的树，二叉树中节点的度最多为2（0,1,2），其子树具有左子树和右子树之分。需要注意的是，二叉树的左右子树是有次序的，不能颠倒。

2）二叉树的结构

（1）逻辑结构

由概念可知，一棵二叉树是由根节点与左子树和右子树构成的，所以一棵二叉树如下图所示：

（2）几种特殊的二叉树

a. 满二叉树

所有节点的度数都为2的二叉树，其被成为满二叉树，如：

b. 完全二叉树

对于深度为 k 的一棵二叉树，其节点数为 n，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 到 n 的节点（根节点为1，根节点的左孩子为2，根节点的右孩子为3，根节点左孩子的左孩子为4，依次类推）一一对应时，这棵二叉树为完全二叉树，如（绿色数字为编号）：

所以，满二叉树是一棵特殊的完全二叉树。

（3）二叉树的性质

二叉树由于其特别好的结构，左右子树具有次序，所以会具有一些性质：
a. 若规定根节点层数为1，则二叉树第 i 层上至多有 $2^{i-1}$ 个节点。所以对于层数为 k 的满二叉树来说，其节点个数为 $2^{0} + 2^{1} + 2^{2} + 2^{3} + ... + 2^{k - 1} = 2^{k} - 1$ 个节点（等比数列求和）。

b. 若规定根节点层数为1，则深度为 h 的二叉树其最多节点个数（就是当这棵二叉树为满二叉树时的节点个数）为 $2^{h} - 1$ 个。

c. 若规定根节点层数为1，则具有 n 个节点的满二叉树的深度为 $h = \log_{2}(n + 1)$ 层。该性质是通过满二叉树节点个数推出来的，因为满二叉树节点个数 $n = 2^{h} - 1$ ，所以 $h = \log_{2}(n + 1)$ ；具有 n 个节点的完全二叉树的深度为 $h = \left \lfloor \log_{2}n \right \rfloor + 1$ （ $\left \lfloor \right \rfloor$ 为向下取整符号）。

d. 对于任意一棵二叉树，若度为 0 的节点的个数为 $n_{0}$ ，度为2的节点的个数为 $n_{2}$ ，则 $n_{0} = n_{2} + 1$ 。

证明：设度为0的节点的个数为a，度为1的节点的个数为b，度为2的节点的个数为c，则整棵树的边数（边为两个节点之间的连线）为 2c + b；而边的个数又等于 a + b + c -1（每个节点都与其父节点连着一条边，而根节点没有父节点）；故 2c + b = a + b + c - 1 ==> a = c + 1。

（4）物理结构

a. 链式结构

对于二叉树的实现，一般是采用链式结构来实现，结构中含有 3 个域，有两个是指向左孩子和右孩子的指针域，还有一个是节点所包含数据的数据域：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;//指向左孩子
  struct BinaryTreeNode* right;//指向右孩子
  BTDataType data;//数据
}BTNode;

b. 顺序结构

二叉树的顺序结构又叫做堆，是通过数组来实现的，接下来我们就来主要讲解其实现。

重点三  堆的概念与结构

3 数据结构堆

1）堆的概念

堆是用顺序结构实现的二叉树，需要注意的是顺序结构只适合用来存储一棵完全二叉树，因为完全二叉树可以充分利用内存空间，所以堆总是一棵完全二叉树。

2）堆的分类与结构

（1）堆的分类

堆分为两种：

a. 大根堆

大根堆是指在一棵完全二叉树中，某个节点的值总是不大于其父节点的值。在大根堆中，没有节点的值是大于根节点的值的。

b. 小根堆

小根堆是指在一棵完全二叉树中，某个节点的值总是不小于其父节点的值。在小根堆中，没有节点的值是小于根节点的值的。

（2）逻辑结构

由定义可知，堆是一棵完全二叉树，结合大根堆和小根堆的定义，我们可以把一个堆想象成如下结构：

（3）物理结构

物理结构其实就是数组，但是堆的物理结构不像以前的顺序表一样，用于存储数据的数组是有编号的：

如果把一个堆从根节点为0开始从上往下开始编号，那么其每个节点对应的编号正好就是其在数组中存储的下标，通过观察节点的编号可以发现堆有如下性质：
a. 一个编号为 i (i > 0)的节点，其父节点的编号为 (i - 1) / 2。

b. 一个编号为 i 的节点，其左孩子的节点编号为 2 * i + 1 (2 * i + 1 < n，n为堆中总的节点个数，如果 2 * i + 1 > n，则无左孩子)，右孩子的节点编号为 2 * i + 2 (2 * i + 2 < n)。

这个性质在实现堆的时候特别重要，因为这个性质可以用来计算一个节点的父亲节点下标和孩子节点的下标。

由于堆其底层结构是数组，所以其结构就向顺序表一样：

//定义int为堆中数据的数据类型
typedef int HPDataType;
//堆的结构 -- 实际上就是顺序表的结构，只不过换了名字
typedef struct Heap
{
  HPDataType* arr;//存放堆中数据的数组
  int size;//堆中有效数据的个数
  int capacity;//数组的容量
}Heap;

重点四  堆的实现

3）堆的实现

关于堆共有9个操作，包括初始化堆、销毁堆、堆数据的插入、取堆顶元素、删除堆顶元素、判空、求有效元素的个数以及向上调整算法和向下调整算法，其中向上调整算法和向下调整算法是重点，需要多次理解。

（1）堆的初始化、销毁、求有效元素的个数、判空

这几个操作与顺序表相关操作的实现相同，初始化就是令 arr 指向 NULL，size 和 capacity 初始化为0；销毁就是释放 arr 动态开辟的空间，然后将 size 和 capacity 置成0；求有效元素的个数只要返回 size 就可以了；判空只需判断 size 为不为 0 就可以了。

（2）向上调整算法

向上调整算法是指在一个数组内的数据已经是堆的时候，在数组尾部插入一个数据，将此数据向上调整，使之重新变成一个堆，如在一个堆中插入19（红色的19为新插入的19）：

通过向上调算法会变成如下一个堆：
接下来我们就来讲解一下向上调整算法。

首先我们定义新插入的节点的编号为 child ，然后定义 parent 为其父亲的编号，由上面堆的性质可知，parent = (child - 1) / 2，然后我们将编号为 child 和 parent 节点的值进行比较，如果 child 节点的值大于（小根堆为小于） parent 节点的值，那我们就交换 child 节点和 parent 节点的值，然后 child = parent，parent = (child - 1) / 2，继续将 child 向上调整，直到 child 节点的值小于（小根堆为大于）或者 child 到达了根（child == 0）无法向上调整为止。该过程如图所示：

接下来我们来看一下向上调整算法的时间复杂度，为了简化运算，我们将此处的完全二叉树看作满二叉树来看待（多几个节点不影响总体时间复杂度）：

假设堆的高度为 h，则：

第1层有 $2^{0}$ 个节点，需要向上移动 0 层；

第2层有 $2^{1}$ 个节点，需要向上移动 1 层；

第3层有 $2^{2}$ 个节点，需要向上移动 2 层；

........

第h层有 $2^{h-1}$ 个节点，需要向上移动 h-1 层；

所以总移动次数为：T(h) = 0 * $2^{0}$ + 1 * $2^{1}$ + 2 * $2^{2}$ +.... + (h - 1) * $2^{h-1}$ (1) ; 2T(h) = 0 * $2^{1}$ + 1 * $2^{2}$ + 2 * $2^{3}$ +.... + (h - 1) * $2^{h}$ (2) ;

用 (2) - (1) ，得：

T(h) = $2^{h}$ * (h - 1) - ( $2^{1}$ + $2^{2}$ + .... + $2^{h-1}$ ) ==> T(h) = $2^{h}$ * (h - 1) - $2^{h}$ + 2

又由二叉树性质可知： h = $\log_{2}(n + 1)$ ，故：
T(n) = (n + 1) * ( $\log_{2}(n + 1)$ - 1) - (n + 1) + 2 ==> T(n) = O(nlogn)

（3）向下调整算法

向下调整算法是指某个节点的存在使这个树不是一个堆，且在其左右子树是堆的前提下，将该节点向下调整，使之重新变成一个堆，如下面这个堆将堆顶的 5 向下调整：

向下调整算法之后：
接下里我们就来讲解一下向下调整算法。

首先我们定义要向下调整的节点为 parent 节点，然后通过 child = parent * 2 + 1，计算出 child 节点，如果 parent 节点的值小于 child 节点的值（小根堆为大于），那么就让交换 parent 节点的值和 child 节点的值，让 parent = child，child = 2 * parent + 1 继续向下调整，直到 parent 节点的值大于 child 节点的值（小根堆为小于）或者 child 超过节点个数为止。

但是，向下调整算法有一个细节问题，就是 parent 既有左孩子又有右孩子，要重新调整为一个堆就需要让 parent 和更大的（小根堆为更小的）child 交换，而 child = 2 * parent + 1 是计算的左孩子，所以在交换 parent 和 child 的值之前，要先判断 child + 1 节点的值是否大于 child 节点的值，如果大于（小根堆是小于）,那就让 child++，然后再交换。这里还有一个细节，就是 child + 1 是有可能越界的（也就是 parent 节点没有右孩子），所以还要判断一下 child + 1 是否小于节点个数。

向下调整算法如图所示：

接下来我们来看一下向下调整算法的时间复杂度，同样的，这里看作一棵满二叉树来看待：

假设堆的高度为 h，则：

第1层有 $2^{0}$ 个节点，需要向下移动 h - 1 层；

第2层有 $2^{1}$ 个节点，需要向下移动 h - 2 层；

第3层有 $2^{2}$ 个节点，需要向下移动 h - 3 层；

........

第h层有 $2^{h-1}$ 个节点，需要向下移动 0 层；

所以总移动次数为：T(h) = (h - 1) * $2^{0}$ + (h - 2) * $2^{1}$ + (h - 3) * $2^{2}$ + .... + $2^{h - 2}$ (1) ; 2T(h) = (h - 1) * $2^{1}$ + (h - 2) * $2^{2}$ + (h - 3) * $2^{3}$ + .... + $2^{h-1}$ (2) ;

用 (2) - (1)，得：

T(h) = 1 - h + $2^{1}$ + $2^{2}$ + $2^{3}$ + .... + $2^{h-1}$ ==> T(h) = 1 - h + $2^{h}$ - 2 ==> T(h) = $2^{h}$ - h - 1

又 h = $\log_{2}(n + 1)$ ，故：

T(n) = n - $\log_{2}(n + 1)$ ==> T(n) = O(n)

（4）堆数据的插入、取堆顶元素、删除堆顶元素

有了向上调整算法和向下调整算法之后，这 3 个操作就很好实现了。

插入数据：根据顺序表里面的插入数据，首先，我们需要先判断数组是否需要扩容；然后在数组尾部插入数据（即下标为 size - 1 的位置），最后将尾部数据向上调整使之重新变成一个堆即可，最后别忘记让 ++size。

取堆顶元素：返回 arr[0] 即可。

删除堆顶元素：之前顺序表里面删除头部元素，都是让 arr 里面的数据向前移动一位，如果采用这个方法删除堆顶元素的话，不仅时间复杂度为 O(n)，而且最重要的是整个堆的结构都会被打乱，所以这个方法不可行。这里采用先将 arr 数组头部元素和尾部元素进行交换，然后 --size，再让 0 下标的元素向下调整，使之重新变成一个堆，这样就达到了删除堆顶元素的效果。

4）代码

Heap.h文件：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

//初始化堆
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HPDataType x);
//删除堆顶元素
void HPPop(HP* php);
//取堆顶元素
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);
//求堆中元素个数
int HPSize(HP* php);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);

Heap.c文件：

#include"Heap.h"

//初始化堆
void HPInit(HP* php)
{
  assert(php);
  php->arr = NULL;
  php->size = php->capacity = 0;
}

//堆的销毁
void HPDestroy(HP* php)
{
  assert(php);
  //php->arr必须是动态开辟的空间才能释放
  if (php->arr)
    free(php->arr);

  php->arr = NULL;
  php->size = php->capacity = 0;
}

//交换函数
void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //这里建小根堆，建大根堆的话只需要让 > 变成 <
    if (arr[child] < arr[parent])
    {
      Swap(&arr[child], &arr[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 : 2 * php->capacity;
    HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType)*newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail！\n");
      exit(1);
    }
    php->arr = tmp;
    php->capacity = newcapacity;
  }
  php->arr[php->size] = x;
  //插入数据之后需要让size位置数据向上调整，保证其还是一个堆
  AdjustUp(php->arr, php->size);
  php->size++;
}

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
  //这里还是建小堆，建大堆只要让判断判断条件里面的大小于号互反就可以
  //左孩子序号
  int child = 2 * parent + 1;
  while (child < n)
  {
    //如果右孩子小于左孩子，就让child走到右孩子
    if (arr[child+1] < arr[child] && child + 1 < n)//右孩子不能越界
    {
      child++;
    }
    if (arr[parent] > arr[child])
    {
      Swap(&arr[parent], &arr[child]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

//判空
bool HPEmpty(HP* php)
{
  assert(php);
  //只要size为0，就为空
  return php->size == 0;
}
 
//删除堆顶元素
void HPPop(HP* php)
{
  //先判断堆为不为空
  assert(!HPEmpty(php));
  //需要先把堆顶元素跟最后一个元素交换位置
  Swap(&php->arr[0], &php->arr[php->size-1]);
  //然后让元素个数减一
  php->size--;
  //再让堆顶元素向下调整，使之成为一个新的堆
  AdjustDown(php->arr, 0, php->size);
}

//取堆顶元素
HPDataType HPTop(HP* php)
{
  //先判断堆为不为空
  assert(!HPEmpty(php));
  //直接返回堆顶元素
  return php->arr[0];
}

//求堆中元素个数
int HPSize(HP* php)
{
  assert(php);
  return php->size;
}

test.c文件：

void Heap_Test()
{
    HP hp;
    HPInit(&hp);
    int a[] = { 18, 12, 15, 18, 7, 11, 8, 20, 1, 13, 2 };

    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        HPPush(&hp, a[i]);
    }
    while (!HPEmpty(&hp))
    {
        int top = HPTop(&hp);
        HPPop(&hp);
        printf(" ");
        printf("%d\n", HPSize(&hp));
    }

    printf("\n");
}

int main()
{
    Heap_Test();

    return 0;
}