第五章 树于二叉树 七、树和森林的遍历（广度优先遍历、深度优先遍历）

1、树的遍历

        树是一种递归定义的数据结构，所以我们可以使用递归实现遍历。

（1）先根遍历（最先访问根节点）（深度优先遍历）

1.使用孩子兄弟表示法将其转化为二叉树的形式。

2.使用先序遍历二叉树。

3.得到森林的遍历序列。

（2）后根遍历（深度优先遍历）

1.使用孩子兄弟表示法将其转化为二叉树的形式。

2.使用中序序遍历二叉树。

3.得到森林的遍历序列。

（3）层序遍历（广度优先遍历）

1、效果和二叉树的层序遍历一致。

2、从根节点开始遍历，A入队，访问A。

3、A的孩子结点（B、C、D）入队。

4、访问B，B的结点E、F入队。

5、依此类推遍历完所有的结点。

2、森林的遍历

（1）先序遍历

1、先把森林转化为与之对应的二叉树。

2、对二叉树进行先序遍历，得到也就是森林的先序遍历序列

（2）中序遍历

1、先把森林转化为与之对应的二叉树。

2、对二叉树进行中序遍历，得到也就是森林的中序遍历序列