一：前言
二叉樹的遍歷方法分四種:前序，中序，後序以及層次遍歷。
其中，前中後遍歷方法的實現分遞歸和非遞歸，非遞歸遍歷的實現需要借助於棧。
實際上，遞歸的調用就是一種棧的實現，所以，非遞歸遍歷就需要人工借助棧結構來實現。
而層次遍歷需要借助隊列。
二：前中後序遍歷
遞歸遍歷：
遞歸遍歷的思想和方法很簡單，通過調整輸出語句來實現前，中，後三種遍歷。
代碼如下：
void show(BiTree T)
{
if(T)
{
printf("%c ",T->data);//修改這三個語句的順序分別實現三種遍歷
show(T->lchild);
show(T->rchild);
}
}
非遞歸遍歷：
總結了5總不同的非遞歸遍歷算法，四種思路，都需要借助棧來完成。
第一種遍歷算法：
算法的思路：
1.從根結點開始，若當前結點的左孩子不為空，則遍歷左孩子並進棧。
2.結點的左孩子為空時，出棧並遍歷當前結點的右孩子結點
3.以右孩子結點為根結點，又沿著左孩子不斷遍歷，重復1.2步驟
此算法為前序遍歷
void preorder1(BiTree T)//前序遍歷1
{
LinkStack s;
InitStack(&s);
BiTree temp;
temp = T;
while(temp || !EmptyStack(s)) //第一個條件temp是為了進入循環
{
if(temp) //一直遍歷左子樹到底部
{
Push(&s,temp);
printf("%c",temp->data);
temp = temp->lchild;
}
else //lchild為空，跳轉到rchild
{
Pop(&s,&temp);
temp = temp->rchild;
}
}
}
第二種遍歷算法：
算法思路與第一種遍歷算法一致，只是改變了遍歷語句的位置，不是在進棧的時候輸出，而是在出棧的時候輸出，前序遍歷則為中序遍歷
1.從根結點開始，當前結點左孩子不為空時，左孩子進棧。
2.當前結點左孩子為空時，出棧並輸出當前結點，然後跳轉該結點的右孩子
3.重復1，2步驟直到棧空
void inorder(BiTree T)//中序遍歷
{
LinkStack s;
InitStack(&s);
BiTree temp = T;
while(temp || !EmptyStack(s))
{
if(temp)
{
Push(&s,temp);
temp = temp->lchild;
}
else
{
Pop(&s,&temp);
printf("%c ",temp->data); //出棧時輸出則為中序遍歷
temp = temp->rchild;
}
}
}
第三種遍歷算法：
此種算法為前序遍歷
算法思路：1.先將根結點入棧
2.出棧棧頂並輸出，先入棧當前結點的右孩子結點，在入棧當前結點的左孩子結點
3.重復第2步直到棧空
void preorder2(BiTree T)
{
LinkStack s;
InitStack(&s);
BiTree temp = T;
Push(&s,temp);
while(!EmptyStack(s))
{
Pop(&s,&temp); //出棧頂並輸出
printf("%c ",temp->data);
if(temp->rchild) //入棧右孩子
{
Push(&s,temp->rchild);
}
if(temp->lchild) //入棧左孩子
{
Push(&s,temp->lchild);
}
}
}
第四種遍歷算法：
後序遍歷的非遞歸實現比較復雜，要保證輸出當前結點時左右孩子結點已經輸出（或者左右孩子為空）
即每輸出一個結點要滿足以下兩個條件之一：
1.此結點的左右孩子為空
2.此結點的左右孩子已經遍歷
算法思路：1.先將根結點入棧，以棧空為循環停止的條件
2. 用結點指針pre記錄上一個輸出結點地址，cur記錄當前結點地址
2.1 當前結點的左右孩子為空時，或者pre記錄的結點為當前結點的左（右）孩子時，出棧並輸出當前結點，並更新pre
2.2 否則按照右孩子，左孩子的順序入棧
3.循環第2步直到棧空
void postorder(BiTree T)
{
BiTree pre,cur;
LinkStack s;
InitStack(&s);
cur = pre = T;
Push(&s,cur);
while(!EmptyStack(s))
{
GetTop(s,&cur); //當前結點的左右孩子都為空，pre為cur的左孩子或者右孩子時，出棧並輸出當前結點
if((cur->lchild == NULL && cur->rchild == NULL) || cur->lchild == pre || cur->rchild == pre)
{
Pop(&s,&cur);
printf("%c ",cur->data);
pre = cur; //更新當前結點
}
else
{
if(cur->rchild) //否則入棧右孩子，左孩子
{
Push(&s,cur->rchild);
}
if(cur->lchild)
{
Push(&s,cur->lchild);
}
}
}
}
第五種遍歷算法：
此種非遞歸遍歷算法思想可以像遞歸遍歷一樣通過修改部分的順序做到：前中後序三種遍歷。
不過便利往往帶來的是代碼結構上的復雜，此種算法所借助的棧和上面的遍歷算法借助的棧不同。
上面的算法使用的棧存儲的數據時一個二叉樹結點指針，而此算法棧儲存的是一個結構體
棧數據類型定義：
typedef struct { // 棧數據定義
BiTree ptr;
int task;
}Datatype;
其中，task有兩個值，0表示訪問，1表示遍歷。所有結點的task的初始值為1
算法思路：
1.根結點先進棧，task初始化為1
2.出棧，若當前結點的task為0 則訪問當前結點，task為1，則修改task為0，並按想要的遍歷順序入棧左右孩子結點。
例如：若中序遍歷，則先入棧右孩子結點，當前結點，左孩子結點。（其他遍歷順序則改一下入棧順序）
3.直到棧空，停止循環
此算法完整代碼：
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct binode{ //二叉樹結點定義
char data;
struct binode * lchild,*rchild;
}BiNode,*BiTree;
//非遞歸遍歷所要用到的棧
#define MAX 50
typedef struct { // 棧數據定義
BiTree ptr;
int task;
}Datatype;
typedef struct {
Datatype * arr;
int top;
int stacksize;
}SqStack;//順序棧
void InitStack(SqStack *S) //初始化字符棧
{
S->arr = (Datatype*)malloc(sizeof(Datatype)*MAX);
if(S->arr == NULL)
{
printf("初始化失敗....\n");
exit(0);
}
S->top = -1;
S->stacksize = MAX;
}
int Push(SqStack *S,Datatype ch)//進棧(字符棧)
{
Datatype *p;
int select;
if(S->top+1 == S->stacksize) //先判斷棧是否已滿
{
printf("棧的容量已滿，無法進棧");
return 0;
}
S->arr[++S->top] = ch;
return 1;
}
int Pop(SqStack *S,Datatype *ch)//出棧（字符棧）
{
if(S->top < 0)
{
printf("棧為空....\n");
return 0;
}
*ch = S->arr[S->top];
S->top--;
return 1;
}
int GetTopStack(SqStack S,Datatype *ch) //取字符棧頂
{
if(S.top < 0)
{
return 0;
}
*ch = S.arr[S.top];
return 1;
}
int EmptyStack(SqStack S) //判斷棧空
{
if(S.top < 0)
{
return 1;
}
return 0;
}
/******************************棧結束*********************************/
void CreateBitree(BiTree *T) //前序創建二叉樹
{
char ch;
scanf(" %c",&ch);
getchar();
if(ch == '#')
{
*T = NULL;
}
else
{
*T =(BiTree)malloc(sizeof(BiNode));
(*T)->data = ch;
CreateBitree(&((*T)->lchild));
CreateBitree(&((*T)->rchild));
}
}
void View(BiTree T)//非遞歸遍歷 實現不同的遍歷順序修改第一個else語句的結點入棧順序
{
Datatype temp;
BiTree p;
temp.task = 1;
temp.ptr = T;
SqStack S;
InitStack(&S);
if(T == NULL) return ;
Push(&S,temp);
while(!EmptyStack(S))
{
Pop(&S,&temp); //先把根出棧
p = temp.ptr; //記錄根地址
if(temp.task == 0) //task為0 則訪問輸出
{
printf("%c ",temp.ptr->data);
}
else //task為1 則將孩子進棧
{
if(p->rchild) //右孩子進棧
{
temp.task = 1;
temp.ptr = p->rchild;
Push(&S,temp);
}
temp.task = 0; //根的狀態由遍歷改為訪問，然後進棧
temp.ptr = p;
Push(&S,temp);
if(p->lchild) //左孩子進棧
{
temp.ptr = p->lchild;
temp.task = 1;
Push(&S,temp);
}
}
}
printf("\n");
}
int main()//二叉樹創建：a b d # # e # # c f # # g # #
{
BiTree T;
CreateBitree(&T);
printf("中序遍歷為：");
View(T);
return 0;
}
三：層次遍歷
層次遍歷需要使用隊列
算法思路比較結單，即對每個結點按左孩子，右孩子的順序進隊列即可，出隊列時訪問即為層次遍歷。
此處就不贅述算法思路步驟了，直接上代碼。
void DispLayer(BiTree T) //層次遍歷
{
LinkQueue rear; //裝二叉樹的結點地址的隊列
BiTree view = NULL;
InitQueue(&rear);
if(T == NULL)
{
return ;
}
EnQueue(&rear,T); //先將總樹根地址裝進去
while(!EmptyQueue(rear)) //隊列為空則遍歷完畢
{
DeQueue(&rear,&view); //小樹根出隊列
printf("%c ",view->data); //輸出小樹根
if(view->lchild) //小樹根左右孩子存在則入隊列
{
EnQueue(&rear,view->lchild);
}
if(view->rchild)
{
EnQueue(&rear,view->rchild);
}
}
printf("\n");
}
以上即為二叉樹的各種遍歷算法。
二叉樹遍歷（圖解） http://www.linuxidc.com/Linux/2015-07/119765.htm
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
