森林、树和二叉树的转换.ppt

第六章 树和二叉树 本章主要内容 3.树、森林和二叉树的转换 树和森林的存储表示复杂，实施具体的算法很困难，而二叉树的算法的比较丰富，牵涉到树和森林的问题，一般转换成对应的二叉树，通过二叉树来解决 树转换成二叉树 将一棵树转换为二叉树的方法是： 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明 4.树和森林的遍历 树的遍历：有先根遍历和后根遍历两种 思考：树的遍历有没有中根遍历？ * 一、树的基本概念 二、二叉树 三、二叉树的遍历 三、线索二叉树 四、树和森林 六、哈夫曼树 七、本章主要要求 树转换成二叉树 森林转换成二叉树 二叉树转换成树 二叉树转换成森林 转换过程示意图： 先根遍历： 访问根结点 按照从左到右的顺序先根遍历根结点的每一棵子树 后根遍历： 按照从左到右的顺序后根遍历根结点的每一棵子树 访问根结点 遍历的结果 ？ 先根遍历结果： A B E F I G 先根遍历：先访问树的根结点，然后依次先根遍历根 的每棵子树 D A B D E F G I 后根遍历：先依次后根遍历每棵子树，然后访问根结点 A B D E F G I 后根遍历： E I F G B D A A B C D E F G H I J K L M N O 先根遍历： 后根遍历： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O [例] 树： 对应二叉树： 先序遍历： A B E F I G C D H J K L N O M 中序遍历： E I F G B C J K N O L M H D A 树的先根遍历与对应二叉树的先序遍历结果相同！ 树的后根遍历与对应二叉树的中序遍历结果相同！