初阶数据结构】——写了将近 5 万字，终于把二叉树初阶的内容讲清楚了-阿里云开发者社区

文章目录

前言

1. 树的概念及结构

1.1 树的概念

1.2 树与非树

1.3 树的相关概念

1.4 树的表示

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

2. 二叉树概念及结构

2.1 概念

2.2 现实中的二叉树

2.3 特殊的二叉树

2.3.1 满二叉树

2.3.1 完全二叉树

2.4 二叉树的性质

2.5 二叉树的存储结构

2.5.1 顺序存储

2.5.2 链式存储

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

3.1 二叉树的顺序结构

3.2 堆的概念及结构

堆的性质

孩子结点和父亲结点的下标关系

3.3 堆的实现

3.3.1 堆的向上调整算法

1. 铺垫及其前提

2. 算法讲解及实现

3. 向上调整建堆

3.3.2 堆的向下调整算法

1. 铺垫及其前提

2. 算法讲解及实现

3.3.3 剩余接口实现

3.3.4 堆的构建

1. 向下调整建堆

2. 向下向上调整建堆的时间复杂度

3.为何向下调整建堆更优

3.4 堆的应用

3.4.1 堆排序

3.4.2 TOP-K 问题

4. 堆及其应用对应源码

4.1 heap.h

4.2 heap.c

4.3 test.c

5. 二叉树的链式结构及实现

5.1 二叉树的链式结构

5.2 二叉树的前、中、后序遍历

1. 举例

2. 代码实现（递归方式）

5.3 求二叉树结点个数

5.4 求叶子结点个数

5.5 求二叉树高度/深度

5.6 求第K层结点个数(k>=1)

5.7 查找值为x的结点

5.8 二叉树的创建和销毁

1.创建

2. 销毁

3.代码展示

5.9 二叉树的层序遍历

1. 思路讲解及举例

2. 代码实现

5.10 判断二叉树是否为完全二叉树

1. 思路讲解

2. 代码实现

6. 链式结构相关代码

6.1 Queue.h

6.2 Queue.c

