二叉树的遍历

遍历方案

　　从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

　　⑴访问结点本身（N）， 　　⑵遍历该结点的左子树（L）， 　　⑶遍历该结点的右子树（R）。 　　以上三种操作有六种执行次序： 　　NLR、LNR、LRN、NRL、RNL、RLN。 　　注意： 　　前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

三种遍历的命名

　　根据访问结点操作发生位置命名： 　　① NLR： 前序遍历(PreorderTraversal亦称（先序遍历）） 　　——访问根结点的操作发生在遍历其左右子树之前。 　　② LNR： 中序遍历(InorderTraversal) 　　——访问根结点的操作发生在遍历其左右子树之中（间），它也被叫做“对称序列”。 　　③ LRN： 后序遍历(PostorderTraversal) 　　——访问根结点的操作发生在遍历其左右子树之后。 　　注意： 　　由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为 先根遍历、中根遍历和后根遍历。

遍历算法

　　1．中序遍历的 递归算法定义： 　　若二叉树非空，则依次执行如下操作： 　　⑴遍历左子树； 　　⑵访问根结点； 　　⑶遍历右子树。 　　2．先序遍历的递归算法定义： 　　若二叉树非空，则依次执行如下操作： 　　⑴ 访问根结点； 　　⑵ 遍历左子树； 　　⑶ 遍历右子树。 　　3．后序遍历得递归算法定义： 　　若二叉树非空，则依次执行如下操作： 　　⑴遍历左子树； 　　⑵遍历右子树； 　　⑶访问根结点。

　　4．层次遍历

 

前序（Pre-order Traversal）、中序（In-order Traversal）、后序遍历（Post-orderTraversal）和深度优先搜索的顺序类似，层序遍历（Level-order Traversal）和广度优先搜索的顺序类似。
前序和中序遍历的结果合在一起可以唯一确定二叉树的形态，也就是说根据遍历结果可以构造出二叉树。