中序遍歷

樹中節(jié)點(diǎn)結(jié)構(gòu)為:

核心代碼:

在使用擴(kuò)展先序遍歷創(chuàng)建二叉樹時(shí)，首先要根據(jù)一棵二叉樹寫出它的先序遍歷序列，然后根據(jù)圖中各個(gè)節(jié)點(diǎn)左右孩子的 狀況進(jìn)行加點(diǎn)遍歷，凡是沒有左右孩子的節(jié)點(diǎn)，遍歷到它的左右孩子是都用"."表示它的左右孩子，注意這里面的"."只是用來表示它的父節(jié)點(diǎn)沒有它這個(gè)左孩子或右孩子，并不表示節(jié)點(diǎn)，所以在遍歷過程中應(yīng)該訪問到"."就結(jié)束了，不能再沿著"."繼續(xù)遍歷。

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問 題。 遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。本節(jié)主要講二叉樹中遍歷過程，遍歷方法，重點(diǎn)介紹擴(kuò)展先序遍歷序列以及利用此序列創(chuàng)建二叉樹的過程，順便比較一下各種遍歷方法的異同和應(yīng)用。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)訪問結(jié)點(diǎn)本身(N)，

(2)遍歷該結(jié)點(diǎn)的左子樹(L)，

(3)遍歷該結(jié)點(diǎn)的右子樹(R)。

根據(jù)遍歷的原則:先左后右，對(duì)于先序遍歷，顧名思義就是先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹，

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)遍歷該結(jié)點(diǎn)的左子樹(L)，

(2)訪問結(jié)點(diǎn)本身(N)，

(3)遍歷該結(jié)點(diǎn)的右子樹(R)。

對(duì)于中序遍歷，就是先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹;

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)遍歷該結(jié)點(diǎn)的左子樹(L)，

(2)遍歷該結(jié)點(diǎn)的右子樹(R)。

(3)訪問結(jié)點(diǎn)本身(N)，

對(duì)于后序遍歷，就是先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn);

根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名：

① NLR:前序遍歷(PreorderTraversal亦稱(先序遍歷))

--訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

② LNR:中序遍歷(InorderTraversal)

--訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)。

③ LRN:后序遍歷(PostorderTraversal)

--訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

用二叉鏈表做為存儲(chǔ)結(jié)構(gòu)，先序遍歷算法可描述為:

void InOrder(BinTree T)

{ //算法里①~⑥是為了說明執(zhí)行過程加入的標(biāo)號(hào)

① if(T) { // 如果二叉樹非空

② printf("%c"，T->data); // 訪問結(jié)點(diǎn) ③ InOrder(T->lchild); ④ InOrder(T->rchild); ⑤ }

⑥ } // InOrder

void createBiTree(BiTree *bt){

char ch;

ch = getchar();

if(ch == '.')

*bt = NULL;

else{

*bt = (BiTree)malloc(sizeof(BiTNode));//向內(nèi)存申請(qǐng)節(jié)點(diǎn)空間

(*bt)->data = ch;

createBiTree(&((*bt)->LChild));//生成左子樹

createBiTree(&((*bt)->RChild));//生成右子樹

}

}/*createBiTree*/

/*==================打印二叉樹=============*/

void printTree(BiTree bt,int nLayer){

int i;

if(bt == NULL)

return ;

printTree(bt ->RChild,nLayer+1);

for(i=0;i<nLayer;i++)

printf(" ");

printf("%c\n",bt->data);

printTree(bt->LChild,nLayer+1);

}

圖一:

(a)1 2 4 . . 6 . . 3 . 5 . 7 . 8 . .

(b)1 2 4 . . 5 . . 3 6 . . 7 . . 運(yùn)行結(jié)果:

圖二:

(a)7 3 1 . . 2 . . 9 . 10 . 8 . 4 . .

(b)7 3 1 . . 5 4 . . . 11 10 . . 15 . .

運(yùn)行結(jié)果:

樹的遍歷是樹的一種重要的運(yùn)算。所謂遍歷是指對(duì)樹中所有結(jié)點(diǎn)的系統(tǒng)的訪問，即依次對(duì)樹中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時(shí)，若按訪問結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來，就可分別得到樹中所有結(jié)點(diǎn)的前序列表，中序列表和后序列表。相應(yīng)的結(jié)點(diǎn)次序分別稱為結(jié)點(diǎn)的前序、中序和后序。

樹的這3種遍歷方式可遞歸地定義如下:

§ 如果T是一棵空樹，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都是空操作，得到的列表為空表。

§ 如果T是一棵單結(jié)點(diǎn)樹，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都只訪問這個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)本身就是要得到的相應(yīng)列表。

§ 否則，設(shè)T如圖6所示，它以n為樹根，樹根的子樹從左到右依次為T1,T2,..,Tk，那么有:

§ 對(duì)T進(jìn)行前序遍歷是先訪問樹根n,然后依次前序遍歷T1,T2,..,Tk。

§ 對(duì)T進(jìn)行中序遍歷是先中序遍歷T1，然后訪問樹根n，接著依次對(duì)T2,T2,..,Tk進(jìn)行中序遍歷。

§ 對(duì)T進(jìn)行后序遍歷是先依次對(duì)T1,T2,..,Tk進(jìn)行后序遍歷，最后訪問樹根n。