6.3 Test.c (对链式二叉树的各种操作）

前言

我们在前面文章学到的数据结构：顺序表、链表，不管是单链表还是带头双向循环链表，以及后面的栈和队列。

它们呢，其实都属于一类数据结构——线性表。

那从这篇文章开始：

我们将开始学习数据结构中的非线性结构，今天我们先来学习第一种——二叉树

1. 树的概念及结构

那要学习二叉树，我们首先要知道什么是树。

所以我们先来了解一下数据结构中树的概念及结构。

如果不提数据结构，只谈树，相信大家都不陌生，对吧，谁还没见过树啊。

那数据结构中的树，到底是什么东西呢？

我们一起来看一看。

1.1 树的概念

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

现实生活中的树：

数据结构中的树：

有一个特殊的结点，称为根结点，根节点没有前驱结点

除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。

每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。

1.2 树与非树

大家看这3个东西是树吗？

它们不是树。

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

1.3 树的相关概念

下面我们一起来了解一些与树相关的概念：

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的度为6

叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点

非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推

至于结点的层次呢，其实有两种方案，一种是从0开始，即认为根节点的层次为0，另一种是从1开始。

这两种方案呢其实都可以，但在这里建议大家选择从1开始。

为什么呢？

因为如果我们认为根节点的层次是0，那要表示空树就是-1了。

而如果从1开始，那空树的层次就是0，空树是0 是不是好像更符合我们正常的逻辑啊。

当然只是建议，两种都可以。

树的高度或深度：树中节点的最大层次；如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

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

1.4 树的表示

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

我们这里就简单的了解其中最常用的孩子兄弟表示法。

那什么是孩子兄弟表示法呢？

这种表示方法是一种非常巧妙，非常牛的表示方法。

树中每个结点的结构都是一样的，一个数据域和两个指针域。它的两个指针一个指向自己的第一个孩子结点，另一个指针指向与它相邻的第一个兄弟结点。如果没有孩子或兄弟就指向空。

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

这个表示方法牛的地方就在于，就只需要这两个指针，就可以表示你这个结点有任意多个孩子。

🆗，我们来看一个例子：

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

Linux系统的目录结构，其实就是一棵树：

2. 二叉树概念及结构

🆗，那了解了树的概念之后，接下来我们就来看一下二叉树。

那什么是二叉树呢？

2.1 概念

一棵二叉树是结点的一个有限集合，该集合:

或者为空

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

由上图我们可以得出：

二叉树不存在度大于2的结点

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

2.2 现实中的二叉树

我们看两张图片：

图片中的这两棵树其实就是二叉树，可以看成是上下颠倒的二叉树，它们都不存在度大于2的结点。

如果更准确一点的话，应该说它们是满二叉树，就是我们接下来要学习的。

2.3 特殊的二叉树

有两种比较特殊的二叉树：

2.3.1 满二叉树

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

我们来证明一下：

满二叉树每层都是满的，那它每层的结点个数就有这样的关系：

那我们很容易能够看出来，这就是一个等比数列嘛！

所以呢：

如果二叉树总共有k层（即高度为k），那第k层的结点个数就是2^(k-1)个。

那节点的总数就是：

我们根据等比数列的求和公式可以算出来：

结果为：2^k-1个。

大家也可以用错位相减法算也很简单。

那如果一棵满二叉树结点个数为N，假设高度为h，就有这样的关系：

高度为h，所以结点总数就是2^h-1

那么就有2^h-1=N

所以该满二叉树的高度:

2.3.1 完全二叉树

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

这段概念呢说了一大堆，而且也不是很好理解，大家可以不用看。

其实总结一下，可以这样理解二叉树：

二叉树它的前n-1层（结点个数）一定是满的，最后一层可以不满，当然也可以是满的（那此时就是满二叉树了），所以，满二叉树也是一种特殊的完全二叉树。

举个例子：

这就是一棵完全二叉树。

但是，一定要注意⚠：

完全二叉树最后一层的结点从左到右必须是连续的，中间不能间断。

举个栗子：

🆗，那我们接下来再来讨论一下完全二叉树的结点个数：

那满二叉树呢，如果高度确定了，其实它的结点个数就也确定住了。

但是我们说完全二叉树，它的最后一层可以不满，当然也可以是满的。

所以呢，完全二叉树结点个数最多的情况其实就是最后一层也是满的；最少的情况就是最后一层只有一个结点。

注意⚠不要认为是0个，0个的话高度就变了。

因此：

完全二叉树的结点个数应该是一个范围！

那我们就来讨论一下这个范围：

假设一棵完全二叉树高度为h，那它前n-1层的结点个数其实和满二叉树是一样的，都是一个等比数列，公比为2。

那我们其实很容易得出这个范围：

那这个范围我们就得出来了。

2.4 二叉树的性质

接下来我们来看几个二叉树的性质，这些性质在我们做题的过程中可能会用到：

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点。

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是。

前两个结论经过上面的学习，相信不用给大家过多解释了。

对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1

性质还没说完，我们先来看几个题：

根据性质3：度为0的结点个数等于度为2的加1，我们很容易得出答案是B。

这道题根据性质，也很好解：

所以答案是A。

一棵完全二叉树的节点数为531个，那么这棵树的高度为（）

A 11

B 10

C 8

D 12

根据我们前面得出的结论，完全二叉树的结点个数是一个范围：

我们可以把高度代进去，得出范围，看531在那个范围中。

答案是B。

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(n+1) 。
(p s ：log2(n+1)是log以2为底，n+1为对数)
这个结论呢，我们在上面也已经证明过了。

2.5 二叉树的存储结构

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

2.5.1 顺序存储

顺序结构存储就是使用数组来存储。

但是呢：

一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。

而现实中使用中只有堆才会使用数组来存储，关于堆我们马上就会讲到。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.5.2 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

这是二叉树的两种存储结构，大家先了解一下，后面我们还会详细讲解。

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

我们先来学习二叉树的顺序结构及其实现。

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。

而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

接下来我们将重点学习一下堆。

3.2 堆的概念及结构

那什么是堆呢？

堆其实是一棵二叉树，更准确一点说，它是一棵完全二叉树。

堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

那具体的概念是什么呢？

如果有一个关键码的集合K = {k1, k2 ,… , kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足以下条件，则称为堆：

如果该完全二叉树中所有的父亲结点的值均大于等于其孩子结点，则称其为大堆或大根堆。

如果该完全二叉树中所有的父亲结点的值均小于等于其孩子结点，则称其为小堆或小根堆。

注意：

堆只有大堆和小堆。

所以说:

堆是一个一维数组，但是随便给你一个一维数组，它就不一定是堆了，因为必须满足大堆或小堆的特征，才能叫做堆。

堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
堆的逻辑结构是一棵完全二叉树，但是其物理结构，即实际的存储结构是一个一维数组。
其在数组中存储的顺序就是对其做层序遍历的顺序。

🆗，那大家接下来再思考一个问题：

堆是一棵完全二叉树，但是它存储在数组里面，那我们如何找一个结点的孩子或是它的双亲结点呢？

如果是链式存储，我们直接通过它的左右孩子指针就能找到，那顺序存储呢？

其实它们的下标之间是有关系的。

孩子结点和父亲结点的下标关系

双亲结点找孩子：

左孩子：leftchild=parent x 2+1

右孩子：rightchild=parent x 2+2

我们来看一下是不是：

大家可以试一试，是完全正确的。

注意：

如果parent*2 再+1或+2之后超出了下标范围，就证明该结点没有对应的左孩子或右孩子。

那如何通过孩子找双亲结点呢？

不管是左孩子找双亲，还是右孩子找双亲，都满足：

parent=（ child - 1 ）/ 2

我们可以发现，所有结点的左孩子下标都是奇数，右孩子下标都是偶数，但是它们减1除2的结果是一样的（因为C语言中是整除），最终都等于它们双亲结点的下标。

🆗，那接下来我们一起来看一个题：

这个怎么判断呢？

我们说堆虽然物理结构是一个一维数组，但是逻辑上是一个完全二叉树，所以我们只需要将它转化成完全二叉树，然后就可以判断它是不是堆了。

我们判断一下会发现其实A选项就是一个堆。

将A选项的数组转换为完全二叉树：

是不是很容易看出来是一个大堆啊。

所以答案就是A，其它的大家可以自己判断一下。

3.3 堆的实现

接下来我们就一起来用C语言实现一下堆：

常用的接口：

// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

我们这里呢采用顺序结构来实现堆，其实就是用数组来实现，那我们建堆肯定要向数组中插入元素，那我们就可以搞一个动态数组，空间不够可以扩容。

那就需要一个变量来记录数组大小，当然还有容量。

所以，堆的结构我们就可以这样定义：

typedef int HPDataType;
struct heap
{
  HPDataType* arr;
  int size;   //数组大小
  int capacity;  //容量
};

大家看这个结构是不是和我们之前写的顺序表很一样啊。

那我们可以直接把初始化和销毁的函数直接写一下，就和顺序表一样：

//初始化堆
void HeapInit(hp* php)
{
  assert(php);
  php->arr = NULL;
  php->capacity = php->size = 0;
}
//销毁堆
void HeapDestory(hp* php)
{
  assert(php);
  free(php->arr);
  php->arr = NULL;
  php->capacity = php->size = 0;
}

那我们继续。

大家再来思考一下，我们向堆里面插入新数据的时候，可能是任何值，可能大可能小。

但是堆是对数据有要求的，大堆要求所有的父亲结点的值大于它们对应的孩子；小堆要求所有父亲结点小于其孩子。

所以呢，我们向一个堆中插入一些新的数据，插入之后它可能就不是堆了。

那怎么办呢？

那在每次插入新数据之后，我们就要对堆进行检查和调整，确保在加入新的数据之后，它还是一个堆。

那如何调整，这就是我们接下来要学习的：

3.3.1 堆的向上调整算法

1. 铺垫及其前提

那假设现在有这样一个堆：

是一个大堆，那我们现在要插入新数据，并且要保证插入之后的堆还是一个大堆。

首先大家想一下，是不是插入任何一个数据，我们都要对堆进行调整？

🆗，不是的，如果插入之后，它直接就满足当前对应的堆的特征，那就不用调整了。

举个栗子：

就上面那个堆，假设我们现在再插入一个数据12：

大家看需要调整吗？

是不是不用了，原来是个大堆，插入之后还满足是一个大堆。那就不用动了。

那需要调整的情况呢？

现在我们要插入一个100。

🆗，大家看现在这样还是大堆吗？

是不是已经不是大堆了啊。

那要怎么调，大堆需要满足什么条件，任意一个父亲结点都要大于它的孩子，那现在是不是存在不满足条件的树啊。

2. 算法讲解及实现

那我们开始调整：

怎么调？

首先进行向上调整要保证之前的数据必须是一个堆。

然后看插入的数据满足不满足对应的大小关系，不满足就进行交换，直到满足为止。

100这个结点是不是大于它的父亲啊，那大堆中大的才应该做父亲，所以呢，就应该交换100和30这两个结点。

那调整一次就完了吗？

如果调整一次后满足了，那确实就结束了，但是现在是不是还不满足是一个大堆啊，那就要继续调整。

100还是大于它的父亲70：
所以：

这个调整应该是一个循环的过程，那循环什么时候结束呢？

当调整到所有结点都满足大堆或小堆的关系时，或者需要一直调整，当插入的新数据一直交换到成为根结点时就结束了。

当然如果插入的数据直接满足，那一次也不需要调整。

我们把这种从下往上调整的算法叫做向上调整。

大家思考一下，向堆中插入一个元素，时间复杂度是多少？

最坏的情况需要交换多少次，最坏情况就是插入的数据需要一直交换到成为根结点，那就是高度次。

所以应该是log2(N)。

接下来我们就来实现一下向上调整算法：

代码：

//交换
void swap(HPDataType* e1, HPDataType* e2)
{
  HPDataType tmp = *e1;
  *e1 = *e2;
  *e2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{
  assert(arr);
  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;
    }
  }
}

那要是对小堆进行向上调整呢？

很简单，只需要把上面向上调整算法中比较的>换成<就行了。

if (arr[child] < arr[parent])

那我们现在写一下插入数据的函数，插入完直接调用向上调整函数进行调整：

//插入数据，并保证它仍然是一个堆
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->arr, newcapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->arr = tmp;
    php->capacity = newcapacity;
  }
  php->arr[php->size] = x;
  php->size++;
  //向上调整
  AdjustUp(php->arr, php->size - 1);
}

3. 向上调整建堆

那其实我们现在就可以建堆了，怎么建？

直接一个一个进行元素的插入就行了，插入一个调整一次，插入一个调整一次，堆不就建成了。

int main()
{
  int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
  {
    HeapPush(&hp, arr[i]);
  }
  HeapPrint(&hp);
  HeapDestory(&hp);
  return 0;
}

这样一个大堆就建成了。

如果向建成小堆，只需把向上调整算法中的>换成<就行了。

3.3.2 堆的向下调整算法

1. 铺垫及其前提

现在我们已经可以建立一个大堆或小堆了，那大家思考一下，堆这种数据结构有没有什么特别的价值，或者说有什么作用？

可能大家都听说过一种排序叫做堆排序。

🆗，这确实是堆的一个应用。不过除此之外，堆还可以用来解决另外一个问题：

叫做Top-K问题：即在一组数据中找出最大或最小的前K个数据。

那大家思考一下，为什么用堆可以解决TOP-K问题呢？

因为在一个大堆中，堆顶的元素（即根结点）的值一定是最大的，相同道理，小堆的堆顶一定是最小的。

那我们取出堆顶的数据，就取出了这组数据中最大或最小的那个数据了。

但是TOP-K问题不是只取一个最值，我们要取出前K个，也就是说接下来我们要想办法取出次大的数据。

