關(guān)于二叉樹(shù)的遍歷

作者：曹忠明，華清遠(yuǎn)見(jiàn)嵌入式學(xué)院講師。

二叉樹(shù)遍歷就是沿某條搜索路徑周游二叉樹(shù)，對(duì)樹(shù)中的每一個(gè)節(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。由于二叉樹(shù)的遞歸性質(zhì)，遍歷算法也是遞歸的。

二叉樹(shù)的遍歷有先序遍歷、中序遍歷和后序遍歷。下面以(圖一)中二叉樹(shù)介紹一下這三種遍歷。

(圖一) 二叉樹(shù)

1、先序遍歷

先序遍歷的遍歷規(guī)則是（中 前 后），中就是父節(jié)點(diǎn)，前就是左孩子，后是右孩子。既先訪問(wèn)當(dāng)前節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。這個(gè)過(guò)程是由根節(jié)點(diǎn)開(kāi)始的一個(gè)遞歸的過(guò)程。以上面這個(gè)二叉樹(shù)為例。他的遍歷過(guò)程為：

(1)ABC

(2)A(BD)(CE)

(3)A(B(DF))(C(EGH))

算法實(shí)現(xiàn)為：

PREORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹(shù)返回*/

printf ( " %c ",r->data ); /*先訪問(wèn)當(dāng)前節(jié)點(diǎn)*/

PREORDER ( r->lchild ); /*再訪問(wèn)該節(jié)點(diǎn)的左子樹(shù)*/

PREORDER ( r->rchild ); /*最后訪問(wèn)該節(jié)點(diǎn)右子樹(shù)*/

}

2、中序遍歷

中序遍歷的遍歷規(guī)則是（前 中 后），既訪先問(wèn)左子樹(shù)，再訪問(wèn)當(dāng)前節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。他的遍歷過(guò)程為：

(1)BAC

(2)(DB)A(CE)

(3)((DF)B)A(C(GEH)

算法實(shí)現(xiàn)為：

INORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹(shù)返回*/

INORDER ( r->lchild ); /*先訪問(wèn)該節(jié)點(diǎn)的左子樹(shù)*/

printf ( " %c ",r->data ); /*再訪問(wèn)當(dāng)前節(jié)點(diǎn)*/

INORDER ( r->rchild ); /*最后訪問(wèn)該節(jié)點(diǎn)右子樹(shù)*/

}

3、后序遍歷

中序遍歷的遍歷規(guī)則是（前 后 中），既先訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)，在訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子樹(shù)，最后訪問(wèn)當(dāng)前節(jié)點(diǎn)。他的遍歷過(guò)程為：

(1)BCA

(2)(DB)(EC)A

(3)((FD)B)((GHE)C)A

算法實(shí)現(xiàn)為：

POSTORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹(shù)返回*/

POSTORDER ( r->lchild ); /*先訪問(wèn)該節(jié)點(diǎn)的左子樹(shù)*/

POSTORDER ( r->rchild ); /*再訪問(wèn)該節(jié)點(diǎn)右子樹(shù)*/

printf ( " %c ",r->data ); /*最后訪問(wèn)當(dāng)前節(jié)點(diǎn)*/

}

由上面一個(gè)例子可以看出，這是一個(gè)遞歸的過(guò)程，由根節(jié)點(diǎn)開(kāi)始，遞歸的對(duì)各自的孩子結(jié)點(diǎn)按規(guī)則遍歷。

“本文由華清遠(yuǎn)見(jiàn)http://www.embedu.org/index.htm提供”