77树与二叉树的转换 孩子兄弟 表示法 讨论1:树如何转为二叉树? 转换步骤 step1:将树中同一结点的兄弟相连; 加线 step2:保留结点的最左孩子连线, 删除其它孩子连线; 抹线 step3:将同一孩子的连线绕左孩子 旋转45度角。 旋转
1 7.7 树与二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟 表示法 step2: 保留结点的最左孩子连线， 删除其它孩子连线； step3: 将同一孩子的连线绕左孩子 旋转45度角
树转二叉树举例 方法:加线抹线旋转 特点是? 根结点没有右孩子! 兄弟相连 长兄为父孩子靠左 b d d g f)(
2 方法：加线—抹线—旋转 a b e i d f g h c 树转二叉树举例： a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！
讨论2:二叉树怎样还原为树? 要点:逆操作,把所有右孩子变为兄弟! b (d) d g g h
3 讨论2：二叉树怎样还原为树？ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f g h c i
讨论3:森林如何转为二叉树? 即F={TT2,…,Tm}={ root, LB,RB} 法一 ①各森林先各自转为二叉树; ②依次连到前一个二叉树的右子树上 法二:森林直接变兄弟,再转为二叉树 (参见教材P138图6.17,两种方法都有转换示意图) 法一和法二得到的二叉树是完 全相同的、惟一的
4 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 讨论3：森林如何转为二叉树？ 即F={T1 , T2 , …,Tm} B={root, LB, RB} 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完 全相同的、惟一的
森林转二叉树举例: 用法二,森林直接变兄弟,再转为二叉树) )D(F)(田 兄弟相连长兄为父① 头树为根孩子靠左
5 A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 森林转二叉树举例： （用法二，森林直接变兄弟，再转为二叉树） 兄弟相连 长兄为父 头树为根 孩子靠左 A