实验九 森林

实验目的和要求

1. 掌握树和森林线索点和性质
2. 掌握将森林改为二叉树的方法
3. 掌握求森林深度的方法

实验环境

1. Visual Studio 2017 Community
2. Windows 10 Pro

实验内容

1. 利用给定数据森林，并将其改为二叉树
2. 求森林的深度

实验过程

任务一

设计

由前面的存储结构可知，若要将森林转换为二叉树，需进行这样的转换：对森林中的每个结点，用一个二叉树结点来对应，并将二义树结点的片边指针指向其第一个孩子(作为左孩子形式)，右边指针指向其下一个兄弟(作为右孩子形式)，将森林中各棵树的根当做兄弟来转换,如果森林用有序表 F = (T1, T2, …, T) 来表示，则将森林F转换为对应的二叉树 BT 的形式化描述如下。

如果 m = 0,则 BT 为空；否则依次做如下操作：

1. 将 T 的根结点作为 BT 的根
2. 将 T 的子树森林转换为 BT 的左子树
3. 将(T2, T3,…, T)转换为BT的右子树

由描述可知，转换过程可分 3 部分，即根、子树和兄弟森林，而子树和兄弟森林的求解与原题求解类似。

在求树的深度时，可以参考二叉树求深度的方法，不同的是在新的二叉树中，遇到左孩子才需要将深度增加。

编码实现

编码实现，通过 C++ 来实现以上分析过程。

测试

实验收获

通过本次实验掌握树和森林线索点和性质，掌握将森林改为二叉树的方法，掌握求森林深度的方法。