C++算法
C++ 数据结构基础：树、二叉树及堆的特性与实现
树与二叉树的基础概念、术语及表示方法，重点讲解了满二叉树、完全二叉树的定义与性质。内容涵盖二叉树的顺序存储与链式存储结构，并深入分析了堆作为特殊完全二叉树的特性，包括大根堆与小根堆的定义，以及堆节点索引与父子关系的数学规律，为后续堆的实现奠定基础。
树与二叉树的基础概念、术语及表示方法，重点讲解了满二叉树、完全二叉树的定义与性质。内容涵盖二叉树的顺序存储与链式存储结构，并深入分析了堆作为特殊完全二叉树的特性，包括大根堆与小根堆的定义，以及堆节点索引与父子关系的数学规律，为后续堆的实现奠定基础。
树是一种非线性的数据结构，它是由 n(n>=0) 个有限结点组成一个具有层次关系的集合，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树有以下特点：
我们接下来演示几个非树形结构的样例，让我们更好地理解树这样一个结构：
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系
实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法，如下：
struct TreeNode {
struct Node* child; // 左边开始的第一个孩子结点
struct Node* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据
};
我们可以举一个例子来说明为什么孩子兄弟法可以轻松地表示出来整颗树，如下图的二叉树：
我们使用孩子兄弟法来表示这颗树的大致示意如下：
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联，如图：
我们先来看看现实中的二叉树：
可以看到这棵树的每个分支都只有两个节点，将它倒过来就是我们树形结构中的二叉树了
在树形结构中，我们最常用的就是二叉树，二叉树就是最大度为 2 的树，一个节点最多有两个孩子，它的结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空
二叉树具有以下特点:
一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 k，且结点总数是 2^k - 1，则它就是满二叉树，如图：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树
也就是说完全二叉树就是除了最后一层，其它层次的节点个数都达到最大，而满二叉树则要求不仅其它层次的节点个数都达到最大，最后一层的节点个数也要达到最大，所以满二叉树是一种特殊的完全二叉树，我们画一个完全二叉树看看：
二叉树一般可以使用两种结构存储，一种是顺序结构，另一种则是链式结构
顺序结构存储就是使用数组来存储二叉树，一般使用数组更适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，我们简单画两个图对比一下：
根据上图可以看到，如果我们使用数组存放完全二叉树，基本上不会产生空间浪费，就算有也只浪费了较少的空间，但是如果使用数组存放非完全二叉树的话，就会产生极大的空间浪费
所以我们一般使用数组存放完全二叉树，而使用数组存放完全二叉树的这种结构就是我们二叉树的顺序结构，但是如果我们存放的二叉树不是完全二叉树呢？这时候我们就会采用二叉树的链式结构来存放
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常表示的方法是，链表中每个结点由三个域组成，分别是数据域和左右指针域，左右指针域用来存放左右孩子的地址，数据域则是当前节点存放的数据
链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。在 C++ 篇章我们学到高阶数据结构后会用到三叉链，接下来我们分别来画一画二叉链，三叉链我们后面再学习，如图：
二叉树链式结构最大的特点就是，它可以存储非完全二叉树的同时不浪费空间，所以我们常常使用链式结构来存放一些不规则的二叉树，使用顺序结构存放完全二叉树
我们平常所说的堆是一种特殊的数据结构，那么它的本质是什么呢？它的本质其实就是一颗完全二叉树，并且使用顺序结构存储数据，也就是说堆是使用数组存放数据的一颗完全二叉树
但是堆比起平常普通的完全二叉树要多出一些特性，普通二叉树在上面已经介绍过了，我们现在重点介绍堆这种特殊的完全二叉树
堆这种特殊的完全二叉树特殊在它的根节点，它的根节点要么就是整个完全二叉树中的最大值，要么就是整个完全二叉树中的最小值，如果堆的根节点是最大值，那么就叫大根堆，如果是最小值就叫小根堆
那么是不是除了根节点以外其它节点就没有要求了呢？并不是的，因为一颗完全二叉树可以看成是由多颗子树构成，这些子树也有自己的根节点，它们也必须遵守在整颗子树中，根节点最大或最小这个要求，我们简单画个图理解：
在这颗完全二叉树中，首先整颗完全二叉树的最小值是根节点，然后根节点下面有左右两颗子树，其中左子树中的根节点 15 为左子树中的最小值，右子树中的根节点 56 为左子树中的最小值
随后左子树又有自己的左右子树，右子树也有自己的左右子树，只要一直遵守这个规则，最终我们就会得到一个堆，但是我们发现了一个问题，15 为根节点的子树下面的两个节点 25 和 30，比 15 的兄弟节点 56 都要小，这会不会有问题呢？
注意注意：在堆中，子树之间是独立存在的，互不影响，我们只看一颗子树的根节点是否是这颗子树的最小值，在左子树中 15 是它的最小值，在右子树中 56 是它的最小值，所以它依然满足堆的定义，因为子树之间是独立存在的，互不影响
所以上图的完全二叉树可以说完全遵守了堆的规则，每颗子树的根节点是整颗子树的最小值，那么上面的这颗完全二叉树其实是一个小根堆
现在应该能大致理解完全二叉树和堆的关系了吧，堆是一种更加特殊的完全二叉树，我们一般实现二叉树的顺序结构就是实现的堆这种特殊的完全二叉树
其实堆的特性我们上面基本上已经讲完了，我们现在可以总结一下它的特性，为我们后面的实现做一些铺垫，如下：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online