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