在使用扩展先序遍历创建二叉树时，首先要根据一棵二叉树写出它的先序遍历序列，然后根据图中各个节点左右孩子的 状况进行加点遍历，凡是没有左右孩子的节点，遍历到它的左右孩子是都用"."表示它的左右孩子，注意这里面的"."只是用来表示它的父节点没有它这个左孩子或右孩子，并不表示节点，所以在遍历过程中应该访问到"."就结束了，不能再沿着"."继续遍历。

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。本节主要讲二叉树中遍历过程，遍历方法，重点介绍扩展先序遍历序列以及利用此序列创建二叉树的过程，顺便比较一下各种遍历方法的异同和应用。

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

(1)访问结点本身(N)，

(2)遍历该结点的左子树(L)，

(3)遍历该结点的右子树(R)。

根据遍历的原则:先左后右，对于先序遍历，顾名思义就是先访问根节点，再访问左子树，最后访问右子树，

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

(1)遍历该结点的左子树(L)，

(2)访问结点本身(N)，

(3)遍历该结点的右子树(R)。

对于中序遍历，就是先访问左子树，再访问根节点，最后访问右子树;

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

(1)遍历该结点的左子树(L)，

(2)遍历该结点的右子树(R)。

(3)访问结点本身(N)，

对于后序遍历，就是先访问左子树，再访问右子树，最后访问根节点;

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

① NLR:前序遍历(PreorderTraversal亦称(先序遍历))

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

② LNR:中序遍历(InorderTraversal)

--访问根结点的操作发生在遍历其左右子树之中(间)。

③ LRN:后序遍历(PostorderTraversal)

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