编程语言算法
数据结构与算法：树、二叉树及堆与完全二叉树的关系
树与二叉树的基本概念、术语及存储结构。详细阐述了满二叉树与完全二叉树的定义与区别，分析了二叉树的顺序存储与链式存储特点。最后讲解了堆的定义及其与完全二叉树的关系，总结了堆的节点索引特性，为后续实现堆数据结构奠定基础。
树与二叉树的基本概念、术语及存储结构。详细阐述了满二叉树与完全二叉树的定义与区别，分析了二叉树的顺序存储与链式存储特点。最后讲解了堆的定义及其与完全二叉树的关系，总结了堆的节点索引特性，为后续实现堆数据结构奠定基础。
树是一种非线性的数据结构，它是由 n(n>=0) 个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树的特点：
我们接下来演示几个非树形结构的样例，让我们更好地理解树这样一个结构：
在上面的三个示例图中，它们的根节点都是 A，然后 BCD 三个节点分别构成了三颗子树，BCD 可以认为是三颗子树的'根节点'，但是它们并非是真正的树形结构，因为子树之间有了交集，不满足刚刚讲的树的最后一个特点，所以不构成真正的树形结构
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系。实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法，如下：
struct TreeNode {
// 左边开始的第一个孩子结点
struct Node* child;
// 指向其右边的下一个兄弟结点
struct Node* brother;
// 结点中的数据
int data;
};
我们可以举一个例子来说明为什么孩子兄弟法可以轻松地表示出来整颗树，如下图的二叉树：
我们使用孩子兄弟法来表示这颗树的大致示意如下：
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联，如图：
我们先来看看现实中的二叉树：
可以看到这棵树的每个分支都只有两个节点，将它倒过来就是我们树形结构中的二叉树了，我们简单画一个二叉树，如图：
在树形结构中，我们最常用的就是二叉树，二叉树就是最大度为 2 的树，一个节点最多有两个孩子，它的结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空
二叉树的特点：
对于任意的二叉树都是由以下几种情况复合而成
一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 k，且结点总数是 2^k - 1，则它就是满二叉树，如图：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。也就是说完全二叉树就是除了最后一层，其它层次的节点个数都达到最大，而满二叉树则要求不仅其它层次的节点个数都达到最大，最后一层的节点个数也要达到最大，所以满二叉树是一种特殊的完全二叉树，我们画一个完全二叉树看看：
二叉树一般可以使用两种结构存储，一种是顺序结构，另一种则是链式结构
顺序结构存储就是使用数组来存储二叉树，一般使用数组更适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，我们简单画两个图对比一下：
根据上图可以看到，如果我们使用数组存放完全二叉树，基本上不会产生空间浪费，就算有也只浪费了较少的空间，但是如果使用数组存放非完全二叉树的话，就会产生极大的空间浪费。所以我们一般使用数组存放完全二叉树，而使用数组存放完全二叉树的这种结构就是我们二叉树的顺序结构，但是如果我们存放的二叉树不是完全二叉树呢？这时候我们就会采用二叉树的链式结构来存放
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常表示的方法是，链表中每个结点由三个域组成，分别是数据域和左右指针域，左右指针域用来存放左右孩子的地址，数据域则是当前节点存放的数据。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。在后续内容我们会用到三叉链，接下来我们分别来画一画二叉链，三叉链我们后面再学习，如图：
二叉树链式结构最大的特点就是，它可以存储非完全二叉树的同时不浪费空间，所以我们常常使用链式结构来存放一些不规则的二叉树，使用顺序结构存放完全二叉树
我们平常所说的堆是一种特殊的数据结构，那么它的本质是什么呢？它的本质其实就是一颗完全二叉树，并且使用顺序结构存储数据，也就是说堆是使用数组存放数据的一颗完全二叉树。但是堆比起平常普通的完全二叉树要多出一些特性，普通二叉树在上面已经介绍过了，我们现在重点介绍堆这种特殊的完全二叉树。堆这种特殊的完全二叉树特殊在它的根节点，它的根节点要么就是整个完全二叉树中的最大值，要么就是整个完全二叉树中的最小值，如果堆的根节点是最大值，那么就叫大根堆，如果是最小值就叫小根堆。那么是不是除了根节点以外其它节点就没有要求了呢？并不是的，因为一颗完全二叉树可以看成是由多颗子树构成，这些子树也有自己的根节点，它们也必须遵守在整颗子树中，根节点最大或最小这个要求，我们简单画个图理解：
在这颗完全二叉树中，首先整颗完全二叉树的最小值是根节点，然后根节点下面有左右两颗子树，其中左子树中的根节点 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