声明：图片引用自《极客时间——数据结构与算法之美》
二叉树
二叉树：就是最多只能有两个叉的树结构。
图中1是普通的二叉树，2、3是两种特殊的二叉树。
2是满二叉树
满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
3是完全二叉树
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大
不是完全二叉树的例子中：
第1个，不满足叶子节点都在最底下两层
第2个，不满足最后一层的叶子节点都靠左排列
第3个，不满足除了最后一层外，其他层的节点个数要达到最大
二叉树的具体存储表示
链式存储法
每个节点有三个部分，data存储数据，left、right部分是指针，存储节点的指向。类似链表。
代码中，可以想到用对象构建。
顺序存储法
顺序存储法，就是基于数组的存储方式。不需要像链式存储那样，每个节点还要保存left、right指针，占用额外的空间，顺序存储法只浪费一个下标0的存储空间。
当前，前提是这棵树是完全二叉树，所以完全二叉树是最适合用顺序存储法的树结构，这也是为什么完全二叉树要求最后一层子节点都靠左排列的原因。
如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。
二叉树的遍历
二叉树的三种遍历方式：
- 前序遍历
对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 - 中序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 - 后序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
简单总结：
节点自身什么时候打印，就是那种遍历。
节点自身最先打印，就是前序遍历；
节点自身中间的时候打印，就是中序遍历；
节点自身最后一个打印，就是后续遍历。
二叉树的遍历过程就是一个递归，只是递归的顺序不同，有了三种不同的遍历方式。
遍历二叉树的时间复杂度：
不管是哪种遍历方式，节点最多会被访问两次，所以总的遍历时间只和节点个数n有关，所以时间复杂度是O(n)
堆
堆结构是二叉树结构的一种，它必须满足以下要求：
- 堆是一个完全二叉树
- 每个节点的值必须都大于等于（或小于等于）其左右子节点的值
节点的值大于等于左右子节点的值，这种堆叫做大顶堆，因为它的根节点的值是最大的。
节点的值小于等于左右子节点的值，这种堆叫做小顶堆，因为它的根节点的值是最小的。
1、2是大顶堆，3是小顶堆，4不是堆，因为它不是完全二叉树。
