6.4树和森林 6.4.1树和森林与二叉树的转换 6.4.2树和森林的存储方式 6.4.3树和森林的遍历
6 6.4 树和森林 6.4.1 树和森林与二叉树的转换 6.4.2 树和森林的存储方式 6.4.3 树和森林的遍历
6.4.1 树和森林与二叉树的转换 孩子—兄弟 表示法 讨论1： 树如何转为二叉树？ 转换步骤： step1:将树中同一结点的兄弟相连； 加线 step2:保留结点的最左孩子连线 删除其它孩子连线； 抹线 step3:将同一孩子的连线绕左孩子 旋转45度角。 旋转 7
7 6.4.1 树和森林与二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟 表示法 step2: 保留结点的最左孩子连线， 删除其它孩子连线； step3: 将同一孩子的连线绕左孩子 旋转45度角
树转二叉树举例： 特点是？ 方法：加线—抹线一旋转 根结点没有右孩子！ 兄弟相连 长兄为父 孩子靠左 a C e 8
8 方法：加线—抹线—旋转 a b e i d f g h c 树转二叉树举例： a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！
讨论2：二叉树怎样还原为树？ 要点：逆操作，把所有右孩子变为兄弟！ a b e 9
9 讨论2：二叉树怎样还原为树？ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f g h c i