那我们是不是应该把第一次取出来的数据从堆中删除啊。

那现在就有一个新的问题：如果正确的从堆中删除一个数据？

我们现在实现的堆是存放在数组中的，那堆顶的元素是在下标为0的位置的。

我们可不可以用常规的数组头删的方法，直接移动后面的元素覆盖呢？

这样做不太行。

为什么不行？

有两点原因：

首先这样挪动数据效率比较低。

另外，最主要的一点，这样做导致堆原来建立起的关系就乱了。

举个栗子：

这是我们刚才在上面建立好的一个大堆：

大家看，我们这样删除的话，关系是不是就乱了。

我们之前辛辛苦苦建立起来的关系，建立的“族谱”，就被破坏了。

本来呢，49和34两个人说好了，我们要做一辈子的好兄弟，结果呢，你49却想去当34的爸爸，这样可不行啊。

而且，我们看对于当前这个堆来说，删除堆顶元素之后其实就不再是一个大堆了。

所以这种删除的方法就不是很好，那有没有更好一点的呢？

有大佬呢就想出了这样的方法。

说与其向上面那样把整个“家族”的关系都搞乱了，倒不如先做一个小的变动。

怎么搞呢？

先不直接删除，先拿堆中的最后一个“子孙”和堆顶的元素进行一下交换。

为什么这样做呢？

这样交换以后再删除是不是就比较方便了啊。

因为我们要删除的就是堆顶的元素，把它交换到数组的最后一个位置，数组头删不方便，尾删是不是很easy啊，直接size- -就把最大值删除了。

那删除之后是不是就完事了？

不是滴，虽然现在最大值我们已经可以直接删除了，但是删除完我们就可以直接取次大的了吗？

还不行，因为我们刚才把堆中最后一个元素交换到了堆顶，那大堆的最后一个数据，不敢保证是堆中最小的，但也是比较小的吧。

所以呢意思就是虽然把你推上位了，你成功坐到了堆顶的位置，但是，你撑不住啊！！！

因此，还需要进行一些调整。

虽然还是需要我们进行调整，但是：

我们看他现在的结构有一个特点：

就是它的左右子树并没有得到破坏，仍然保持是一个堆。

这也是向下调整算法的一个前提：

左右子树必须都是堆堆，才能调整。

向上和向下调整我们放在一起回忆一下：

向上调整算法的要求原来的数据必须是一个堆；

向下调整算法要求左右子树必须都是堆。

2. 算法讲解及实现

🆗，铺垫了这麽久，接下来我们就来学习一下如何进行向下调整。

我们接着上面的往下看：

现在这个堆是这样一个状态：

我们把18推上去了，但是它撑不住啊！

它没能力坐稳这个位置啊，所以我们要进行调整，使得他还得是一个大堆，这样我们才能继续取下一个次大的值。

如何调整：

其实思路跟向上调整一样，只不过这次我们是从上往下，不符合关系的进行交换，直至使它成为一个新的大堆。

我们开始调整：

18在这里肯定不合适，它比自己的孩子还要小，所以要交换。

和谁交换？

34可以吗，34换到堆顶，它是不是还撑不住啊。

所以我们要选择它的孩子中大的那一个进行交换。

那在这里就是49。

那现在18坐到原来49的位置，现在这个位置怎么样？

🆗，18是不是还是坐不稳啊。

还得进行交换。

选择18的孩子中大的那一个交换：

现在是不是就可以了啊。

我们交换了两次完成了，所以这还是一个循环的过程。

那这个循环的交换过程应该什么时候停止？

是不是当交换到满足大小关系或者一直交换，直到自己成为叶子结点时结束啊。

那接下来就来实现一下代码：

//向下调整
void AdjustDown(HPDataType* arr, int size, int parent)
{
  assert(arr);
  int child = parent * 2 + 1;
  while (child < size)
  {
    //得出较大的那个孩子
    if (child + 1 < size && arr[child + 1] > arr[child])
    {
      child++;
    }
    //如果孩子大于父亲，就交换
    if (arr[parent] < arr[child])
    {
      swap(arr[child], arr[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    //如果小于孩子，调整结束
    else
    {
      break;
    }
  }
}
//删除堆顶元素，并确保删除之后还是一个堆
void HeapPop(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);
}

算法写好了，我们来验证一下好吧：

我们对上面建好的那个堆先删除一下堆顶元素，在打印出来，看看是不是还保持是一个堆。

🆗，没有问题，跟我们画图得出的结果是一样的。

3.3.3 剩余接口实现

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  return php->arr[0];
}
// 堆的数据个数
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
// 堆的判空
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

3.3.4 堆的构建

其实在上面我们已经建立过堆了：

但是上面我建立堆是一个数据一个数据去插入，然后经过调整形成一个堆。

1. 向下调整建堆

但是上面那种方式去建堆其实不是特别好（时间复杂度是N*log2N，我们后面会证明），有些地方会让我们这样去建立一个堆：

就是给我们一个数组，数组的元素可能是任意值，我们需要将这个数组进行一些处理使它变成一个堆。是直接对数组进行操作，而不是像上面那样，将数组中的元素一个一个的插入去建堆。

下面我就来实现一下这个构建堆的方式：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

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

那应该怎么做呢？

🆗，我们知道它的逻辑结构是一棵二叉树，那如果它的左右子树已经是一个堆的话，我们就可以很容易将整棵树调整成一个堆。

怎么调整我们上面是不是已经讲过了：

如果它的左右子树已经满足是一个堆，我们可以利用向下调整算法将它变成一个堆。

那我们给的数组可能是随便给的，它的左右子树有可能都不是堆，那我们要如何处理呢？

也就是说现在不具备左右子树都是堆的条件，那怎么办？

既然没有条件，那我们就创造条件嘛！

先想办法把左右子树变成堆就行了。

我们先将给的数组int arr[] = {27,15,19,18,28,34,65,49,25,37};转换为对应完全二叉树：

那要想让它的左右子树都变成堆，我们可以从最后一个结点开始，向前依次调整。

但是，最后的这几个叶子结点，是不是可以直接略过不用管啊，因为这几个没有孩子结点，你可以把它看成一个大堆，也可以看成小堆。

所以，我们只需从倒数第一个非叶子结点开始，依次向前对每一棵子树进行向下调整将其变为堆，这样在调整前面结点的时候，它们对应的左右子树就已经满足是堆了，一直到将根结点调整完，堆就建好了。

那现在又有一个问题：

我们要从倒数第一个非叶子结点开始往前调，那怎么找到倒数第一个非叶子结点呢？

其实观察一下可以发现，倒数第一个非叶子结点就是最后一个结点的父亲结点。

假设最后一个结点的下标是n-1，那倒数第一个非叶子结点的下标就是(n-1-1)/2 。

那我们接下就来实现一下这个构建堆的算法：

// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size)
{
  assert(php);
  php->arr = (HPDataType*)malloc(sizeof(HPDataType) * size);
  if (php->arr == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  memcpy(php->arr, arr, sizeof(HPDataType) * size);
  php->capacity = php->size = size;
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->arr, size, i);
  }
}

由于我们这里是直接对数组操作，所以我们直接把给的数组使用memcpy拷贝到堆中，然后调整。

那算法写好了，我们来验证一下：

就用上面那个数组，我们现在尝试用该算法将数组直接构建成一个堆。

🆗，一个大堆就构建好了：

2. 向下向上调整建堆的时间复杂度

我们刚才建堆其实是用向下调整的算法建堆的：

给一个数组，把它看成一个完全二叉树，然后从倒数第一个非叶子结点开始往上依次对每个结点进行向下调整，最终构建一个堆。

那接下来，我们来算一下这种建堆方式的时间复杂度：

我们说算一个算法的时间复杂度，我们通常考虑的都是最坏的情况，那向下调整建堆什么样的情况会是最坏的情况呢？

我们调整的对象是什么：

是一个数组，但是我们要把它看作一个完全二叉树去调整，那什么样的完全二叉树需要调整的次数会尽可能多呢？

