普通树的遍历
11-11
第五节
普通树的遍历
一、先根次序遍历树
规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。
上图先根遍历次序为 r a w x d h e b f c s t i m o n j u
当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。
二、后根次序遍历树
规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。
上图后根遍历次序为 w h d e x a f b s m o n i j t u c r
当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。
三、森林的遍历
1. 先根遍历森林
若森林非空，则可按下述规则遍历之
① 访问森林中第一棵树的根结点；
② 先根遍历第一棵树中根结点的子树森林；
③ 先根遍历其余树构成的森林；
若对下图的森林进行先根遍历，则得到森林的先根序列为A B D C E F G H J I。森林的先根遍历即为其对应的二叉树的前序遍历。
2. 后根遍历森林
若森林非空，则可按下述规则遍历之
① 后根遍历森林中第一棵树的根结点的子树森林；
② 访问第一棵树的根结点；
③ 后根遍历其余树构成的森林；
若对上图(a)中的森林进行先根遍历，则得到森林的后根序列为B C D A F E H J I G 。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。