申明：图片援用自《极客工夫——数据结构与算法之美》

二叉树

二叉树：就是最多只能有两个叉的树结构。

图中 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 不是堆，因为它不是齐全二叉树。