二叉树的遍历

　　⑴访问结点本身（n），

　　⑵遍历该结点的左子树（l），

　　⑶遍历该结点的右子树（r）。

　　以上三种操作有六种执行次序：

　　nlr、lnr、lrn、nrl、rnl、rln。

　　注意：

　　前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

　　根据访问结点操作发生位置命名：

　　——访问根结点的操作发生在遍历其左右子树之前。

　　——访问根结点的操作发生在遍历其左右子树之中（间），它也被叫做“对称序列”。

　　——访问根结点的操作发生在遍历其左右子树之后。

　　若二叉树非空，则依次执行如下操作：

　　⑴遍历左子树；

　　⑵访问根结点；

　　⑶遍历右子树。

　　2．先序遍历的递归算法定义：

　　⑴ 访问根结点；

　　⑵ 遍历左子树；

　　⑶ 遍历右子树。

　　3．后序遍历得递归算法定义：

　　⑵遍历右子树；

　　⑶访问根结点。

　　4．层次遍历

前序（pre-order traversal）、中序（in-order traversal）、后序遍历（post-ordertraversal）和深度优先搜索的顺序类似，层序遍历（level-order traversal）和广度优先搜索的顺序类似。

前序和中序遍历的结果合在一起可以唯一确定二叉树的形态，也就是说根据遍历结果可以构造出二叉树。