二叉树的遍历
按某条上搜索路径访问树中的每个结点，树的每个结点均被访问一次，而且只访问一次。
遍历的三种方式：
1、先序便利（根左右）；
2、中序便利（左根右）；
3、中序便后（左右根）；
先序遍历
1、访问根结点
2、先序便利左子树
3、先序便利右子树
先序遍历的递归算法：
void PerOrder(BiTree T){
if(T!==null){
visit(T);
PerOrder(T->lchild);
PerOrder(T->rchild);
}
}
中序遍历
1、中序便利左子树
2、访问根结点
3、中序便利右子树
中序遍历的递归算法：
void InOrder(BiTree T){
if(T!==null){
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
后序遍历
1、后序便利左子树
3、后序便利右子树
2、访问根结点
后序遍历的递归算法：
void PostOrder(BiTree T){
if(T!==null){
PostOrder (T->lchild);
PostOrder (T->rchild);
visit(T);
}
}
中序遍历非递归算法，借助栈，算法思想：
1、初始时依次扫描根结点的所有左侧结点，并将它们一一进栈；
2、出栈一个结点，访问它；
3、扫描该结点的右孩子结点并将其进栈；
4、依次扫描右孩子结点的所有左侧结点并一一进栈；
5、反复该过程直到栈空为止。
void InOrder2(BiTree T){
InitStack(S);BiTree p = T;
while(p||!IsEmpty(S)){
if(p){
Push(S,p);
p=p->lchild;
}else{
Pop(S,p);
visit(p);
p->rchild;
}
}
}
层次遍历
1、初始将根入队并访问根结点，然后出队；
2、若有左子树，则将左子树的根入队；
3、若有右子树，则将右子树的根入队；
4、然后出队，访问该结点；
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);
}
}
}
由遍历序列构造二叉树
（后）先序遍历序列和中序遍历序列可以确定一颗二叉树，而后序遍历序列和先序遍历序列不可以确定一颗二叉树。
中序遍历序列和先序遍历序列
1、在先序序列中，第一个结点是根结点；
2、根结点将中序遍历序列划分为两部分；
3、然后在先序序列中确定两部分的结点，并且两部分的第一个结点分别为左子树和右子树的根；
4、在子树中递归重复该过程，便能唯一确定一课二叉树。
线索二叉树
线索化：
若无左子树，则将左指针指向其前驱结点；
若无右子树，则将右指针指向其后驱结点；
线索二叉树结点结构
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表。
中序线索二叉树
前驱结点：
如果左指针为线索，则其指向结点为前驱结点
如果左指针为左孩子，则其左子树的最右侧结点为前驱结点
后驱结点：
如果右指针为线索，则其指向结点为后驱结点
如果右指针为左孩子，则其右子树的最左侧结点为后驱结点
中序线索二叉树线索化
引入了头结点的线索二叉树
中序线索二叉树的遍历
