实验九 森林
实验九 森林
实验目的和要求
- 掌握树和森林线索点和性质
- 掌握将森林改为二叉树的方法
- 掌握求森林深度的方法
实验环境
- Visual Studio 2017 Community
- Windows 10 Pro
实验内容
- 利用给定数据森林,并将其改为二叉树
- 求森林的深度
实验过程
任务一
设计
由前面的存储结构可知,若要将森林转换为二叉树,需进行这样的转换:对森林中的每个结点,用一个二叉树结点来对应,并将二义树结点的片边指针指向其第一个孩子(作为左孩子形式),右边指针指向其下一个兄弟(作为右孩子形式),将森林中各棵树的根当做兄弟来转换,如果森林用有序表 F = (T1, T2, …, T) 来表示,则将森林F转换为对应的二叉树 BT 的形式化描述如下。
如果 m = 0,则 BT 为空;否则依次做如下操作:
- 将 T 的根结点作为 BT 的根
- 将 T 的子树森林转换为 BT 的左子树
- 将(T2, T3,…, T)转换为BT的右子树
由描述可知,转换过程可分 3 部分,即根、子树和兄弟森林,而子树和兄弟森林的求解与原题求解类似。
在求树的深度时,可以参考二叉树求深度的方法,不同的是在新的二叉树中,遇到左孩子才需要将深度增加。
编码实现
编码实现,通过 C++ 来实现以上分析过程。
测试
实验收获
通过本次实验掌握树和森林线索点和性质,掌握将森林改为二叉树的方法,掌握求森林深度的方法。