定义
按照一定的顺序( 原则)对二叉树中每一个结点都访问一次(仅访问一次)，得到一个由该二叉树的所有结点组成的序列，这一过程称为二叉树的遍历。
常用的遍历方法:
1、前序遍历（DLR）
2、中序遍历（LDR）
3、后序遍历（LRD）
4、按层次遍历
对二叉树进行遍历的时间复杂度均为O(n)；
其中，L表示遍历左子树；R表示遍历右子树；D表示访问根节点；
前后中序是相对于根节点而言的，如下：
对于如下二叉树：
前序遍历
二叉树的前序遍历原则（递归）如下：
若被遍历的二叉树非空，则
1、访问根结点；
2、以前序遍历原则遍历根结点的左子树；
3、以前序遍历原则遍历根结点的右子树；
对于上述二叉树，前序序列为：A B D E J C F I G
递归算法的C语言实现如下：
void PREORDER(BTREE T)
{
if(T!=NULL){
VISIT(T); //访问T指结点
PREORDER(T->lchild);
PREORDER(T->rchild);
}
} 中序遍历
二叉树的中序遍历原则（递归）如下：
若被遍历的二叉树非空，则
1、以中序遍历原则遍历根结点的左子树；
2、访问根结点；
3、以中序遍历原则遍历根结点的右子树；
对于上述二叉树，中序序列为：D B J E A F I C G
递归算法的C语言实现如下：
void INORDER(BTREE T)
{
if(T!=NULL){
INORDER(T->lchild);
VISIT(T); //访问T指结点
INORDER(T->rchild);
}
} 后序遍历
二叉树的后序遍历原则（递归）如下：
若被遍历的二叉树非空, 则
1、以后序遍历原则遍历根结点的左子树；
2、以后序遍历原则遍历根结点的右子树；
3、访问根结点。
对于上述二叉树，后序序列为：D J E B I F G C A
递归算法的C语言实现，如下：
void POSTORDER(BTREE T)
{
if(T!=NULL){
POSTORDER(T->lchild);
POSTORDER(T->rchild);
VISIT(T); // 访问T指结点
}
} 按层遍历
二叉树按层遍历原则：
被遍历的二叉树非空,则按照层次从上到下,每一层从左到右依次访问结点。
上述二叉树，按层次遍历序列为：A, B, C, D, E, F, G, J, I
按层遍历的C语言实现（队列）如下：
#define
void LAYERORDER(BTREE T)
{
BTREE QUEUE[NodeNum], p; //顺序队列
int front, rear;
if(T!=NULL){
QUEUE[0]=T;
front=-1;
rear=0;
while(front<rear){ // 若队列不空，front负责读取，rear负责进入队列
p=QUEUE[++front];
VISIT(p); // 访问p指结点
if(p->lchild!=NULL) // 若左孩子非空
QUEUE[++rear]=p->lchild;
if(p->rchild!=NULL) // 若右孩子非空
QUEUE[++rear]=p->rchild;
}
}
} 递归问题的非递归算法的设计
递归算法的优点
(1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然；
(2)算法的描述直观，结构清晰，且算法的正确性证明比非递归算法容易。
递归算法的不足
(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显；
(2)对算法进行优化比较困难；
(3) 分析跟踪算法的执行过程比较麻烦；
(4)描述算法的语言不具有递归功能时，算法无法描述。
递归算法如何改为非递归算法？
以中序遍历为例，非递归算法设计如下：
1、若p 指向的结点非空，则将p指的结点的地址进栈，然后，将p 指向左子树的根;（p=p->lchild）
2. 若p 指向的结点为空，则从堆栈中退出栈顶元素送p，访问该结点，然后，将p 指向右子树的根；（p=p->rchild）
重复上述过程，直到p为空,并且堆栈也为空。
C语言实现如下：
void INORDER(BTREE T)
{
BTREE STACK[M], p=T;
int top=-1; //初始化堆栈
if(T!=NULL){
do {
while(p!=NULL){
STACK[++top]=p; //进栈
p=p->lchild;
}
p=STACK[top– –]; //左孩子为空，出栈
VISIT(p); // 将此行放置进栈循环体之前，即为前序遍历
p=p->rchild;
}while(!(p==NULL && top==-1));
}
} 其中，STACK[0: M-1]—保存遍历过程中结点的地址；
top—栈顶指针,初始为-1；
p—为遍历过程中使用的指针变量，初始时指向根结点。
中序遍历非递归算法核心思想
中序遍历非递归算法核心思想如下：
设置一个堆栈保存遍历过程中结点的位置；
设置一个变量，初始时给出根结点的位置；
反复执行下列过程：
1、若变量所指位置上的结点存在，则将该变量所指位置进栈，然后将该变量移到左孩子；
2、若变量所指位置上的结点不存在，则从堆栈中退出栈顶元素送变量，访问该变量位置上的结点，然后将该变量移到右孩子；
直到变量所指位置上结点不存在，同时堆栈也为空。
使用顺序存储结构实现中序遍历非递归算法
中序遍历非递归算法变形如下：
STACK[0…M-1] – 保存遍历过程中结点的位置(下标)；
top – 栈顶指针,初始为-1；
i – 为遍历过程中使用的位置变量，初始指向根结点（i=0，BT[0]）；
1、若i 指向的结点非空，则将i进栈，然后，将i 指向左子树的根（i=2*i+1）;
2、若i 指向的结点为空，则从堆栈中退出栈顶元素送i，访问该结点，然后，将i指向右子树的根（i=2*i+2）；
重复上述过程,直到i指的结点不存在，且堆栈也为空。
C 语言实现如下：
#define
void INORDER(datatype BT[],int n) //n为结点总数
{
int STACK[MaxSize],i,top=-1;
i=0;
if(n>=0){
do{
while(i<n){ //注意此执行条件
STACK[++top]=i; // BT[i]的位置i进栈
i=i*2+1; // 找到i的左孩子的位置
}
i=STACK[top--]; // 退栈
VISIT(BT[i]); // 访问结点BT[i]
i=i*2+2; // 找到i的右孩子的位置
}while(!(i>n-1 && top==-1)); //注意此执行条件
}
} 利用遍历序列恢复二叉树
可以利用前序序列和中序序列恢复二叉树；
可以利用中序序列和后序序列恢复二叉树；
不可以利用前序序列和后序序列恢复二叉树；