Question

数据结构——树和森林的遍历方法

Answer 1

1、树的遍历的定义 ：以某种方式访问树中的每一个结点，且仅访问一次。 树的遍历主要有先根遍历和后根遍历。
2、(1)先根遍历： 若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
(2)后根遍历： 若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。
Example one：

根据以上这幅图有如下结果：

注意到我们并没有定义一般树的中根遍历，因为子结点该怎么分两部分并没有定义，所以只定义先、后根。
Example two:

1、前序遍历
前序遍历的定义为：
（1）访问森林中第一棵树的根结点；
（2）前序遍历第一棵树的根结点的子树；
（3）前序遍历去掉第一棵树后的子森林。

2、中序遍历
中序遍历的定义为：
（1）中序遍历第一棵树的根结点的子树；
（2）访问森林中第一棵树的根结点；
（3）中序遍历去掉第一棵树后的子森林。

森林与二叉树的转换

树转化为二叉树：
⑴ 加虚线（或者粗实线）。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。
⑵ 去连线。除最左的第一个子结点（长子节点）外，父结点与所有其它子结点的连线都去掉。

森林转换成二叉树：
当一般的树转换成二叉树后，二叉树的右子树必为空。若把森林中的第二棵树(转换成二叉树后)的根结点作为第一棵树(二叉树)的根结点的兄弟结点，则可导出森林转换成二叉树的转换步骤如下：
（1）、把每棵树转换为二叉树
（2）、按给出的森林中树的次序，第一棵树不动，从第二棵树开始，依次把后一棵树的根结点作为前一棵二叉树的根结点的右孩子，用线连起来，当所有的二叉树连接起来后，就得到了由森林转换来的二叉树。