最后我们再谈一谈关于树和森林的遍历问题。

    树的遍历分为两种方式。

    1.一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。

    2.另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。 比如图6-11-4中右下方的树，它的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。


    森林的遍历也分为两种方式：

    1.前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。 比如图6-11-5下面三棵树的森林，前序遍历序列的结果就是ABCDEFGHJI。

    2.后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。 比如图6-11-5下面三棵树的森林，后序遍历序列的结果就是BCDAFEJHIG。

    可如果我们对图6-11-5的左侧二叉树进行分析就会发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。

    这也就告诉我们，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。这其实也就证实，我们找到了对树和森林这种复杂问题的简单解决办法。