普通树的遍历.doc

《普通树的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五节普通树的遍历一、先根次序遍历树    规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。上图先根遍历次序为 rawxdhebfcstimonju    当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。二、后根次序遍历树   规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。   上图后根遍历次序为 whdexafbsmonijtucr    当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。三、森林的遍历   1.先根遍历森林 

2、    若森林非空，则可按下述规则遍历之     ①访问森林中第一棵树的根结点；     ②先根遍历第一棵树中根结点的子树森林；     ③先根遍历其余树构成的森林；    若对下图的森林进行先根遍历，则得到森林的先根序列为ABDCEFGHJI。森林的先根遍历即为其对应的二叉树的前序遍历。  2.后根遍历森林    若森林非空，则可按下述规则遍历之     ①后根遍历森林中第一棵树的根结点的子树森林；     ②访问第一棵树的根结点；     ③后根遍历其余树构成的森林；   若对上图(a)中的森林进行先根遍历，则得到森林的后根

3、序列为BCDAFEHJIG。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。