《森林、树和二叉树的转换ppt课件.ppt》由会员分享，可在线阅读，更多相关《森林、树和二叉树的转换ppt课件.ppt（9页珍藏版）》请在三一办公上搜索。
1、第六章 树和二叉树,本章主要内容,一、树的基本概念二、二叉树三、二叉树的遍历三、线索二叉树四、树和森林六、哈夫曼树七、本章主要要求,3.树、森林和二叉树的转换,树和森林的存储表示复杂，实施具体的算法很困难，而二叉树的算法的比较丰富，牵涉到树和森林的问题，一般转换成对应的二叉树，通过二叉树来解决,树转换成二叉树森林转换成二叉树二叉树转换成树二叉树转换成森林,树转换成二叉树,将一棵树转换为二叉树的方法是：树中所有相邻兄弟之间加一条连线。对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明,转换过程示
2、意图：,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,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,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,树的先根遍历与对应二叉树的先序遍历结果相同！树的后根遍历与对应二叉树的中序遍历结果相同！,
