数据结构-5.10.树和森林的遍历

一.树的逻辑结构：

二.树的先根遍历：

1.visit函数代表访问根结点，visit函数函数体可以是遍历，修改数据等；

2.形参R一开始代表整个树的根结点；

3.一个结点可能有多个子树，因此使用while循环检查是否有下一个没有被访问过的子树；

4.上述图片中的树的访问：

先访问根结点A，再访问第二层的B,C,D，B,C,D相当于三个子树的根结点：

以B结点为例，准确来说是在访问以B为根结点的子树，同理此时该访问结果如下：

易知，最终结果为：

访问流程：优先往左走

5.把上述图片里的树转化为二叉树：利用了孩子兄弟表示法

注：对树的先根遍历的结果和把这棵树转换为二叉树后再用先序遍历的结果是一样的

三.树的后根遍历：

1.对上述图片中的树访问结点的结果与过程在图片右边，对各个结点的探索次序如下：

2.上述图片中的树转化为二叉树为：利用了孩子兄弟表示法

注：对树的后根遍历的结果和把这棵树转换为二叉树后再用中序遍历(不是后序遍历)的结果是一样的

四.树的层次遍历：

1.上述图片的树的层次遍历过程：

首先根结点A入队列：

然后根结点A出队列，A的所有孩子入队：

以此类推：

最终队列里的结点都没有孩子，也就不会有结点入队，依次都出来了：

2.树的层次遍历又叫树的广度优先遍历(优先横向遍历)，与之对应的树的先根遍历和后根遍历又叫树的深度优先遍历(优先纵向遍历)：

五.森林的先序遍历：本质利用了递归

1.森林和树是相互递归定义的；

2.以第一颗树为例：

先访问根结点B，B结点下面，以E结点为根结点的树和以F结点为根结点的树又构成了一个小森林，然后是先序遍历第一棵树中根结点的子树森林即遍历以E结点为根结点的树和以F结点为根结点的树，此时递归回到访问森林中第一棵树的根结点，此时的森林是小森林即以E结点为根结点的树和以F结点为根结点的树组成的森林，先访问E结点，同理，再遍历以K结点为根结点和以L结点为根结点的森林，先访问K结点，再然后先序遍历除去第一棵树之后剩余的树构成的森林，即遍历L结点，最后是F结点，其他树同理：

3.为了不出错，可以依次只对森林里的一棵树进行先根遍历，再对其子树进行先序遍历，之后遍历剩下的树，再依次排出完整的序列即可；

4.另一种方法：先把森林转化为对应的二叉树，再对该二叉树进行先序遍历，结果一样即森林的先序遍历效果等同于依次对该森林对应的二叉树的先序遍历：

六.森林的中序遍历：本质利用了递归

森林的中序遍历效果等同于依次对该森林对应的二叉树的中序遍历：

七.总结：

效果等价表：可以把一种转化为另一种进行遍历，结果一样

如树的后根遍历与森林的中序遍历效果一样