第7章树和二叉树：树和森林的遍历

7.10 树和森林的遍历

1. 树的遍历

由树结构的定义，可以引出两种次序遍历树的方法：

（1）先根（次序）遍历

先访问树的根结点，然后依次先根遍历根的每棵子树。

以图 7.10.1 所示的树为例，先根遍历，可得树的先根序列为：RADEBCFGHK

（2）后根（次序）遍历

先依次后根遍历每棵子树，然后访问根结点。

以图 7.10.1 所示的树为例，后根遍历，可得树的后根序列为：DEABGHKFCR

2. 森林的遍历

按照森林和树相互递归的定义，森林也有两种遍历方法

（1）先序遍历

若森林非空，按照下述规则遍历：

① 访问森林中第一棵树的根结点；

② 先序遍历第一棵树的根结点的子树森林；

③ 先序遍历除去第一棵树之后剩余的树构成的森林

如图 7.10.2 所示的森林，根据先序遍历，得到森林的先序序列为：ABCDEFGHIJ

（2）中序遍历

若森林为空，则可按下述规则遍历：

① 中序遍历森林中第一棵树的根结点的子树森林；

② 访问第一棵树的根结点；

③ 中序遍历除去第一棵树之后剩余的树构成的森林。

如图 7.10.2 所示的森林，根据中序遍历，得到森林的中序序列为：BCDAFEHJIG

由森林与二叉树之间转换的规则可知，当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。

将图 7.10.2 所示的森林转换为二叉树，如图 7.10.3 所示，对该二叉树分别进行先序和中序遍历，可得和上述相同的序列。

当以二叉链表做树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现。

树、森林的遍历与二叉树的遍历的对应关系：