新闻  |   论坛  |   博客  |   在线研讨会
关于二叉树的遍历
mayer | 2009-09-08 20:08:38    阅读:2876   发布文章
关于二叉树的遍历

 

 

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

二叉树遍历就是沿某条搜索路径周游二叉树,对树中的每一个节点访问一次且仅访问一次。由于二叉树的递归性质,遍历算法也是递归的。
二叉树的遍历有先序遍历、中序遍历和后序遍历。下面以(图一)中二叉树介绍一下这三种遍历。

(图一) 二叉树

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 );                     /*最后访问当前节点*/
        }

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

参与讨论
登录后参与讨论
推荐文章
最近访客