常見遍歷方式有四種，先序须喂、中序吁断、后序趁蕊、層次遍歷。
1. 先中后序遍歷（遞歸）
void preOrder(tree t)
{
if(t != NULL)
{
visit(t);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
先中后仔役，不過是調(diào)整了visit的順序而已掷伙。
2. 先中序遍歷（非遞歸）
void InOrder2(tree t)
{
InitStack(s);
tree p = t;
while(!p || !IsEmpty(s))
{
if(p)
{
push(s,p);
p = p->lchild;
}
else
{
pop(s,p);
visit(p);
p = p->rchlid;
}
}
}
無論前序還是中序，結點指針的順序都是
- 指向根結點又兵，入棧
- 不斷指向左孩子任柜，入棧（此時訪問結點，前序）
- 直到為空
- 指向通過出棧結點沛厨，指向雙親（此時訪問結點宙地，中序）
- 指向右孩子
不斷重復上述過程，
直到指向二叉樹右子樹最下層的最右的結點逆皮，此時由于不用指向雙親宅粥，因此臨時保存雙親結點的棧已經(jīng)為空。
再指向這個結點的右孩子（棧依舊為空）电谣，其右孩子也為空秽梅，因此滿足退出循環(huán)。
從微觀角度來看
指針指向一個結點
如果要訪問其左孩子（左孩子不為空時就要訪問）辰企，則要保存該結點（入棧）
以備指針指向該結點（出棧）风纠，以訪問其右孩子
每一個分支，都要先指向雙親結點牢贸，
然后指向它的左孩子（也許要遍歷左子樹）竹观，
然后回頭指向雙親結點，
接著指向它的右孩子（也許要遍歷右子樹）
前序潜索，中序的區(qū)別在于
前序是第一次指向結點時臭增，訪問結點
中序是指針指向結點的左孩子，通過出棧竹习，指針重新指向結點時誊抛，訪問結點
3. 后序非遞歸
后序遍歷方式依舊使用棧，分析可得遍歷流程為：
I. 指針指向根結點整陌，找到其左孩子
II. 指針指向其左孩子拗窃，訪問左子樹
III. 指針指向其右孩子，訪問右子樹
IV. 指針指向結點泌辫，訪問
V. 指針指向其雙親結點
入棧規(guī)則：結點入棧随夸，左子樹入棧，所有左子樹出棧后震放，結點右子樹進棧宾毒。
出棧規(guī)則：結點為葉子節(jié)點，立即出棧殿遂；結點的左右孩子均被訪問過诈铛。
一個子樹的根結點在這個過程中總共被指針指向過三次乙各，第一次通過其訪問其左孩子，第二次通過其訪問其右孩子幢竹，最后一次訪問該結點耳峦。
如何判斷是第幾次指向結點以確定該如何操作是問題關鍵。
方法有兩種：
(1) 保留指向上一次出棧結點的指針
若其等于棧頂結點的左孩子妨退，則表明左子樹遍歷完成妇萄，開始遍歷右子樹
若其等于棧頂結點的右孩子，則表明現(xiàn)結點的左右子樹都遍歷完畢咬荷，可以出棧
如果都不是冠句，指針指向棧頂左孩子，并入棧
(2) 創(chuàng)建一個tag棧幸乒，記錄s棧中結點被訪問的次數(shù)懦底，每次只處理棧頂結點。
根結點入棧罕扎，tag為0聚唐，則開始遍歷左子樹，且tag++
tag為1腔召，則開始遍歷右子樹杆查，且tag++
tag為2，則代表已經(jīng)遍歷完左右子樹臀蛛，將結點亲桦，以及tag出棧
void traverse(tree t)
{
initStack(s);
initStack(tag);
tree p = t;
push(p,s);
push(0,tag);
while(!IsEmpty(s))
{
switch(tag[top])
{
case 0:
{
tag[top]++;
p = getTop(s)->lchild;
if(p)
{
push(p,s);
push(0,tag);
}
}
case 1:
{
tag[top]++;
p = getTop(s)->rchild;
if(p)
{
push(p,s);
push(0,tag);
}
}
case 2:
{
visit(s[top]);
pop(s);
pop(tag);
}
}
}
}
(3) 雙棧法
- 根結點進入s1
- 根結點出棧，進入s2
- 根結點的左結點進入s1浊仆，右結點進入s1
- 右結點出棧客峭，進入s2
- 左結點出棧，進入s2
因此抡柿，進入s2的順序是舔琅，根結點，右結點洲劣，左結點
出棧的順序备蚓，左結點，右結點囱稽，根結點
void PostTraverse(BiTree T){
BiTree root = T ;
SqStack S1,S2; //輔助棧星著，S1用來存儲樹入棧，S2用來存儲后序遍歷序列
//初始化
InitStack(S1);
InitStack(S2) ;
Push(S1,root); //1.首先根節(jié)點入棧
while(!isEmpty(S1)){ //當棧S1不為空時：1.先S1出棧 2.將從S1出棧的棧頂元素入棧S2
BiTree P=Pop(S1);
Push(S2,P);
if(P->lchild !=NULL) Push(S1,P->lchild);
if(P->rchild !=NULL) Push(S1,P->rchild) ;
}
while(!isEmpty(S2)){
printf("%c",(*(--S2.top))->data);
}
}
