C++ 数据结构基础：树、二叉树及堆的特性与实现

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系

实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法，如下：

struct TreeNode {
    struct Node* child; // 左边开始的第一个孩子结点
    struct Node* brother; // 指向其右边的下一个兄弟结点
    int data; // 结点中的数据
};

我们可以举一个例子来说明为什么孩子兄弟法可以轻松地表示出来整颗树，如下图的二叉树：

我们使用孩子兄弟法来表示这颗树的大致示意如下：

4.树形结构实际运用举例

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联，如图：

二、二叉树的概念及特殊二叉树

1.二叉树的概念

我们先来看看现实中的二叉树：

可以看到这棵树的每个分支都只有两个节点，将它倒过来就是我们树形结构中的二叉树了

在树形结构中，我们最常用的就是二叉树，二叉树就是最大度为 2 的树，一个节点最多有两个孩子，它的结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空

二叉树具有以下特点:

• 二叉树不存在度大于 2 的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
• 对于任意的二叉树都是由以下几种情况复合而成

2.特殊的二叉树

满二叉树

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

完全二叉树

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

也就是说完全二叉树就是除了最后一层，其它层次的节点个数都达到最大，而满二叉树则要求不仅其它层次的节点个数都达到最大，最后一层的节点个数也要达到最大，所以满二叉树是一种特殊的完全二叉树，我们画一个完全二叉树看看：

二叉树的性质 (由满二叉树特点推导)

• 如果根节点是二叉树的第 1 层，那么一颗非空二叉树中的第 k 层最多有 2^(k-1) 个节点
• 如果根节点是二叉树的第 1 层，那么一共 k 层的二叉树最多有2^k - 1 个节点，可以根据等比数列求和公式证明
• 如果根节点是二叉树的第 1 层，并且有 n 个节点，那么这颗二叉树有h = log2 (n+1) 层

三、二叉树的存储结构

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

1.二叉树的顺序结构

顺序结构存储就是使用数组来存储二叉树，一般使用数组更适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，我们简单画两个图对比一下：

根据上图可以看到，如果我们使用数组存放完全二叉树，基本上不会产生空间浪费，就算有也只浪费了较少的空间，但是如果使用数组存放非完全二叉树的话，就会产生极大的空间浪费

所以我们一般使用数组存放完全二叉树，而使用数组存放完全二叉树的这种结构就是我们二叉树的顺序结构，但是如果我们存放的二叉树不是完全二叉树呢？这时候我们就会采用二叉树的链式结构来存放

2.二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常表示的方法是，链表中每个结点由三个域组成，分别是数据域和左右指针域，左右指针域用来存放左右孩子的地址，数据域则是当前节点存放的数据

链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。在 C++ 篇章我们学到高阶数据结构后会用到三叉链，接下来我们分别来画一画二叉链，三叉链我们后面再学习，如图：

二叉树链式结构最大的特点就是，它可以存储非完全二叉树的同时不浪费空间，所以我们常常使用链式结构来存放一些不规则的二叉树，使用顺序结构存放完全二叉树

四、堆和完全二叉树之间的关系以及堆的特性

1.堆和完全二叉树之间的关系

我们平常所说的堆是一种特殊的数据结构，那么它的本质是什么呢？它的本质其实就是一颗完全二叉树，并且使用顺序结构存储数据，也就是说堆是使用数组存放数据的一颗完全二叉树

但是堆比起平常普通的完全二叉树要多出一些特性，普通二叉树在上面已经介绍过了，我们现在重点介绍堆这种特殊的完全二叉树

堆这种特殊的完全二叉树特殊在它的根节点，它的根节点要么就是整个完全二叉树中的最大值，要么就是整个完全二叉树中的最小值，如果堆的根节点是最大值，那么就叫大根堆，如果是最小值就叫小根堆

那么是不是除了根节点以外其它节点就没有要求了呢？并不是的，因为一颗完全二叉树可以看成是由多颗子树构成，这些子树也有自己的根节点，它们也必须遵守在整颗子树中，根节点最大或最小这个要求，我们简单画个图理解：

在这颗完全二叉树中，首先整颗完全二叉树的最小值是根节点，然后根节点下面有左右两颗子树，其中左子树中的根节点 15 为左子树中的最小值，右子树中的根节点 56 为左子树中的最小值

随后左子树又有自己的左右子树，右子树也有自己的左右子树，只要一直遵守这个规则，最终我们就会得到一个堆，但是我们发现了一个问题，15 为根节点的子树下面的两个节点 25 和 30，比 15 的兄弟节点 56 都要小，这会不会有问题呢？

注意注意：在堆中，子树之间是独立存在的，互不影响，我们只看一颗子树的根节点是否是这颗子树的最小值，在左子树中 15 是它的最小值，在右子树中 56 是它的最小值，所以它依然满足堆的定义，因为子树之间是独立存在的，互不影响

所以上图的完全二叉树可以说完全遵守了堆的规则，每颗子树的根节点是整颗子树的最小值，那么上面的这颗完全二叉树其实是一个小根堆

现在应该能大致理解完全二叉树和堆的关系了吧，堆是一种更加特殊的完全二叉树，我们一般实现二叉树的顺序结构就是实现的堆这种特殊的完全二叉树

2.堆的特性

其实堆的特性我们上面基本上已经讲完了，我们现在可以总结一下它的特性，为我们后面的实现做一些铺垫，如下：

1. 堆中某个结点的值总是不大于或不小于其父结点的值
2. 堆总是一棵完全二叉树
3. 对于具有 n 个结点的堆来说，如果按照从上至下，从左至右的顺序对所有结点依次编号 (编号的目的是为了将它们存放到数组中)，那么对下标为 k 的节点有以下特性： （1）如果 k > 0，那么 k 节点的父节点/双亲节点的下标为 (k - 1)/2，k == 0 时为根节点的编号，无双亲节点 （2）如果 2k + 1 < n，那么 k 节点的左孩子下标为 2k + 1，否则无左孩子 （3）如果 2k + 2 < n，那么 k 节点的右孩子下标为 2k + 2，否则无右孩子