遍历二叉树

傷城~ 2022-06-05 08:11 351阅读 0赞

**遍历二叉树**

今天我们学习了二叉树，现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法：先序、中序和后序。

根据二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点、左子树和右子树。因此若能依次遍历这三部分，便是遍历了整个二叉树。假如用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6钟遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称之为先序遍历、中序遍历和后序遍历。下面我就分别来讲讲这三种遍历的规则吧！

一、先序遍历：

先序遍历的规则为：1.首先访问根结点；2.然后遍历左子树；3.最后遍历右子树。我们可以用一句口诀来帮助我们的记忆：先根再左后右。我知道只是这样口头说的话可能很难理解，我们用一个例子来解释一下吧：

![20171122112502882][]

如上图所示：根据口诀：先根意思是先访问根结点得到第一个是A；再左，再访问左子树，访问到左子树时继续用口诀得到左子树的序列为BDE，然后再访问E的子树H；后右，最后访问右子树，也继续用那个口诀，得到右子树的序列为CFG；把所有遍历的序列结合起来就可以得到此二叉树的先序遍历结果：ABDEHCFG。先序遍历的代码实现如下：

void PreOrder(PBTNode pHead) {
        if (NULL == pHead) {
            return;
        }
        printf("%C ",pHead->num);  //先访问根结点
        PreOrder(pHead->leftNode);  //再遍历左子树
        PreOrder(pHead->rightNode); //最后遍历右子树
    }

二、中序遍历：

中序遍历的规则为：1.首先遍历左子树；2.然后访问根结点；最后遍历右子树；同样可以用一句口诀可以概括：先左再根后右，我们依然以上图为例：先左，首先遍历左子树，得到序列DBE，因为B的右子树E的下面还有一个子树，但是是右子树，所以A的左子树的序列为DBEH；再根，然后再访问根结点；后右，最后再访问右子树，得到序列FCG；把所有遍历的序列结合起来就得到此二叉树的中序遍历结果：DBEHAFCG。中序遍历的代码实现如下：

void InOrder(PBTNode pHead){
        if (NULL == pHead) {
            return;
        }
            InOrder(pHead->leftNode);//先遍历左子树
            printf("%C ", pHead->num);//再访问根结点
            InOrder(pHead->rightNode);//最后遍历右子树
    }

三、后序遍历：

后序遍历的规则为：1.首先遍历左子树；2.然后遍历右子树；3.最后访问根结点；依然用一句口诀：先左再右后根。我们还以上图为例用后序遍历的方法来遍历二叉树：先左，首先遍历左子树，得到序列DEB，因为E的子树为右子树，所以A的左子树的序列应该为DHEB；再右，然后再来遍历右子树，得到序列FGC；后根，最后再访问根结点；所以把所有遍历的序列结合起来就得到此二叉树的后序遍历结果：DHEBFGCA。后序遍历的代码实现如下：

void PostOrder(PBTNode pHead) {
        if (NULL == pHead) {
            return;
        }
        PostOrder(pHead->leftNode);//先遍历左子树
        PostOrder(pHead->rightNode);//再遍历右子树
        printf("%C ", pHead->num);//最后访问根结点
    }

这里需要说明一点的是由二叉树的先序序列和中序序列，或由其后序序列和中序序列都能唯一地确定一棵二叉树。下面我依然用一个例题来解释一下：

例：

设一棵二叉树的先序序列为：ABDFCEGH，中序序列为：BFDAGEHC

1.画出这棵二叉树。

2.用后序遍历来遍历这棵二叉树。

这道题的解法为：首先我们可以根据先序序列来确定根结点A，然后根据中序序列来确定A的左子树BFD和右子树GEHC然后用同样的方法可以知道A的左子树和右子树的结构，最后可以得到如下图所示的二叉树：

![Center][]

下面我们再来看看第二小题：用后序遍历来遍历这棵二叉树，同样记住这个口诀：先左再右后根，我们很容易便可以得出这棵二叉树的后序遍历序列为：FDBGHECA。

以上就是我对遍历二叉树的一些理解，如果有什么不对的地方欢迎指正！！！

[20171122112502882]: /images/20220605/0c35f3ba3ce4484596adf9aa0d58f897.png
[Center]: /images/20220605/d2b2b5843c4d4fa286e5648d51109dd1.png