数据结构与算法 (25).pdf

《数据结构与算法 (25).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (25).pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章树和森林8.1 树和森林的基本概念8.2 树的存储8.3 树和二叉树8.4 树的遍历第8章 树和森林8.4.1 树的遍历 8.4.2 森林的遍历8.4 树(森林)的遍历3B C DE F GHI J K1 1森林中第一棵树的根结森林中第一棵树的根结点；点；2 2森林中第一棵树的子树森林中第一棵树的子树森林；森林；3 3森林中其它树构成的森林。森林中其它树构成的森林。森林由三部分构成：森林由三部分构成：1.森林的组成部分森林的组成部分4先序遍历：若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历：（后根遍历

2、森林中每棵树）若森林为空，返回；中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。2.森林的遍历森林的遍历5例子：例子：以以先序先序遍历方式访问如图所示的遍历方式访问如图所示的森林森林。解：解：A-B-C-D-E-F-G-H-I-J-K-L-M A A B B C C D D E E F F G G H H I I J J K K L L M M 例子：例子：以以中序中序遍历方式访问如图所示的遍历方式访问如图所示的森林森林。解：解：B-A-E-F-G-D-C-I-K-L-M-J-H A A B B C C D D E E F F G G J J K K L L M M H H I I 6讨论：若采用“先转换，后遍历”方式，结果是否相同？ABCDEFGHJI先序序列：中序序列：A B C D E F G H I JB C D A F E H J I G结论：森林及其对应二叉树的先序和中序遍历序列相同。ABCDEFGHJI7先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历对树和森林的遍历可以调用二叉树对应的遍历算法对树和森林的遍历可以调用二叉树对应的遍历算法3.树、森林和二叉树遍历的对应关系8The endThe end