K叉树及知识点总结 0.5小时 4.重点和难点 (1)掌握树与二叉树的联系、区别与转换。 (2)掌握树的链式存储方法和顺序存储方法,及各自的优缺点。 5.授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是树这一章的重点和难点内容的讲授注意事项 (1)森林与二叉树的等价转换 树与二叉树、森林与二叉树之间可以相互转化,而且这种转换是一一对应的。树和森林 转化成二叉树后,那么森林或树的相关操作都可以转换成对二叉树的操作。 树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明 连线:将兄弟结点用线连接起来。 切线:保留父结点与其第一个子结点的连线,将父结点到其它子结点的连线切掉。 旋转:以根为轴,平面向下顺时针方向旋转一定的角度。旋转只是为了调整画面,使得 转化后的二叉树看起来比较规整。 而二叉树转换为树或森林,就是上面三步曲的逆操作。 这种转换过程应多举例,并且用图片展示转换过程。 (2)父指针表示法 由于树中每一个结点的父指针是唯一的,所以父指针表示法可以唯一地表示任何一棵 树。在这种表示方法下,寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点 出发找出一条向上延伸到达其祖先的路径,即从一个结点到其父亲结点,再到其祖父结点等 等。求祖先路径所需要的时间正比于路径上的结点个数,因此父指针表示法对于求树根结点 的运算非常方便。 合并两棵树的操作也非常简单,只需要将一棵树的树根表示为另一棵树的子结点,也就 是设置父指针值即可。 父指针表示求结点的子结点和兄弟结点就比较麻烦,需要查询整个结构。另外,这种存 储结构中没有表示出结点之间的左右次序。父指针表示法适合于无序树的情况,而且只适合 于查询结点的根和合并树等操作,其主要优点是节省存储空间而且操作便捷。 (3)等价类和并查集 父指针表示法的一个重要应用是实现并查集( Union/ Find)。并查集是一种特殊的集合,2 K 叉树及知识点总结 0.5 小时 4．重点和难点 （1） 掌握树与二叉树的联系、区别与转换。 （2） 掌握树的链式存储方法和顺序存储方法，及各自的优缺点。 5．授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是树这一章的重点和难点内容的讲授注意事项 (1) 森林与二叉树的等价转换 树与二叉树、森林与二叉树之间可以相互转化，而且这种转换是一一对应的。树和森林 转化成二叉树后，那么森林或树的相关操作都可以转换成对二叉树的操作。 树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明： 连线：将兄弟结点用线连接起来。 切线：保留父结点与其第一个子结点的连线，将父结点到其它子结点的连线切掉。 旋转：以根为轴，平面向下顺时针方向旋转一定的角度。旋转只是为了调整画面，使得 转化后的二叉树看起来比较规整。 而二叉树转换为树或森林，就是上面三步曲的逆操作。 这种转换过程应多举例，并且用图片展示转换过程。 (2) 父指针表示法 由于树中每一个结点的父指针是唯一的，所以父指针表示法可以唯一地表示任何一棵 树。在这种表示方法下，寻找一个结点的父结点只需要 O(1)时间。在树中可以从一个结点 出发找出一条向上延伸到达其祖先的路径，即从一个结点到其父亲结点，再到其祖父结点等 等。求祖先路径所需要的时间正比于路径上的结点个数，因此父指针表示法对于求树根结点 的运算非常方便。 合并两棵树的操作也非常简单，只需要将一棵树的树根表示为另一棵树的子结点，也就 是设置父指针值即可。 父指针表示求结点的子结点和兄弟结点就比较麻烦，需要查询整个结构。另外，这种存 储结构中没有表示出结点之间的左右次序。父指针表示法适合于无序树的情况，而且只适合 于查询结点的根和合并树等操作，其主要优点是节省存储空间而且操作便捷。 (3) 等价类和并查集 父指针表示法的一个重要应用是实现并查集(Union/Find)。并查集是一种特殊的集合