擴展先序遍歷內容

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

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

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

(1)訪問結點本身(N)，

(2)遍歷該結點的左子樹(L)，

(3)遍歷該結點的右子樹(R)。

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

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

(1)遍歷該結點的左子樹(L)，

(2)訪問結點本身(N)，

(3)遍歷該結點的右子樹(R)。

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

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

(1)遍歷該結點的左子樹(L)，

(2)遍歷該結點的右子樹(R)。

(3)訪問結點本身(N)，

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

根據訪問結點操作發(fā)生位置命名：

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

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

② LNR:中序遍歷(InorderTraversal)

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

③ LRN:后序遍歷(PostorderTraversal)

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

用二叉鏈表做為存儲結構，先序遍歷算法可描述為:

void InOrder(BinTree T)

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

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

② printf("%c"，T->data); // 訪問結點 ③ 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));//向內存申請節(jié)點空間

(*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 . . 運行結果:

圖二:

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

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

運行結果:

樹中節(jié)點結構為:

核心代碼:

· Preorder前序遍歷--訪問結點的操作發(fā)生在遍歷其左右子樹之前

· Inorder中序遍歷--訪問結點的操作發(fā)生在遍歷其左右子樹之間

· Postorder后序遍歷--訪問結點的操作發(fā)生在遍歷其左右子樹之后

· Level order層次遍歷--按每一層的節(jié)點，從左到右逐次訪問

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的系統(tǒng)的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時，若按訪問結點的先后次序將結點排列起來，就可分別得到樹中所有結點的前序列表，中序列表和后序列表。相應的結點次序分別稱為結點的前序、中序和后序。

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

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

§ 如果T是一棵單結點樹，那么對T進行前序遍歷、中序遍歷和后序遍歷都只訪問這個結點。這個結點本身就是要得到的相應列表。

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

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

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

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