是不是满的情况啊：

我们知道满二叉树是一种特殊的完全二叉树。

那在是一棵满二叉树的基础上，什么情况下需要调整次数最多？

是不是所有非叶子结点和它的孩子结点的大小关系都不满足，都需要交换且需要交换到最后一层才满足大小关系，这时是最坏的情况。

所以就是这样的：

那总次数怎么算，其实就是前h-1层的结点个数乘以它们要交换的层数。

因此：向下调整建堆的时间复杂度为O(N)。

🆗，那趁热打铁，我们再来算一下向上调整建堆的时间复杂度：

那总次数就是第2到最后一层所有结点需要调整的次数之和。

详细计算过程就不写了，最后得出的时间复杂度是N*log2N。

所以说，向上调整建堆没有没有向下调整建堆优。

3.为何向下调整建堆更优

那我们来分析一下，为什么向下建堆更优更快呢？

大家看，向下建堆我们是从倒数第一个非叶子结点开始往上调整，最后一层的结点我们是不是不用管啊，那如果在像这种是满二叉树的最坏情况下:

结点总数是2^h-1个

但最后一层就有2^(h-1)个，占了一半都有了。

而且，越靠下层，结点个数越多的，调整的次数越少，因为是向下，上面的调整次数虽然变多了，但是结点个数就很少了。

那向上调整正好反过来了，那效率可不就低了嘛。

所以呢：

今后建堆，我们建议大家选择向下调整算法来建堆。

3.4 堆的应用

我们已经学完堆了，那堆有啥应用呢？

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆

升序：建大堆

降序：建小堆

利用堆删除思想来进行排序

这就是堆排序的两个步骤。

首先，简单解释一下为啥升序建大堆，降序建小堆：

拿升序来说，其实建小堆也不是不能搞，只是不太好。

为什么呢？

现在这有一个数组，如果升序，建小堆可以首先可以得到最小的数据，🆗，就是堆顶元素。

那像得到下一个次小的怎么办，把第一个删除了，重新把剩余元素建堆？

那把第一个删除了，往哪保存啊。

再开新空间？再搞个数组保存？

也可以，但它的空间复杂度就是O(N)了。

再一个，删除之后，像选出次大的，我们是不是还要重新建堆啊，而且把第一个删除之后原来堆里的关系也就全乱了。

那建堆的时间复杂度是O(N)，还是向下调整建堆比较优的。而且这样搞我们建一次堆才能选出来一个数，如果一次选一个数我们直接遍历也能搞定，没必要建堆了，反而麻烦了。

那其实降序也是这样。

所以好的做法是什么呢？

我们就换一下：升序我们就建大堆，降序建小堆。

好的，那我们接下来就还以升序为例，给大家讲一下完整的一个堆排序的过程：

假设我们现在要对这样一组数据进行堆排序：

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

堆排序呢，我们只需给数组和元素个数就行了：

  int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
  HeapSort(arr, sizeof(arr) / sizeof(arr[0]));

接下来我们就来实现一下HeapSort函数：

首先第一步建堆（注意这里是直接将数组改变成堆），升序我们建大堆

选择向下调整建堆更优：

void HeapSort(int* arr, int n)
{
  //建堆：升序大堆，降序小堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
}

堆建好了，下一步是利用堆删除思想来进行排序，什么意思呢？解释一下：

将上面的数组建成大堆应该是这样的：

那现在堆顶的数据就是最大的，现在想排升序，怎么搞？

什么叫利用堆删除的思想呢？

🆗，现在堆顶数据是最大的，我们将堆顶数据与最后一个交换：

交换之后怎么办，最大值已经处在最终应该待的位置了，那最后一个数我们就不用管了，也不用开新空间去保存它。

下次调整数据个数我们传n-1就行了：

AdjustDown(arr, n-1, i);

接下来只需对前n-1个数进行调整，还需要重新建堆吗？

是不是只需要进行一个向下调整就OK了啊。因为此时对于前n-1个数组成的这个完全二叉树来说，它的左右子树都是堆，那我们就可以用向下调整算法，调整之后就是前n-1个数建成的堆了，就能拿到次大的数即此时堆顶的数据。

依次循环往复，什么时候结束？

当堆中只剩一个数据时结束，这时就排好了。

为什么这种方法更好呢？

之前那种方法我们除了要保存删除的数据之外，每次选一个数就要重新建一次堆，效率很低。

但是这种方法，我们不需要开新空间，而且每次选一个数只需进行一次向下调整即可，向下调整最多只需调整高度次，时间复杂度为log2(N)，就快了不少。

所以说，这才是真正的堆排嘛！

🆗，那思路理清了，接下来来写代码：

//堆排序
void HeapSort(int* arr, int n)
{
  //建堆：升序大堆，降序小堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
  int count = n - 1;
  while (count > 0)
  {
    swap(&arr[0], &arr[count]);
    AdjustDown(arr, count, 0);
    count--;
  }
}

堆排序就实现好了。

简单补充一下大家可能有疑惑的地方：

上面不是说堆中只有一个数据就该结束了嘛，是的，只有一个的话其它的元素都排好了，那最后这一个自然也就在正确位置了。

那为啥循环结束条件是：while (count > 0)呢？

因为调整之后还没完，还要等下一轮循环进去之后交换完它们的位置才是正确的。

当只剩两个数据count=2时，调整完，count- -变成1，再次进入循环，先交换，将较大的那个换到第二个位置，那这时其实已经排好序了，不过接着下来有调整一次，不过这个没关系，只有一个数据，调不调都一样，然后count- - 变成0，循环结束。

在这里我们拿升序给大家举例了，那其实降序也是一样的，换成小堆就行了。

堆排序的时间复杂度时O（N*log2N)

大家可以算一算。

最后，写好了那我们来测试一下：

没有问题。

3.4.2 TOP-K 问题

其实在上面我们已经提到过TOP-K问题了，再来回顾一下：

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序。

那其实用我们这篇文章前面所学的东西也能解决TIOP-k问题：

加入现在要在N个数中找出最大的前K个，怎么做？

建立一个N个数的大堆，pop（删除堆顶元素）K次，依次取堆顶数据。

如果N比较小的情况下，我们确实可以这样搞，而且效率也不算特别差。

但是：

不管是排序也好，还是用刚才介绍的这种方法，都会面临一个问题：

上面提到top-k问题一般数据量都比较大。

如果数据量非常大，排序或者将所有数据建堆就不太可取了(可能数据都不能一下子全部加载到内存中)。

比如现在有100亿个整数，换算一下差不多40G，电脑内存一般情况都放不下，除非搞文件里放到磁盘上。

那这时前面提到的方法就不行了。

所以下面我们提供一个新思路：

用数据集合中前K个元素来建堆

取前k个最大的元素，则建小堆

取前k个最小的元素，则建大堆

用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素，然后向下调整，最终我们想要的最大或最小的K个数据，就在这个K个数的堆中

🆗，那为什么这么做就能取出TOP-k的数据呢？简单解释一下：

我们以取前K个最大的数据为例。

那我们要以前K个数据建小堆，然后拿后面的数据依次和堆顶数据进行比较，那小堆的话堆顶的数最小的，后面比较大的数就会替换堆顶数据，然后调整之后这些大的数据还是跑到了堆的下面，所以即使先遇到了最大的数据，也不会堵在堆顶使得其它次大的数据进不来，因为大的总是在下面，这样一直调整一直交换，最后这个堆中保留的就是最大的k个数。

那我们来算一下该算法的时间和空间复杂度：

时间复杂度：

首先k个数建堆，然后假设后面每个数比较都要替换和进行向下调整，那就是k+(N- k ) x log2K，那数据很多的情况下，k相对于N就很小了。

所以可以认为时间复杂度是O(N*log2K）。

空间复杂度：

那就是O(K)，我们只创建了一个k个数的堆嘛。

那我们接下来就举个栗子，实现一下这个算法：

这里我们就不搞特别多的数据，放在文件里搞了，只是给大家演示一下，重点还是让大家理解一下这个过程。

我们这里就给一个数组模拟一下这个过程：

int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};

