关于二叉树的遍历

作者：曹忠明，华清远见嵌入式学院讲师。

二叉树遍历就是沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。由于二叉树的递归性质，遍历算法也是递归的。

二叉树的遍历有先序遍历、中序遍历和后序遍历。下面以(图一)中二叉树介绍一下这三种遍历。

(图一) 二叉树

1、先序遍历

先序遍历的遍历规则是（中 前 后），中就是父节点，前就是左孩子，后是右孩子。既先访问当前节点，再访问左子树，最后访问右子树。这个过程是由根节点开始的一个递归的过程。以上面这个二叉树为例。他的遍历过程为：

(1)ABC

(2)A(BD)(CE)

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

算法实现为：

PREORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空树返回*/

printf ( " %c ",r->data ); /*先访问当前节点*/

PREORDER ( r->lchild ); /*再访问该节点的左子树*/

PREORDER ( r->rchild ); /*最后访问该节点右子树*/

}

2、中序遍历

中序遍历的遍历规则是（前 中 后），既访先问左子树，再访问当前节点，最后访问右子树。他的遍历过程为：

(1)BAC

(2)(DB)A(CE)

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

算法实现为：

INORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空树返回*/

INORDER ( r->lchild ); /*先访问该节点的左子树*/

printf ( " %c ",r->data ); /*再访问当前节点*/

INORDER ( r->rchild ); /*最后访问该节点右子树*/

}

3、后序遍历

中序遍历的遍历规则是（前 后 中），既先访问当前节点的左子树，在访问当前节点的右子树，最后访问当前节点。他的遍历过程为：

(1)BCA

(2)(DB)(EC)A

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

算法实现为：

POSTORDER ( bitree *r)

{

if ( r = = NULL )

return ; /*空树返回*/

POSTORDER ( r->lchild ); /*先访问该节点的左子树*/

POSTORDER ( r->rchild ); /*再访问该节点右子树*/

printf ( " %c ",r->data ); /*最后访问当前节点*/

}

由上面一个例子可以看出，这是一个递归的过程，由根节点开始，递归的对各自的孩子结点按规则遍历。

“本文由华清远见http://www.embedu.org/index.htm提供”