由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。先序、中序、后序遍歷二叉樹的區(qū)別在于：根節(jié)點(diǎn)被訪問的先后。也就是每種遍歷方式的按自己獨(dú)特的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。本文我們主要來探討一下二叉樹中序遍歷。

先訪問根節(jié)點(diǎn)再訪問其左右子樹，這是先序遍歷；按照左子樹、根節(jié)點(diǎn)、右子樹的順序訪問的方式便為中序遍歷；那么后序遍歷，自然就是先訪問左右子樹，再訪問根節(jié)點(diǎn)了。二叉樹的三種遍歷方式其實(shí)思想都是一樣的，掌握了一種就可以舉一反三。

中序遍歷遞歸寫法很簡單，就是直接按照定義來實(shí)現(xiàn)就 OK 了。

status Mid_view_root(BTpoint T,status (*view)(TElemType e)) ???//中序遍歷的遞歸寫法
{
??if(T!=NULL)
??{
????if(Mid_view_root(T->lchild,view))
??????if(Print_tree_data(T->data)) ???
????????if(Mid_view_root(T->rchild,view))
??????????return OK;
????return ERROR;
??}
??else return OK;
}

那么中序遍歷的非遞歸形式該怎么寫呢？

首先，中序遍歷（非遞歸）得用到「 棧 」這種數(shù)據(jù)結(jié)構(gòu)。棧的特點(diǎn)是：先進(jìn)后出，我們也正是利用了這個(gè)特點(diǎn)來實(shí)現(xiàn)中序遍歷的非遞歸形式。

那么，這又是如何實(shí)現(xiàn)的呢？

先遍歷二叉樹的根節(jié)點(diǎn)的左子樹到最后一個(gè)左子樹節(jié)點(diǎn)，按順序?qū)⑺鼈內(nèi)霔＃怀鰲２⑤敵鲎詈笠粋€(gè)左子樹節(jié)點(diǎn)；讀取該節(jié)點(diǎn)的右子樹，重復(fù)上述操作。如果一個(gè)結(jié)點(diǎn)的左右子樹都被訪問過，則退回到該節(jié)點(diǎn)的父結(jié)點(diǎn)，將其輸出，讀取右子樹。如此循環(huán)，最后就能得到中序遍歷（非遞歸）的輸出了。

假設(shè)有這么一棵二叉樹：

首先，結(jié)點(diǎn)「 1 」進(jìn)棧，因?yàn)樗凶笞訕洌x取左子樹到最后一個(gè)左子樹結(jié)點(diǎn)「 4 」，在這過程中將它們按序進(jìn)棧，這時(shí)棧中的元素為「1， 2， 4 」。「 4 」出棧，讀取它的右子樹，重復(fù)上述操作，得到棧中元素為「 1， 2， 7 」。「 7 」出棧，因?yàn)榻Y(jié)點(diǎn)「 7 」沒有右子樹，可視為已訪問過其右子樹，退回到結(jié)點(diǎn)「 7 」的父結(jié)點(diǎn)即結(jié)點(diǎn)「 4 」。因?yàn)椤?4 」的左右子樹都已被訪問過，退回到其父結(jié)點(diǎn)「 2 」，「 2 」出棧，讀取其右子樹。

代碼實(shí)現(xiàn)有兩種方式。一種是比較復(fù)雜的，調(diào)用了棧的幾個(gè)函數(shù)來實(shí)現(xiàn)該功能。

//中序遍歷二叉排序樹(非遞歸）
Status InOrderTraverse2(BiTree T)
{
????SqStack S;
????BiTree p;
????p=(BiTree)malloc(sizeof(BiTNode));
????InitStack(S); ?// 構(gòu)建一個(gè)空棧
???p=T;
????while(p||!StackEmpty(S)) ??// StackEmpty( S ) ?判斷棧是否為空
???{
????????if(p)
????????{
????????????Push(S,p); ???????// 入棧
???????????p=p->lchild;
????????}
????????else
????????{
????????????Pop(S,p); ??????// 出棧
???????????if(!PrintElement(p->data)) ????// 輸出結(jié)點(diǎn)的值
???????????????return ERROR;
????????????p=p->rchild;
????????}
????}
????printf("\n");
????return OK;
}

第二種就很簡潔了，不需要那么多個(gè)函數(shù)，幾乎與我們的思路一模一樣：

//中序遍歷序列(非遞歸算法)
status M_nonrecursive(BTpoint T,Stack S) ???????
{
??while(T!=NULL||S.base!=S.top)
??{
????while(T!=NULL)
????{
??????*S.top++=T;
??????T=T->lchild;
????}
????T=*--S.top;
????Print_tree_data(T->data); ??// 輸出結(jié)點(diǎn)的值
???T=T->rchild;
??}
??return OK;
}

至于二叉樹前序和后序遍歷，基本上很容易就能推導(dǎo)出來了，因?yàn)槎弑闅v方式和二叉樹中序遍歷有許多的共通之處，在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中，對二叉樹遍歷所有方式有一個(gè)完整的描述和整理，感興趣的小伙伴可以前去觀看，收集這些優(yōu)秀的資料，化為己用，我們也能夠?qū)崿F(xiàn)知識積累的跨越。