搞一个数组，随便给一些值，现在我们找出最大的5个。

首先第一步，找大的值，应该建小堆：

我们之前向下调整是建大堆的，建小堆的话把大于小于号改变一下就行了。

//前5个数建小堆
  int minHeap[5];
  for (int i = 0; i < k; i++)
  {
    minHeap[i] = arr[i];
  }
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(minHeap, k, i);
  }

接着第二步：

拿剩余元素依次与堆顶数据进行比较，大于堆顶数据则替换，然后向下调整。

for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
  {
    if (arr[j] > minHeap[0])
    {
      minHeap[0] = arr[j];
      AdjustDown(minHeap, k, 0);
    }
  }

两个步骤，就完成了：

void test_topk()
{
  int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};
  //找出最大的5个
  //前5个数建小堆
  int k = 5;
  int minHeap[5];
  for (int i = 0; i < k; i++)
  {
    minHeap[i] = arr[i];
  }
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(minHeap, k, i);
  }
  for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
  {
    if (arr[j] > minHeap[0])
    {
      minHeap[0] = arr[j];
      AdjustDown(minHeap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minHeap[i]);
  }
  printf("\n");
}

验证一下：

🆗，最大的前5个就出来了。

不过我们测试的数据比较少，其实数据量大也是一样的逻辑，只不过比较和调整的次数多一点罢了。

4. 堆及其应用对应源码

4.1 heap.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef int HPDataType;
typedef struct heap
{
  HPDataType* arr;
  int size;   //数组大小
  int capacity;  //容量
}HP;
// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size);
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//打印
void HeapPrint(HP* php);
//向上调整
void AdjustUp(HPDataType* arr, int child);
//插入数据，并保证它仍然是一个堆
void HeapPush(HP* php, HPDataType x);
//向下调整
void AdjustDown(HPDataType* arr, int size, int parent);
//删除堆顶元素，并确保删除之后还是一个堆
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
int HeapSize(HP* php);
// 堆的判空
bool HeapEmpty(HP* php);
void swap(HPDataType* e1, HPDataType* e2);

4.2 heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"
// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size)
{
  assert(php);
  php->arr = (HPDataType*)malloc(sizeof(HPDataType) * size);
  if (php->arr == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  memcpy(php->arr, arr, sizeof(HPDataType) * size);
  php->capacity = php->size = size;
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->arr, size, i);
  }
}
//初始化堆
void HeapInit(HP* php)
{
  assert(php);
  php->arr = NULL;
  php->capacity = php->size = 0;
}
//销毁堆
void HeapDestory(HP* php)
{
  assert(php);
  free(php->arr);
  php->arr = NULL;
  php->capacity = php->size = 0;
}
//交换
void swap(HPDataType* e1, HPDataType* e2)
{
  HPDataType tmp = *e1;
  *e1 = *e2;
  *e2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{
  assert(arr);
  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 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->arr, newcapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->arr = tmp;
    php->capacity = newcapacity;
  }
  php->arr[php->size] = x;
  php->size++;
  //调整
  AdjustUp(php->arr, php->size - 1);
}
//打印
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->arr[i]);
  }
  printf("\n");
}
向下调整（大堆）
//void AdjustDown(HPDataType* arr, int size, int parent)
//{
//  assert(arr);
//  int child = parent * 2 + 1;
//  //没有右孩子，说明是个叶子，循环结束
//  while (child < size)
//  {
//    //得出较大的那个孩子，有可能有右孩子，但没有左孩子
//    //所以加上child + 1 < size
//    if (child + 1 < size && arr[child + 1] > arr[child])
//    {
//      child++;
//    }
//    //如果孩子大于父亲，就交换
//    if (arr[parent] < arr[child])
//    {
//      swap(&arr[child], &arr[parent]);
//      parent = child;
//      child = parent * 2 + 1;
//    }
//    //如果小于孩子，调整结束
//    else
//    {
//      break;
//    }
//  }
//}
//向下调整（小堆）
void AdjustDown(HPDataType* arr, int size, int parent)
{
  assert(arr);
  int child = parent * 2 + 1;
  //没有右孩子，说明是个叶子，循环结束
  while (child < size)
  {
    //得出较大的那个孩子，有可能有右孩子，但没有左孩子
    //所以加上child + 1 < size
    if (child + 1 < size && arr[child + 1] < arr[child])
    {
      child++;
    }
    //如果孩子小于父亲，就交换
    if (arr[parent] > arr[child])
    {
      swap(&arr[child], &arr[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    //如果小于孩子，调整结束
    else
    {
      break;
    }
  }
}
//删除堆顶元素，并确保删除之后还是一个堆
void HeapPop(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);
}
// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  return php->arr[0];
}
// 堆的数据个数
int 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
#include "heap.h"
void test1()
{
  int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
  {
    HeapPush(&hp, arr[i]);
  }
  HeapPrint(&hp);
  HeapPop(&hp);
  HeapPrint(&hp);
  HeapDestory(&hp);
}
void test2()
{
  int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
  HP hp;
  HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0]));
  HeapPrint(&hp);
  HeapDestory(&hp);
}
//堆排序
void HeapSort(int* arr, int n)
{
  //建堆：升序大堆，降序小堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
  int count = n - 1;
  while (count > 0)
  {
    swap(&arr[0], &arr[count]);
    AdjustDown(arr, count, 0);
    count--;
  }
}
void testHeapSort()
{
  int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
  HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
  {
    printf("%d ", arr[i]);
  }
}
void test_topk()
{
  int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};
  //找出最大的5个
  //前5个数建小堆
  int k = 5;
  int minHeap[5];
  for (int i = 0; i < k; i++)
  {
    minHeap[i] = arr[i];
  }
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(minHeap, k, i);
  }
  for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
  {
    if (arr[j] > minHeap[0])
    {
      minHeap[0] = arr[j];
      AdjustDown(minHeap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minHeap[i]);
  }
  printf("\n");
}
int main()
{
  //test1();
  //test2();
  //testHeapSort();
  test_topk();
  return 0;
}

5. 二叉树的链式结构及实现

5.1 二叉树的链式结构

首先再回顾下二叉树的概念，二叉树是：

一棵二叉树是结点的一个有限集合，该集合:

或者为空

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

每个结点，只要不为空，就可以被分为根，左子树，右子树，因此，二叉树是递归定义的。

上面呢我们其实已经了解过二叉树的链式存储了，我们在一起来回忆一下：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

然后我们来学习一下二叉树的遍历：

二叉树遍历(Traversal)是按照某种特定的规则，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

5.2 二叉树的前、中、后序遍历

首先我们来学习二叉树的前、中、后序遍历。

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前，即根，左子树，右子树。

中序遍历(Inorder Traversal ) ——访问根结点的操作发生在遍历其左右子树中间，即左子树，根，右子树。

后序遍历(Postorder Traversal ) ——访问根结点的操作发生在遍历其左右子树之后，即左子树，右子树，根。

1. 举例

下面我们举个栗子来帮助大家理解：

来看这棵二叉树：

首先按照二叉树的概念可以将它分为3个部分：

然后它的左右子树还可以再分：

每棵子树都可以被分为根、左子树、右子树，一直分，一直分，直至被分成空（NULL）才停止。

那在遍历时也是一样，每棵子树都要按照相同的规则取遍历它的根，左子树和右子树，除非它是空。

下面我将对他进行前中后三种遍历操作：

首先看前序遍历（根、左子树、右子树）：

大家对照图，跟着我的思路走。

首先访问根是1：

然后1的左子树2，对左子树2同样先访问根

1 2

然后2的左子树3，同样先根

1 2 3

3的根完了是左子树，左子树是空：

1 2 3 NULL

，然后右子树，也是空：

1 2 3 NULL NULL

现在3整个访问完了，相当于2的左子树完了，然后是2的右子树，也是空：

1 2 3 NULL NULL NULL

