| 遍历是按某种策略访问树中的每个结点，且仅访问一次。
|
|
|
| 由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根结点、左子树和右子树三部分构成，因此若能依次遍历这三个部分的信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，依据访问根结点位置的不同，可得到二叉树的前序、中序和后序三种遍历方法。
|
|
|
| 中序遍历二叉树的操作定义如下。若二叉树为空，则进行空操作。否则：
|
|
|
|
|
|
|
|
|
|
|
|
|
| 实际上，将中序遍历算法中对根结点的访问操作放在左子树的遍历之前或右子树的遍历之后，就分别得到先序遍历和后序遍历算法。遍历二叉树的过程实质上是按一定规则，将树中的结点排成一个线性序列的过程。
|
|
|
| 遍历二叉树的基本操作就是访问结点，不论按照哪种次序遍历，对含有n个结点的二叉树，遍历算法的时间复杂度都为O（n）。因为在遍历的过程中，每进行一次递归调用，都是将函数的“活动记录”压入栈中，因此，栈的容量恰为树的高度。在最坏情况下，二叉树是有n个结点且深度为n的单枝树，遍历算法的空间复杂度也为O（n）。
|
|
|
| 设二叉树的根结点所在层数为1，二叉树的层序遍历就是从树的根结点出发，首先访问第1层的树根结点，然后从左到右依次访问第二层上的结点，其次是第三层上的结点，以此类推，自上而下、自左至右逐层访问树中各层结点的过程就是层序遍历。
|
|
|
