数据结构 - 树的遍历
一、二叉树的遍历
对于二叉树，常用的遍历方式包括：先序遍历、中序遍历、后序遍历和层次遍历 。
1、先序遍历（PreOrder）
先序遍历的操作过程如下：
若二叉树为空，则什么也不做；否则，
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
void PreOrder(BiTree T){ //先序遍历if(T!=NULL){visit(T); //访问根结点PreOrder(T->lchild); //递归遍历左子树PreOrder(T->rchild); //递归遍历右子树}
}2、中序遍历（InOrder）
中序遍历（InOrder）的操作过程如下：
若二叉树为空，则什么也不做；否则，
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
void InOrder(BiTree T){ //中序遍历if(T!=NULL){InOrder(T->lchild); //递归遍历左子树visit(T); //访问根结点InOrder(T->rchild); //递归遍历右子树}
}3、后序遍历（PostOrder）
后序遍历（PostOrder）的操作过程如下：
若二叉树为空，则什么也不做；否则，
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
void PostOrder(BiTree T){ //后序遍历伪代码if(T!=NULL){PostOrder(T->lchild); //递归遍历PostOrder(T->rchild); //递归遍历右子树visit(T); //访问根结点}
}4、层次遍历（LevelOrder）
层次遍历（LevelOrder）的操作过程如下：
（1）首先借助一个队列，先将二叉树根结点入队，然后出队，访问出队结点；
（2） 若它有左子树，则将左子树根结点入队；
（3） 若它有右子树，则将右子树根结点入队；
（4） 然后出队，访问出队结点。如此反复，直到队列为空[1,5]。
void LevelOrder(BiTree T){ //层次遍历InitQueue(Q); //初始化辅助队列BiTree P;EnQueue(Q,T); //将根结点入队while(!IsEmpty(Q)){ //队列不空则循环DeQueue(Q,P); //队头结点出队visit(p); //访问出队结点if(p->lchild!=NULL)EnQueue(Q,p->lchild); //左子树不空，则左子树根结点入队if(p->rchild!=NULL)EnQueue(Q,p->rchild); //右子树不空，则右子树根结点入队}
}
5、遍历示例
存在如下图所示二叉树：
二叉树示例
其先序遍历为ABDECF（根-左-右）
其中序遍历为DBEAFC（左-根-右）（仅二叉树有中序遍历）
其后序遍历为DEBFCA（左-右-根）
其层次遍历为ABCDEF
二、一般树的遍历
树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有三种方式：
1.先根遍历：若树非空，先访问树的根结点，然后依次先根遍历根结点的每棵子树。其遍历序列与其转换为二叉树的先序序列相同。
2.后根遍历：若树非空，先依次后根遍历根结点的每棵子树，然后访问树的根结点。其遍历序列与其转换为二叉树的后序序列相同。
3.层次遍历：与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。
例如：如下图所示：
其先根遍历为ABEFGCDHI
其后根遍历为EFGBCHIDA
其层次遍历为ABCDEFGHI