现在2整个访问完了，相当于1的左子树完了，然后是1的右子树4，同样先根：

1 2 3 NULL NULL NULL 4

然后4的左子树5，同样先根：

1 2 3 NULL NULL NULL 4 5

根之后访问5的左子树，然后右子树，都是空：

1 2 3 NULL NULL NULL 4 5 NULL NULL

5整个访问完了，相当于4的左子树访问完了，然后是4的右子树6，照样先根：

1 2 3 NULL NULL NULL 4 5 NULL NULL 6

然后是6的左子树，然后右子树，都是空：

1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

当然有时候为空的话我们可以省略，那就是这样：

1 2 3 4 5 6

然后是中序和后序：

中序后序我就不像上面那样详细解释了，相信如果大家仔细把上面前序理解透了，中序和后序就没啥问题了：

中序（左子树、根、右子树）：

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

后序（左子树、右子树、根）：

NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

大家仔细思考写一写，然后对照一下。

2. 代码实现（递归方式）

那如果现在给我们一棵二叉树，我们要对它进行前中后序遍历，代码怎么写？

因为二叉树是递归定义的，所以，用递归来实现也是非常好的。

我们还来参照这棵二叉树，完成代码：

但是我们的代码写出来是对任意一棵二叉树都成立的。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType val;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

先来看先序遍历：

首先我们要知道空树也是一棵二叉树，如果上来拿到的就是一棵空树，那就直接return，当然这还包含了另一种情况，就是对一棵二叉树的左右子树一直分，一直分，直到分成不可再分的空（NULL）也要结束了。

这两种情况我们可以放在一起，为空时我们可以不做处理，也可以打印一下“NULL”：

if (root == NULL)
  {
    printf("NULL ");
    return;
  }

然后就是不为空的情况了：

不为空的话前序遍历那就先访问根，我们就先打印一下根结点的值：

printf("%d ", root->val);

根之后是左子树，那左子树同样可以看成一棵二叉树分成根，左子树右子树。

那就可以看作与原问题规模类似的子问题，那就可以用递归了：

PrevOrder(root->left);

那接下来右子树也是同样的道理：

PrevOrder(root->right);

那就写好了：

//前序遍历
void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->val);
  PrevOrder(root->left);
  PrevOrder(root->right);
}

代码看起来很简单，但是：

大家对这个递归过程可能还不是特别理解，下面画一下递归展开图帮助大家理解该递归的整个过程：

图中的代码实现跟我们的写法稍有差异，但其实是一样的。

当然，最好的方法还是大家自己去画一遍这个递归展开图，才能理解的更透彻。

那写好了我们来测试一下吧：

测试的话我们要先创建二叉树：

由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

我们就先手动创建一下上面那棵二叉树：

首先搞一个创建结点的函数：

BTNode* CreateBTNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->val = x;
  node->left = node->right = NULL;
  return node;
}

然后我们创建对应的结点并按照上面的关系链接，并调用前序遍历函数

int main() 
{
  BTNode* n1 = CreateBTNode(1);
  BTNode* n2 = CreateBTNode(2);
  BTNode* n3 = CreateBTNode(3);
  BTNode* n4 = CreateBTNode(4);
  BTNode* n5 = CreateBTNode(5);
  BTNode* n6 = CreateBTNode(6);
  n1->left = n2;
  n2->left = n3;
  n1->right = n4;
  n4->right = n6;
  n4->left = n5;
  PrevOrder(n1);
  return 0;
}

运行代码看看结果是否正确：

大家可以翻上去看一下，跟我们上面的结果是一样的。

🆗，那把前序搞明白了，后序和中序是不是就soeasy啊，变换一下代码的位置就搞定了，只是打印的顺序问题

//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->val);
  InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->val);
}

三个一块验证一下：

都是正确的。

除了这3种遍历方式，还有一个层序遍历，这个我们放在后面一点再讲，它是非递归的。

5.3 求二叉树结点个数

接下来我们来实现一个函数，要求它能够求出一棵二叉树的结点个数。

怎么搞？

好像不难，我们还是去遍历一遍二叉树（当然这里选择哪种遍历方式都可以），搞一个计数器，遍历到不是空的结点计数器++就行了嘛。

我们来实现一下：

//统计结点个数
int TreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  int size = 0;
  size++;
  TreeSize(root->left);
  TreeSize(root->right);
  return size;
}

代码就写好了，但这样写对不对呢？

其实简单分析一下就会发现这样写是会有问题的。

啥问题呢？

我们这里还是用了递归的方法，而size是我们定义在函数内部的一个局部变量，每次递归，都会建立新的函数栈帧，那size自然也会随着每次递归在新的函数栈帧中重新创建。

所以，每次递归，size都会重新定义，而每次++的也不是同一个size。

我们可以验证一下：

🆗，确实是错误的，有6个结点，但答案是1。

那如何解决这个问题呢？

我们可能会想到用全局变量或static修饰局部变量size（关于static的作用如果大家遗忘了或者不太清楚可以看之前写的这篇文章）

链接: link

size被static修饰之后，就不会再存储到栈区了，而是会存储在静态区，静态局部变量的初值是在编译期间就指定的，所以运行期间每次递归都不会在重新创建变量size了，这样我们每次++的就是同一个size了。

那这下是不是就行了呢？

哦豁，好像确实可以了。

但是，还会有一个问题：

我们多调用几次Tree Size函数：

欸，为什么会这样？

因为size被static修饰后，其生命周期就是整个程序的生命周期，等到程序结束它才会被销毁，用全部变量也是这样。

所以，第一次调用结果没啥问题，后面再去调用，size也不会重新定义，因此结果才会越来越大。

而且static修饰的话中间程序不结束我们还没有办法给size重新赋初值。

如果确实想这样写的话，那就使用把size定义成全局变量，每次调用之前，将size手动置成0。

不过也不太好。

那有没有更优一点的方法来解决这个问题呢？

🆗，既然用static修饰也不行，用全局变量也不太好，那我们干脆就不用计数器了。

那怎么弄？

直接算啊，如果为空就返回0 ，不为空至少有一个结点，那就返回1+左子树的结点个数+右子树的结点个数：

//统计结点个数
int TreeSize(BTNode* root)
{
  return root == NULL ? 0 :
    1 + TreeSize(root->left) + TreeSize(root->right);
}

一个三目运算符搞定！

来验证一下：

5.4 求叶子结点个数

接下来我们再来看一个问题，如何求一棵二叉树的叶子结点的个数？

首先回顾一下，啥是叶子结点：

那在链式结构中，就是它的左指针和右指针都指向空的结点。

比如在这棵二叉树中：

3，5，6就是3个叶子结点。

那思路是什么样的呢？

也很好办：

如果遇到空，就返回0；不是空，那就判断它是不是叶子结点，是的话返回一个1，不是的话，就返回它的左子树的叶子结点个数+右子树的叶子结点个数。

实现一下代码：

//统计叶子结点个数
int TreeLeafSize(BTNode* root)
{
  if (root)
  {
    if (root->left == NULL && root->right == NULL)
      return 1;
    return TreeLeafSize(root->left) +
      TreeLeafSize(root->right);
  }
  return 0;
}

验证一下：

是3个。

5.5 求二叉树高度/深度

我们接着往下看，如何求一棵二叉树的高度呢？

我们来讲一下思路：

首先给大家明确一下，这里我们认为空树高度为0（即认为根结点层次为1）。

那怎么搞呢？

如果是空树，就返回0；

如果不是空树，返回其左右子树高度中的最大值再+1（即加上当前根结点所处的这一层的1个高度）。

好像也不难，我们来实现一下代码：

//求二叉树的高度
int TreeHeight(BTNode* root)
{
  if (root)
  {
    return
      TreeHeight(root->left) > TreeHeight(root->right) ?
      TreeHeight(root->left)+1 : TreeHeight(root->right)+1;
  }
  return 0;
}

写好了，测试一下，就来计算上面那棵树的高度：

确实是3。

代码逻辑确实没什么问题，也能正确计算出高度。

