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

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

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

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

(圖一) 二叉樹

1、先序遍歷

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

(1)ABC

(2)A(BD)(CE)

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

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

PREORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

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

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

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

}

2、中序遍歷

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

(1)BAC

(2)(DB)A(CE)

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

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

INORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

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

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

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

}

3、后序遍歷

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

(1)BCA

(2)(DB)(EC)A

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

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

POSTORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

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

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

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

}

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

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