二叉树的遍历，就是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
遍历一棵二叉树便要决定对根结点N，左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序(NLR)、中序(LNR)、后序(LRN)三种遍历算法，其中的序是指根结点在何时被访问。
一、先序遍历
先序遍历(PreOrder)的操作过程如下：
若二叉树为空，则什么也不做；否则：
1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。
对应的递归算法如下：
void PreOrder(BiTree T)
{
if(T!=NULL)
{
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
上图先序遍历得到的结果为1,2,4,6,3,5。
注意：这里提供的是伪代码的形式，主要是明白遍历思想，具体要结合实际问题实际分析，下同。
二、中序遍历
中序遍历(InOrder)的操作过程如下：
若二叉树为空，则什么也不做；否则，
1）中序遍历左子树；
2）访问根结点；
3）中序遍历右子树。
对应的递归算法如下：
void InOrder(BiTree T)
{
if(T!=NULL)
{
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
又是这个图，其中序遍历得到的结果为2,6,4,1,3,5。
这里可能不太好理解，分步列一下：
（1）进入结点1左子树；
（2）进入结点2左子树，为空，结点2左子树访问完毕，返回结点2；
（3）访问结点2，访问顺序为2；
（4）进入结点2右子树；
（5）进入结点4左子树；
（6）进入结点6左子树，为空，返回结点6；
（7）访问结点6，访问顺序为2,6；
（8）进入结点6右子树，为空，返回结点6，结点4左子树访问完毕，返回结点4；
（9）访问结点4，访问顺序为2,6,4；
（10）进入结点4右子树，为空，返回结点4，结点2右子树访问完毕，返回结点1；
（11）访问根结点1，访问顺序为2,6,4,1；
右子树的访问思路同上。
三、后序遍历
后序遍历(PostOrder)的操作过程如下：
若二叉树为空，则什么也不做；否则，
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根结点。
对应的递归算法如下：
void PostOrder(BiTree T)
{
if(T!=NULL)
{
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根结点
}
}
还是这个图，后序遍历得到的结果为6,4,2,5,3,1
这个应该还是比较好理解的。
三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。
四、递归算法和非递归算法的转换
借助栈，我们可以将二叉树的递归遍历算法转换为非递归算法。以中序遍历为例，先扫描根结点的所有左结点并将它们一一进栈，然后出栈一个结点*p，访问它，然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。
中序遍历的非递归算法如下：
void InOrder2(BiTree T)
{ //二叉树中序遍历的非递归算法需要借助一个栈
InitStack(S);
BiTree p=T; //初始化栈；p是遍历指针
while(p||!IsEmpty(S)) //栈不空或p不空时循环
{
if(P) //根指针进栈，遍历左子树
{
Push(S,p); //每遇到非空二叉树先向左走
p=p->lchild;
}
else //根指针退栈，访问根结点，遍历右子树
{
Pop(S,p); //退栈，访问根结点
visit(p);
p=p->rchild; //再向右子树走
}
}
}
非递归算法的效率肯定比递归算法的效率高滴！
五、层次遍历
层次遍历顾名思义就是对每一层都进行遍历，如下图所示：
要进行层次遍历需要一个队列。先将二叉树根结点入队，然后出队，访问该结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列空。
二叉树层次遍历算法如下：
void LevelOrder(BiTree T)
{
InitQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根结点入队
while(!IsEmpty(Q)) //队列不空循环
{
DeQueue(Q,p); //队头元素出队
visit(p); //访问当前p所指向结点
if(p->lchild!=NULL)
EnQueue(Q,p->lchild); //左子树不空，则左子树入队列
if(p->rchild!=NULL)
EnQueue(Q,p->rchild); //右子树不空，则右子树入队列
}
}
六、由遍历序列构造二叉树
由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
由二叉树的层次序列和中序序列也可以唯一地确定一棵二叉树。
这告诉我们一个道理：想要利用遍历序列构造二叉树，中序序列必不可少！！