遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
⑴访问结点本身（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）和广度优先搜索的顺序类似。
前序和中序遍历的结果合在一起可以唯一确定二叉树的形态，也就是说根据遍历结果可以构造出二叉树。
