森林与树 ■森林( ( forest是零棵或多棵不相交的树的集合 (通常是有序集合) 对于树中的每个结点,其子树组成的集合就是 森林;而加入一个结点作为根,森林就可以转 化成一棵树了。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 森林与树 ◼ 森林(forest)是零棵或多棵不相交的树的集合 （通常是有序集合）。 ◼ 对于树中的每个结点，其子树组成的集合就是 森林；而加入一个结点作为根，森林就可以转 化成一棵树了
树形结构的各种表示法 树形结构在客观世界中是大量存在的,有多种逻辑表 示方法:如树形表示法、凹入表示法、文氏图表示法 、嵌套括号表示法等。 ◇ A C E□口FG ① K L H□ (a)凹入表表示法 (b)文氏图表示法 (A(BDO, D), E), C(, G(K, L), ) 图62树形结构 (c)嵌套括号表示法 的各种表示法 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树形结构的各种表示法 ◼ 树形结构在客观世界中是大量存在的，有多种逻辑表 示方法：如树形表示法、凹入表示法、文氏图表示法 、嵌套括号表示法等。 A B C D E F G H I J K L A B C D E I J F H G K L （a）凹入表表示法 （b）文氏图表示法 (A(B(D(I，J)，E)，C(F，G(K，L)，H))) （c）嵌套括号表示法 图6.2 树形结构 的各种表示法
612森林与二叉树的等价转换 树与二叉树、森林与二叉树之间可以相互转化 ,而且这种转换是一一对应的。 树和森林转化成二叉树后,那么森林或树的相 关操作都可以转换成对二叉树的操作。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 ◼ 树与二叉树、森林与二叉树之间可以相互转化 ，而且这种转换是一一对应的。 ◼ 树和森林转化成二叉树后，那么森林或树的相 关操作都可以转换成对二叉树的操作
612森林与二叉树的等价转换 树和森林到二叉树的转换过程可用连线、切 线、旋转“三步曲”来说明: 口连线:将兄弟结点用线连接起来。 口切线:保留父结点与其第一个子结点的连线, 将父结点到其它子结点的连线切掉。 a旋转:以根为轴,平面向下顺时针方向旋转 定的角度。旋转只是为了调整画面,使得转化 后的二叉树看起来比较规整。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 ◼ 树和森林到二叉树的转换过程可用连线、切 线、旋转“三步曲”来说明： ❑ 连线：将兄弟结点用线连接起来。 ❑ 切线：保留父结点与其第一个子结点的连线， 将父结点到其它子结点的连线切掉。 ❑ 旋转：以根为轴，平面向下顺时针方向旋转一 定的角度。旋转只是为了调整画面，使得转化 后的二叉树看起来比较规整
612森林与二叉树的等价转换 sR①还 母酽糊辨林 图63森林转换为三叉树 十一五”国家級规划教材。张铭,王膳腾蛟,赵海燕,《数据结构与算法》,高教社,B08.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 T1,T2两棵树构成的森林 A B C D E F G H T1 T2 I J K L M (a) T11 T12 T111 T112 T121 A B C D E F G H I J K L M (b) 经过连线、切线处理 图6.3 森林转换为二叉树 A B D C E F G H I J K L M (c) 旋转操作