一本正经的聊数据结构（5）：二叉树的存储结构与遍历
前文传送门：
存储结构
前面的内容我们介绍了树和二叉树的一些基础概念，树是数据结构中的重中之重，而二叉树又是树结构中的重点。
一直以来，包括我上学的年代，对树和二叉树的掌握都是模棱两可，希望能通过这篇文章可以给各位讲清楚这些疑难点。
二叉树的存储结构分为两种，一种是顺序存储结构，另一种是链式存储结构。
顺序存储结构
顺序存储结构就是使用一维数组存储二叉树中的节点，并且节点的存储位置，就是数组的下标索引。
存储在一维数组中的样子如下：
这个示例是一个 完全二叉树 的示例， 完全二叉树 所对应的顺序存储刚好填满整个数组，但是如果二叉树不是 完全二叉树 的时候，采用顺序存储又是怎样的呢？
下图中浅色结点表示结点不存在：
存储在一维数组中的样子如下：
其中， ∧ 表示数组中此位置没有存储结点。可以看到，使用顺序存储已经造成了空间浪费的情况。
如果是极端的右斜二叉树，顺序存储情况会如何呢？
如下：
存储在一维数组中的样子如下：
可以看到，在顺序存储结构下，极端的右斜二叉树存储造成了存储空间的极大的浪费。
所以顺序存储方式一般适合完全二叉树。
链式存储结构
顺序存储结构有些无法满足二叉树的存储，那么我们考虑使用链式存储结构。
二叉树每个节点最多会有两个孩子，因此，可以将结点数据结构定义为一个数据和两个指针域。如下：
那么刚才我们的那个完全二叉树的存储结构就可以这么展现：
遍历
二叉树的 遍历 是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的遍历依据访问次序可以分为四种方式：
- 前序遍历
- 中序遍历
- 后序遍历
- 层次遍历
前序遍历
简单来讲， 前序遍历 就是由根节点开始，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
还是用这个完全二叉树举例子：
当他进行前序遍历的时候，访问顺序如下：
从根结点出发，则第一次到达结点 A ，故输出 A ;
继续向左访问，第一次访问结点 B ，故输出 B ；
按照同样规则，输出 D ，输出 H ；
当到达叶子结点H，返回到 D ，此时已经是第二次到达 D ，故不在输出 D ，进而向 D 右子树访问， D 右子树不为空，则访问至 I ，第一次到达 I ，则输出 I ；
I 为叶子结点，则返回到 D ， D 左右子树已经访问完毕，则返回到 B ，进而到 B 右子树，第一次到达 E ，故输出 E ；
向E左子树，故输出 J ；
按照同样的访问规则，继续输出 C 、 F 、 G 。
所以，这个完全二叉树的前序遍历结果为： ABDHIEJCFG 。
中序遍历
中序遍历 就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
还是上面的完全二叉树，访问顺序如下：
从根结点出发，则第一次到达结点 A ，不输出 A ，继续向左访问，第一次访问结点 B ，不输出 B ；继续到达 D ， H ；
到达 H ， H 左子树为空，则返回到 H ，此时第二次访问 H ，故输出 H ；
H 右子树为空，则返回至 D ，此时第二次到达 D ，故输出 D ；
由 D 返回至 B ，第二次到达 B ，故输出 B ；
按照同样规则继续访问，输出 J 、 E 、 A 、 F 、 C 、 G ；
所以，中序遍历的结果为： HDIBJEAFCG 。
后序遍历
后序遍历 就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
后序遍历 的访问顺序如下：
从根结点出发，则第一次到达结点 A ，不输出 A ，继续向左访问，第一次访问结点 B ，不输出 B ；继续到达 D ， H ；
到达 H ， H 左子树为空，则返回到 H ，此时第二次访问 H ，不输出 H ；
H 右子树为空，则返回至 H ，此时第三次到达 H ，故输出 H ；
由 H 返回至 D ，第二次到达 D ，不输出 D ；
继续访问至 I ， I 左右子树均为空，故第三次访问 I 时，输出 I ；
返回至 D ，此时第三次到达 D ，故输出 D ；
按照同样规则继续访问，输出 J 、 E 、 B 、 F 、 G 、 C ， A ；
所以，后序遍历的结果为： HIDJEBFGCA 。
层次遍历
层次遍历 就是按照树的层次自上而下的遍历二叉树。
层次遍历的访问顺序如下：
从根节点出发，第一个到达节点 A ，直接输出 A ；
继续向左访问，到达节点 B ，输出节点 B ，继续访问节点的右节点 C ，输出节点 C ，此时，第二层访问结束，继续访问第三层；
访问节点 B 的左节点 D ，输出 D ，继续访问节点 B 的右节点 E ，输出节点 E ；
剩下依次访问节点 F 、 G 、 H 、 I 、 J 。
所以层次遍历的结果为： ABCDEFGHIJ 。
小结
本文介绍了二叉树的存储结构以及四种遍历方式，各位看完了应该对二叉树有一个初步的认知，如果不涉及一些变种的二叉树，仅二叉树的基础内容而言，还是比较简单的，希望各位同学能够自己思考下，在大脑中能建立出一个二叉树的模型，方便后面的学习。