二叉树基础（上）：什么样的二叉树适合用数组存储？
二叉树基础（上）：什么样的二叉树适合用数组存储？
前面学习到的都是线性表结构，栈，队列等等。今天学习一种非线性表结构：树。树这种数据结构比线性表的数据结构要复杂的多，内容也比较多，所以作者 @王争 分四节来讲解。
树目录
带着问题学习，是最有效的学习方式：二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？
树（Tree）
什么是 树 呢？看下图中的树，观察这些 树 都有什么特征？
image
上图中的 树 ，与我们现实生活中的树很相似，上图中橙色的圆，就是 树 中存放的元素，树 中的每个元素，我们叫作 节点；用来连线相邻节点之间的关系，我们叫做 父子关系。
节点关系
除此之外，树还有三个比较相似的概念：高度(Height)、深度(Depth)、层(Level)。
他们的定义是这样的：
- 节点的高度 = 节点到叶子节点的
最长路径（有几条边连接的） - 节点的深度 = 根节点到这个节点所经历的边的个数
- 节点的层数 = 节点的深度 + 1
- 树的高度 = 根节点的高度
note：记忆方式，高度是从下往上算（叶子节点到该节点），深度是从上往下算（根节点到该节点）、高度和深度都是从 0 计数。层数是从 1 计数，跟深度计算类似。
树的三个概念的值举例
二叉树（Binary Tree）
我们最常用的就是二叉树。
二叉树，每个节点最多只有两个 叉，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的结点只有左子节点，有的节点只有右子节点。下图均为二叉树，所以也可以猜想下四叉树、八叉树长什么样子。
二叉树示例
上图中，编号 2 和编号 3 这两个二叉树是比较特殊的。
编号 2 的二叉树，叶子节点全在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。
编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列（最后一层的节点之间不能有空隙，从左到右不能有空隙），并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。
满二叉树的特征非常明显，但是完全二叉树的特征不怎么明显啊，单从长相来看，完全二叉树并没有特别特殊的地方，那么完全二叉树到底是如何定义的呢？
我们需要线了解，如何表示（或者存储）一个二叉树？
想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。
链式存储法
使用链表结构，每个节点有三个字段，数据、左节点指针、右节点指针。我们只要拎住根节点，就可以通过左右节点的指针，把整棵树都穿起来。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。
链表存储二叉树
基于数组的循序存储法
把根节点存储在下标 i = 1 的位置，把左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
公式
所以，求一个节点的父节点：i/2 即可（一般情况下，为了方便计算子节点，根节点都会存储在下标为 1 的位置）。
刚刚示例，其实就是一个完全二叉树，我们可以发现，完全二叉树会浪费下标为 0 的存储位置，如果是非完全二叉树的话，其实会浪费更多的数组存储空间。
非完全二叉树的顺序存储
所以，完全二叉树无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点要从左到右排列的原因。
堆其实是一种完全二叉树，最常用的存储方式就是数组。
二叉树的遍历
前面学习到二叉树的基本定义与存储方法，现在来学习一下二叉树非常重要的操作，二叉树的遍历。（比较常见的面试题）
如何将所有节点都遍历出来呢？三种经典方法：(前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序)
- 前序遍历
- 对于树中任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树
- 中序遍历
- 对于树中任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树
- 后序遍历
- 对于树中任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身
前中后三种遍历方法
实际上，二叉树的前、中、后序遍历就是一个递归的过程。
比如前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归的打印右子树。
前面学习递归的时候了解到，递归代码难不难写主要是看能不能写出递推公式，而写递推公式的关键就是，如果要解决问题 A ，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。所以，我们可以把前、中、后序遍历的递推公式都写出来。
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
通过递推公式来书写递归代码就简单很多了，以下是代码：
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码，表示打印 root 节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印 root 节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印 root 节点
}
二叉树的前、中、后序遍历的递归实现是不是很简单？那么 二叉树遍历的时间复杂度是多少呢？
从前面前、中、后序遍历的顺序图可以看到，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 ○(n)。
解答开篇 & 内容小结
今天学习到一种非线性表数据结构，树。关于树，需要掌握的概念：
- 节点名称：根节点、叶子节点、父节点、子节点、兄弟节点
- 概念：高度（从下往上数）、深度（从上往下数）、层数（深度加1）
我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。
二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。
二叉树既可以用链式存储，也可以用数组顺序存储。
数组循序存储的方式比较适合完全二叉树，其他类型的二叉树存储会比较浪费存储空间。
二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是 ○(n)。
使用递归代码来实现二叉树的遍历操作。
课后思考
- 给定一组数据，比如 1，3，5，6，9，10。求出可以构建出多少种不同的二叉树？
- 今天学习了三种二叉树的遍历方式，前、中、后序。还有一种遍历方式叫做按层遍历，如何实现呢？