但是：

上面那种写法非常不好，看起来很简洁，很省事，但却导致计算效率大大降低。

为什么呢，我们来分析一下：

我们用了一个3目操作符，看起来很简洁。

但是问题出在哪里？

我们前面计算了左右子树的高度，但我们比较完没有保存，后面确定该表达式的最终结果时，又重新进行了计算。

大家可能会觉得这样的话不就算两遍而已，浪费时间不过比原来多一倍罢了。

🆗，我刚开始也是这样想的，但是问题远比你想象的严重很多，这个我用文字不好给大家描述清楚，大家可以自己尝试画一画递归展开图或者调试观察，这样写其实会造成大量大量的重复计算。

所以这样写真的很不好！

我们稍微改进一下，把前面算出来的值保存一下，就会好很多很多很多的。

//求二叉树的高度
int TreeHeight(BTNode* root)
{
  if (root)
  {
    int LeftHeight = TreeHeight(root->left);
    int RightHeight = TreeHeight(root->right);
    return
      LeftHeight > RightHeight ?
      LeftHeight + 1 : RightHeight + 1;
  }
  return 0;
}

5.6 求第K层结点个数(k>=1)

再来，如何求一棵二叉树第K层的结点个数？

这个问题呢，如果大家第一次见，可能不太好想。

接下来我们讲一下思路：

还是分治思想：

首先如果是空树，不管是求第几层，都是0；

不为空的情况，如果k等于1，那不为空的二叉树，第一层肯定是1个结点，返回1；

如果K大于1，就返回相对于其左子树和右子树的第K-1层的结点个数。

思路清楚了，我们来实现代码：

// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{
  if (root)
  {
    if (k == 1)
      return 1;
    return TreeLevelKSize(root->left, k - 1)
    + TreeLevelKSize(root->right, k - 1);
  }
  return 0;
}

验证一下，第2层是2个结点：

5.7 查找值为x的结点

接着再来看一个问题：如何在一棵二叉树中查找值为X的结点，返回其地址？

假如现在我们要在这棵二叉树中查找值为5的结点。

其实也很简单：

跟我们之前在链表中查找一个元素是一样的思路嘛。

这不过这里呢，我们还是用递归去搞。

怎么办？

如果这棵树不为空，那先判断根结点的值是不是等于我们要找的结点的值，等于的话，直接返回根结点地址；

如果根结点不是，那就判断左右子树能不能找到，左子树找不到就接着在右子树找；

左右子树都找不到，那就找不到了，返回NULL。

当然，上面是非空树的情况，如果是空树，那就不用找了，直接返回NULL。

接下来实现一下代码：

// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
  if (root)
  {
    if (root->val == x)
      return root;
    BTNode* ret1 = TreeFind(root->left, x);
    if (ret1)
      return ret1;
    BTNode* ret2 = TreeFind(root->right, x);
    if (ret2)
      return ret2;
    return NULL;
  }
  return NULL;
}

看一下对不对：

没问题。

5.8 二叉树的创建和销毁

1.创建

我们先来看一个题链接: link

这道题呢，给我们一个二叉树的前序遍历字符串，要求我们重构这棵二叉树，并对重构之后的二叉树进行中序遍历。

怎么做呢？

既然给我们的是前序遍历的字符串，那我们就遍历这串字符串，再以前序遍历的顺序去构建这棵二叉树就行了。

从头遍历给定的字符串，如果不是空，那我们就创建一个结点，结点的值就是对应的字符，然后去递归构建它的左子树，接着是右子树，并把构建好的左右子树的根结点链接在它的左右孩子指针上，如果遍历到字符“#”（根据题意表示空树），直接返回NULL即可。

然后我们实现一下代码：

#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode 
{
    BTDataType val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;
BTNode* CreateBTree(char* arr, int* pi) 
{
    if (arr[*pi] == '#') {
        (*pi)++;
        return  NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    root->val = arr[*pi];
    (*pi)++;
    root->left = CreateBTree(arr, pi);
    root->right = CreateBTree(arr, pi);
    return  root;
}
void InOrder(BTNode* root)
{
    if(root)
    {
        InOrder(root->left);
        printf("%c ",root->val);
        InOrder(root->right);
    }
}
int main() {
    char arr[100];
    scanf("%s", arr);
    int i=0;
    BTNode* root=CreateBTree(arr, &i);
    InOrder(root);
    return  0;
}

🆗，虽然OJ通过了，但是上面的程序还是有一些问题的，我们创建的二叉树没有销毁。

2. 销毁

那我们创建一棵二叉树，所有结点都是我们动态开辟出来的，所以程序结束之前我们肯定要将这些空间给释放掉的，即销毁二叉树，否则是不是就内存泄漏了啊。

那怎么做呢？

其实呢方销毁的法不止一种，但是比较优的方法是啥呢，是后序遍历去销毁这棵二叉树。

为啥后序比较好呢？

后序是最后访问根，也就是说我们先销毁左右子树，那如果用先序或中序，我们左右子树没销毁完就先把根给销毁了，但是我们找左右子树是不是要通过根结点的左右指针去找啊，这样就不太方便了。

那我们来实现代码：

//销毁
void TreeDestory(BTNode* root)
{
  if (root)
  {
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);
  }
}

注意⚠：

这里我们用的是一级指针，传的是指向二叉树根结点的指针，所以销毁完最好将函数外面的root指针置空。

3.代码展示

#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode 
{
    BTDataType val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;
BTNode* CreateBTree(char* arr, int* pi) 
{
    if (arr[*pi] == '#') {
        (*pi)++;
        return  NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    root->val = arr[*pi];
    (*pi)++;
    root->left = CreateBTree(arr, pi);
    root->right = CreateBTree(arr, pi);
    return  root;
}
void InOrder(BTNode* root)
{
    if(root)
    {
        InOrder(root->left);
        printf("%c ",root->val);
        InOrder(root->right);
    }
}
//销毁
void TreeDestory(BTNode* root)
{
  if (root)
  {
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);
  }
}
int main() {
    char arr[100];
    scanf("%s", arr);
    int i=0;
    BTNode* root=CreateBTree(arr, &i);
    InOrder(root);
    TreeDestory(root);
    root=NULL;
    return  0;
}

5.9 二叉树的层序遍历

二叉树的遍历，有4种方式，前面我们已经学习了3种方式：前中后序遍历。

1. 思路讲解及举例

现在我们再来学一下二叉树的层序遍历。

那层序遍历的思想是什么呢，又该如何实现呢？

我们一起来看一下：

🆗，我们还来看这棵二叉树：

层序遍历就是从第一层开始，一层一层的往下遍历，每一层从左到右进行遍历。

对于这棵二叉树，它的层序遍历就是1 2 4 3 5 6

思想很简单，那如何用代码实现呢？

要实现层序遍历，在这里我们借助队列来实现：

怎么做呢？

我们先让根结点入队列，然后如果队列不为空，就出对头数据，并把对头数据的孩子结点带入队列，然后继续出对头数据，再将其孩子带入队列，依次循环往复，直到队列为空，就遍历完成了。

最终出队列的顺序就是层序遍历的结果。

2. 代码实现

接下来我们就来实现一下层序遍历：

由于层序遍历需要借助队列实现，所以得先有队列这种数据结构，不过我们之前已经实现过了，直接拿来用就行。

将之前的代码直接添加到当前项目中：

队列有了，我们就来写代码：

当然记得把队列的数据类型修改一下，之前队列我们存的是整型，现在应该存二叉树的结点是吧，但是存结点拷贝比较大，所以存结点指针更好一点：

//层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    printf("%d ", front->val);
    QueuePop(&q);
    if (front->left)
      QueuePush(&q, front->left);
    if (front->right)
      QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}

我们来测试一下：

是不是跟我们上面的结果一样啊，层序遍历就搞定了。

5.10 判断二叉树是否为完全二叉树

我们刚刚学过了二叉树的层序遍历，下面就有一个问题就很适合利用层序遍历来解决。

我们来看一下：

就是判断一棵二叉树是否为完全二叉树。

那如何判断呢？

解这道题的关键就在于我们要熟悉完全二叉树的一个特点：

就是完全二叉树的前n-1层一定是满的，最后一层可以不满，但是必须连续。

1. 思路讲解

那思路是什么呢？

就是对给定的二叉树进行层序遍历，判断其所有结点是否连续。

详细步骤如下：

首先就是层序遍历的步骤，我们先让根结点入队列，然后如果队列不为空，就出对头数据，并把对头数据的孩子结点带入队列，到这里要注意，我们上面层序遍历的时候如果结点的左孩子或右孩子为空，我们没有让它入队列（其实就是选择不打印空NULL罢了），但是在这里为了后面的判断，必须把空孩子也入队列。

这样一直循环往复，什么时候结束呢？

当出队列出出到空就结束，然后进行判断

此时队列中如果全为空，则表明是完全二叉树。

若存在不为空的：

则说明其结点不连续，不是完全二叉树。

🆗，这就是整体的一个思路。

2. 代码实现

下面我们写一下代码：

// 判断二叉树是否是完全二叉树
bool BinaryTreeJudge(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front == NULL)
    {
      break;
    }
    else
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

🆗，就完成了，我们测试一下：

这是我们当前项目里创建的二叉树：

它不是完全二叉树，判断正确

我们把它改成完全二叉树，再来测试一下：

在2的右边再链接一个结点：

6. 链式结构相关代码

层序遍历用到了队列，虽然之前文章里有，这里也再给大家分享一下队列的代码。

6.1 Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef struct BinaryTreeNode* QDataType;
//结点结构
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QueueNode;
//队列结构
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入数据
void QueuePush(Queue* pq,QDataType x);
//对头出数据
void QueuePop(Queue* pq);
//对头取数据
QDataType QueueFront(Queue* pq);
//队尾取数据
QDataType QueueBack(Queue* pq);
//计算队列元素个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

6.2 Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//队尾入数据
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)//空队列
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//对头出数据
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
}
//队头取数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//队尾取数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//计算队列元素个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
    n++;
    cur = cur->next;
  }
  return n;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

