二叉树是 n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。
由二叉树的定义，以及图中所示的二叉树的分析可以得出二叉树具有以下几个特点：
（1）每个节点最多有两颗子树，所以二叉树中不存在度大于 2 的节点。
（2）左子树和右子树是有顺序的，次序不能任意颠倒。
（3）即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。
所有的节点都只有左子树的二叉树叫左斜树。所有节点都是只有右子树的二叉树叫右斜树，这两者统称为斜树。
在一棵二叉树中。如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
（1）顺序存储
二叉树的顺序存储结构就是使用一维数组存储二叉树中的节点，并且节点的存储位置，就是数组的下标索引。
可以看出，当二叉树为完全二叉树时，节点数刚好填满数组。那么当二叉树不为完全二叉树时，采用顺序存储形式如何呢？
其中，未填充节点表示节点不存在。
其中，∧ 表示数组中此位置没有存储节点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。对于这种情况采用顺序存储的方式是十分浪费空间的。因此，顺序存储一般适用于完全二叉树
（2）二叉链表
既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个节点最多有两个孩子。因此，可以将节点数据结构定义为一个数据和两个指针域
则完全二叉树用二叉链表可以这样表示
二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种：
前序遍历
中序遍历
后序遍历
层序遍历
前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。图中的 123 不代表访问顺序，访问顺序在下文中。
图 3.13 所示二叉树访问如下：
从根结点出发，则第一次到达结点 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；
则 3.13 所示二叉树的前序遍历输出为：
ABDHIEJCFG
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图 3.13 所示二叉树中序访问如下：
从根结点出发，则第一次到达结点 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；
则 3.13 所示二叉树的中序遍历输出为：
HDIBJEAFCG
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图 3.13 所示二叉树后序访问如下：
从根结点出发，则第一次到达结点 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；
则图 3.13 所示二叉树的后序遍历输出为：
HIDJEBFGCA
层次遍历就是按照树的层次自上而下的遍历二叉树。针对图 3.13 所示二叉树的层次遍历结果为：
ABCDEFGHIJ
层次遍历的详细方法可以参考二叉树的按层遍历法。
对于二叉树的遍历有一类典型题型。
1）已知前序遍历序列和中序遍历序列，确定一棵二叉树。
例题：若一棵二叉树的前序遍历为 ABCDEF，中序遍历为 CBAEDF，请画出这棵二叉树。
分析：前序遍历第一个输出结点为根结点，故 A 为根结点。中序遍历中根结点处于左右子树结点中间，故结点 A 的左子树中结点有 CB，右子树中结点有 EDF。如图 3.14 所示：
2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。
后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。
注 ：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。
叉起来，下一篇是二叉搜索树
邯城往事