实验九 森林

实验九 森林

实验目的和要求

  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++ 来实现以上分析过程。

测试

森林转为二叉树

实验收获

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