6.3 Test.c (对链式二叉树的各种操作）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType val;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
//前序遍历
void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->val);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->val);
  InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->val);
}
//创建二叉树结点
BTNode* CreateBTNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->val = x;
  node->left = node->right = NULL;
  return node;
}
//统计结点个数
//int TreeSize(BTNode* root)
//{
//  if (root == NULL)
//    return 0;
//  static int size = 0;
//  size++;
//  TreeSize(root->left);
//  TreeSize(root->right);
//  return size;
//}
//统计结点个数
int TreeSize(BTNode* root)
{
  return root == NULL ? 0 :
    1 + TreeSize(root->left) + TreeSize(root->right);
}
//统计叶子结点个数
int TreeLeafSize(BTNode* root)
{
  if (root)
  {
    if (root->left == NULL && root->right == NULL)
      return 1;
    return TreeLeafSize(root->left) +
      TreeLeafSize(root->right);
  }
  return 0;
}
//求二叉树的高度
int TreeHeight(BTNode* root)
{
  if (root)
  {
    int LeftHeight = TreeHeight(root->left);
    int RightHeight = TreeHeight(root->right);
    return
      LeftHeight > RightHeight ?
      LeftHeight + 1 : RightHeight + 1;
  }
  return 0;
}
// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{
  if (root)
  {
    if (k == 1)
      return 1;
    return TreeLevelKSize(root->left, k - 1)
    + TreeLevelKSize(root->right, k - 1);
  }
  return 0;
}
// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
  if (root)
  {
    if (root->val == x)
      return root;
    BTNode* ret1 = TreeFind(root->left, x);
    if (ret1)
      return ret1;
    BTNode* ret2 = TreeFind(root->right, x);
    if (ret2)
      return ret2;
    return NULL;
  }
  return NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    printf("%d ", front->val);
    QueuePop(&q);
    if (front->left)
      QueuePush(&q, front->left);
    if (front->right)
      QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeJudge(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    //遇到空，就跳出进行判断
    if (front == NULL)
    {
      break;
    }
    else
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}
//销毁
void TreeDestory(BTNode* root)
{
  if (root)
  {
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);
  }
}
int main() 
{
  BTNode* n1 = CreateBTNode(1);
  BTNode* n2 = CreateBTNode(2);
  BTNode* n3 = CreateBTNode(3);
  BTNode* n4 = CreateBTNode(4);
  BTNode* n5 = CreateBTNode(5);
  BTNode* n6 = CreateBTNode(6);
  BTNode* n7 = CreateBTNode(7);
  n1->left = n2;
  n2->left = n3;
  n1->right = n4;
  n4->right = n6;
  n4->left = n5;
  n2->right = n7;
  /*PrevOrder(n1);
  printf("\n");
  InOrder(n1);
  printf("\n");
  PostOrder(n1);
  printf("\n");*/
  /*printf("TreeSize:%d\n", TreeSize(n1));
  printf("TreeSize:%d\n", TreeSize(n1));
  printf("TreeSize:%d\n", TreeSize(n1));*/
  //printf("TreeLeafSize:%d\n", TreeLeafSize(n1));
  //printf("TreeHeight:%d\n", TreeHeight(n1));
  //printf("TreeLevelKSize:%d\n", TreeLevelKSize(n1, 2));
  //printf("TreeFind:%p\n", TreeFind(n1, 5));
  //printf("val:%d\n", TreeFind(n1, 5)->val);
  //LevelOrder(n1);
  if (BinaryTreeJudge(n1))
    printf("YES\n");
  else
    printf("NO\n");
  TreeDestory(n1);
  n1 = NULL;
  return 0;
}

那以上就是数据结构初阶二叉树的全部内容，希望能帮到大家。

同时，欢迎大家指正！！！

初阶数据结构】——写了将近 5 万字，终于把 二叉树 初阶的内容讲清楚了

前言

1. 树的概念及结构

1.1 树的概念

1.2 树与非树

1.3 树的相关概念

1.4 树的表示

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

2. 二叉树概念及结构

2.1 概念

2.2 现实中的二叉树

2.3 特殊的二叉树

2.3.1 满二叉树

2.3.1 完全二叉树

2.4 二叉树的性质

2.5 二叉树的存储结构

2.5.1 顺序存储

2.5.2 链式存储

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

3.1 二叉树的顺序结构

3.2 堆的概念及结构

堆的性质

孩子结点和父亲结点的下标关系

3.3 堆的实现

3.3.1 堆的向上调整算法

1. 铺垫及其前提

2. 算法讲解及实现

3. 向上调整建堆

3.3.2 堆的向下调整算法

2. 算法讲解及实现

3.3.3 剩余接口实现

3.3.4 堆的构建

1. 向下调整建堆

3.为何向下调整建堆更优

3.4 堆的应用

3.4.1 堆排序

3.4.2 TOP-K 问题

4. 堆及其应用对应 源码

4.1 heap.h

4.2 heap.c

4.3 test.c

5. 二叉树的链式结构及实现

5.1 二叉树的链式结构

5.2 二叉树的前、中、后序遍历

1. 举例

2. 代码实现（递归方式）

5.3 求二叉树结点个数

5.4 求叶子结点个数

5.5 求二叉树高度/深度

5.6 求第K层结点个数(k>=1)

5.7 查找值为x的结点

5.8 二叉树的创建和销毁

1.创建

3.代码展示

5.9 二叉树的层序遍历

1. 思路讲解及举例

2. 代码实现

5.10 判断二叉树是否为完全二叉树

1. 思路讲解

2. 代码实现

6. 链式结构相关代码

6.1 Queue.h

6.2 Queue.c

6.3 Test.c (对链式二叉树的各种操作）

热门文章

最新文章

相关课程

相关电子书

初阶数据结构】——写了将近 5 万字，终于把二叉树初阶的内容讲清楚了

4. 堆及其应用对应源码