>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
二叉树遍历大致分为以下两种：
1.先序遍历、中序遍历、后序遍历
2.层次遍历
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>一、1.先序遍历、中序遍历、后序遍历。遍历方式可以分为递归、非递归，非递归时需要使用栈。
对非递归先序/中序/后序遍历的总结：
a.前序序列和中序序列的关系相当于以前序序列作为入栈次序，中序序列作为出栈次序
对于上一句的解释：先序的入栈/出栈次序和中序的入栈/出栈次序一致，先序的入栈次序与先序的出栈次序一致，所以先序的入栈次序=中序的出栈次序
b.后序遍历访问到某结点时，此时栈中的结点为该结点的所有祖先结点
// ex12:打印二叉链表中值为x的结点的所有祖先（假设不止一个结点的值为x）。思路：使用非递归后序遍历，当遍历(出栈)时，如果出栈结点值=x时，此时栈里边的元素都是这个结点的祖先
void ex12_printFatherNodeWhenDataEqualsX(LTree T,char x){
LStack S;
initS(S);
LTNode *p = T;
LTNode *pre = NULL;
while(p || S->top != NULL){
if(p){
pushS(S,p);
p = p->lchild;
}else{
p = S->top->value;
if(p->rchild && pre != p->rchild){
p = p->rchild;
pushS(S,p);
p = p->lchild;
}else{
pullS(S,p);
if(p->data == x){
cout << x << "'s father: " << endl;
printS(S);
}
pre = p;
p = NULL;
}
}
}
}
>>>>>二、层次遍历。层次遍历是通过使用队列实现的（根结点入队->根结点出队、while(队列非空){根结点的左、右结点入队}）
层次建立的部分总结：
a.层次遍历的应用例如：求树宽、求树高
b.层次遍历如何判断一层遍历已经结束：使用顺序队进行层次遍历，初始化时Q.ftont=Q.rear=-1，设置last= 0。当last=Q.front时，说明一层遍历结束了，此时让last=Q.rear
// 层次遍历：顺序队实现。用顺序队可以方便计算树高、树宽，因为用last == Q.front就能判断是否一层遍历完毕
void levelOrder(LTree T){
SQueue Q;
initSQ(Q);
LTree E;
initT(E);
int last = 0,level =0,weight =0; // level树高、weight树宽
int count = 0; // 统计每层的结点数量
enSQueue(Q,T);
while(Q.Q_front < Q.Q_rear){
deSQueue(Q,E);
visitT(E);
if(E->lchild){
enSQueue(Q,E->lchild);
count ++;
}
if(E->rchild){
enSQueue(Q,E->rchild);
count ++;
}
if(last == Q.Q_front){ // 一层遍历完毕
last = Q.Q_rear;
level ++;
if(count > weight){
weight = count;
}
count = 0;
}
}
cout << "levelOrder: finish, weight: " << weight << ", high: " << level << endl;
}