二叉樹(shù)的遍歷
按某條上搜索路徑訪問(wèn)樹(shù)中的每個(gè)結(jié)點(diǎn)笨蚁，樹(shù)的每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且只訪問(wèn)一次趟庄。
遍歷的三種方式：
1括细、先序便利（根左右）；
2戚啥、中序便利（左根右）奋单；
3、中序便后（左右根）猫十；
先序遍歷
1览濒、訪問(wèn)根結(jié)點(diǎn)
2、先序便利左子樹(shù)
3拖云、先序便利右子樹(shù)
先序遍歷的遞歸算法：
void PerOrder(BiTree T){
? ? ? ? if(T!==null){
? ? ? ? ? ? ? ? visit(T);
? ??????????????PerOrder(T->lchild);
? ??????????????PerOrder(T->rchild);
????????}
}
中序遍歷
1贷笛、中序便利左子樹(shù)
2、訪問(wèn)根結(jié)點(diǎn)
3宙项、中序便利右子樹(shù)
中序遍歷的遞歸算法：
void InOrder(BiTree T){
????????if(T!==null){??
????????????????InOrder(T->lchild);
????????????????visit(T);
????????????????InOrder(T->rchild);
????????}
}
后序遍歷?
1乏苦、后序便利左子樹(shù)
3、后序便利右子樹(shù)
2尤筐、訪問(wèn)根結(jié)點(diǎn)
后序遍歷的遞歸算法：
void PostOrder(BiTree T){
if(T!==null){
???????????????? PostOrder (T->lchild);
? ???????????????PostOrder (T->rchild);
????????????????visit(T);
????????}
}
中序遍歷非遞歸算法汇荐，借助棧，算法思想：
1盆繁、初始時(shí)依次掃描根結(jié)點(diǎn)的所有左側(cè)結(jié)點(diǎn)掀淘，并將它們一一進(jìn)棧；
2改基、出棧一個(gè)結(jié)點(diǎn)繁疤，訪問(wèn)它；
3秕狰、掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)并將其進(jìn)棧稠腊；
4、依次掃描右孩子結(jié)點(diǎn)的所有左側(cè)結(jié)點(diǎn)并一一進(jìn)棧鸣哀；
5架忌、反復(fù)該過(guò)程直到棧空為止我衬。
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叹放、初始將根入隊(duì)并訪問(wèn)根結(jié)點(diǎn)饰恕，然后出隊(duì)；
2井仰、若有左子樹(shù)埋嵌，則將左子樹(shù)的根入隊(duì)；
3俱恶、若有右子樹(shù)雹嗦，則將右子樹(shù)的根入隊(duì)；
4合是、然后出隊(duì)了罪，訪問(wèn)該結(jié)點(diǎn)；
5聪全、反復(fù)該過(guò)程直到隊(duì)列空為止泊藕；
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);
? ? ? ? ? ? ? ? }
? ? ? ? }
}
由遍歷序列構(gòu)造二叉樹(shù)
（后）先序遍歷序列和中序遍歷序列可以確定一顆二叉樹(shù)，而后序遍歷序列和先序遍歷序列不可以確定一顆二叉樹(shù)难礼。
中序遍歷序列和先序遍歷序列
1娃圆、在先序序列中，第一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)鹤竭；
2踊餐、根結(jié)點(diǎn)將中序遍歷序列劃分為兩部分；
3臀稚、然后在先序序列中確定兩部分的結(jié)點(diǎn)吝岭，并且兩部分的第一個(gè)結(jié)點(diǎn)分別為左子樹(shù)和右子樹(shù)的根；
4吧寺、在子樹(shù)中遞歸重復(fù)該過(guò)程窜管，便能唯一確定一課二叉樹(shù)。
線索二叉樹(shù)
線索化：
若無(wú)左子樹(shù)稚机，則將左指針指向其前驅(qū)結(jié)點(diǎn)幕帆；
若無(wú)右子樹(shù)，則將右指針指向其后驅(qū)結(jié)點(diǎn)赖条；
線索二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)
typedef struct ThreadNode{
? ? ? ? ElemType data;
? ? ? ? struct ThreadNode *lchild,*rchild;
? ? ? ? int ltag,rtag;
}ThreadNode,*ThreadTree;
這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)失乾，稱為線索鏈表。
中序線索二叉樹(shù)
前驅(qū)結(jié)點(diǎn)：
如果左指針為線索纬乍，則其指向結(jié)點(diǎn)為前驅(qū)結(jié)點(diǎn)
如果左指針為左孩子碱茁，則其左子樹(shù)的最右側(cè)結(jié)點(diǎn)為前驅(qū)結(jié)點(diǎn)
后驅(qū)結(jié)點(diǎn)：
如果右指針為線索，則其指向結(jié)點(diǎn)為后驅(qū)結(jié)點(diǎn)
如果右指針為左孩子仿贬，則其右子樹(shù)的最左側(cè)結(jié)點(diǎn)為后驅(qū)結(jié)點(diǎn)
中序線索二叉樹(shù)線索化
引入了頭結(jié)點(diǎn)的線索二叉樹(shù)
中序線索二叉樹(shù)的遍歷
