作者：曹忠明，華清遠見嵌入式學院講師。

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

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

(圖一) 二叉樹

1、先序遍歷

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

(1)ABC

(2)A(BD)(CE)

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

算法實現(xiàn)為：

PREORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

printf ( " %c ",r->data ); /*先訪問當前節(jié)點*/

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

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

}

2、中序遍歷

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

(1)BAC

(2)(DB)A(CE)

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

算法實現(xiàn)為：

INORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

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

printf ( " %c ",r->data ); /*再訪問當前節(jié)點*/

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

}

3、后序遍歷

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

(1)BCA

(2)(DB)(EC)A

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

算法實現(xiàn)為：

POSTORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空樹返回*/

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

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

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

}

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

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