|
设树T如下图所示结点R是根根的子树从左到右依次为T T …T k 树T的前序遍历定义 若树T非空则 ①访问根结点R; ②依次前序遍历根R的各子树T T …T k 树的后序遍历定义 若树T非空则 ①依次后序遍历根T的各子树T l T …T k ; ②访问根结点R 【例】对下面的(a)图中的树进行前序遍历和后序遍历得到的前序序列和后序序列分别是ABCDE和BDCEA 注意 ① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树 ② 后序遍历树恰好等价于中序遍历该树对应的二叉树 森林的两种遍历方法 前序遍历森林 若森林非空则 ①访问森林中第一棵树的根结点; ②前序遍历第一棵树中根结点的各子树所构成的森林 ③前序遍历除第一棵树外其它树构成的森林 后序遍历森林 若森林非空则: ①后序遍历森林中第一棵树的根结点的各子树所构成的森林; ②访问第一棵树的根结点; ③后序遍历除第一棵树外其它树构成的森林 注意 ① 前序遍历森林等同于前序遍历该森林对应的二叉树 ② 后序遍历森林等同于中序遍历该森林对应的二叉树 【例】对下面(a)图中所示的森林进行前序遍历和后序遍历则得到该森林的前序序列和后序序列分别为ABCDEFICJH和 BDCAIFJGHE而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFICJH和BDCAIFJGHE ③ 当用二叉链表作树和森林的存储结构时树和森林的前序遍历和后遍历可用二叉树的前序遍历和中序遍历算法来实现 |
