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

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