4.3.1 二叉树的遍历
所谓二叉树的遍历，是指按照某条搜索路径访问树中的每个结点，使得每个几点均被访问一次，而且仅被访问一次。
遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序、按照先序遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序遍历（LNR）和后序遍历（LRN）三种遍历算法。其中，序指的是根结点在何时被访问。
1、先序遍历（PreOrder）
如果二叉树为空，什么也不做，否则： 1）访问根结点
2）先序遍历左子树
3）先序遍历右子树
void preOrder(BiTree T){
if(T!=null){
visit(T);//访问根结点
preOrder(T->lchild);//递归遍历左子树
predOrder(T-rchild);//递归遍历右子树
}
}2、中序遍历（InOrder）
如果二叉树为空，什么也不做，否则：
1）中序遍历左子树
2）访问根结点
3）中序遍历右子树
void inOrder(BiTree T){
if(T!=null){
inOrder(T->lchild);//递归遍历左子树
visit(T);//访问根结点
inOrder(T-rchild);//递归遍历右子树
}
}3、后序遍历（PostOrder）
如果二叉树为空，什么也不做，否则：
1）后序遍历左子树
2）访问根结点
3）后序遍历右子树
void postOrder(BiTree T){
if(T!=null){
postOrder(T->lchild);//递归遍历左子树
postOrder(T-rchild);//递归遍历右子树
visit(T);//访问根结点
}
}三种遍历算法中递归遍历左、右子树的顺序是固定的，只是访问根结点的顺序不同。
不管采用哪种算法，每个结点都访问一次仅访问一次，故时间复杂度都是O(n)。在递归算法中，递归工作栈的栈深恰好为树的深度，所以在最坏的情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的时间复杂度为O(n).
4、递归算法和非递归算法的转化
可以借助栈，将二叉树的递归遍历算法转化为非递归算法，下面以中序遍历为例给出中序遍历的非递归算法。先扫描（并非访问）根结点的所有左节点并将它们一一进栈，然后出栈一个结点*p（显然结点*p没有左孩子结点或左孩子结点均已访问过），访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。
void inOrder2(BiTree T){
//二叉树中序遍历的非递归算法，算法需要借助一个栈
initStack(s);//初始化栈；
while（p||isEmpty(s)）{//p是遍历指针,栈不空或p不空时循环
IF(P){//p不空时
push（s,p）;//根指针进栈
p=p->lchild;//每遇到非空二叉树，先向左走
}else{
pop(s,p);//根指针退栈
visit(p);//访问根结点
p=p->rchild;//再向右子树走
}
}
}5、层次遍历
要进行层次遍历需要借助一个队列，现将二叉树根结点入队，然后出队，访问该结点，如果它由左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。
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);//右子树不空，则右子树入队列
}
}
}6、由遍历序列构造二叉树
由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树，在先序遍历序列中，第一个结点一定是二叉树的根结点，而在中序遍历中，根结点必然将中序序列分割称两个子序列，前一个子序列就是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点时右子树的根结点。如此递归地进行下去，便能唯一地确定这课二叉树。
同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树，因为后序序列的最后一个结点如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，就可以得到一棵二叉树。