1.实验目的
(1)掌握树和森林的孩子兄弟链表(二叉链表)表示方法。
(2)掌握树和二叉树的结构及算法之间的对应关系。
(3)掌握树的两种遍历算法及其应用。
2.实验任务
设计、实现算法求解下列问题:
(1)按先序、后序、层次遍历森林。
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(2)求森林的高度。
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(3)求森林结点总数。
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(4)求森林叶子结点数。
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(5)求森林的度。
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(6)先序输出结点值及其层次号。
例对图7-1所示森林,输出为:(A,1) (B,2) (E,3) (K,4) (F,3) (G,3) (C,2) (H,3) (I,3) (D,2) (J,3) (L,1) (M,2) (N,2) (O,1) (P,2)
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
(7)输出广义表表示的树。
例对图7-1所示森林,输出为:A( B(E(K),F,G),C(H,I),D(J)), L(M,N), O(P) )
实验测试数据基本要求:
第一组数据: tree11.tre
第二组数据: f20.tre
3.实验说明
(以下给出的森林创建方法仅供参考,实验者可自行设计其它创建方法)
(1)树(森林)的创建
本实验提供的创建代码,创建二叉链表表示的树(森林)分为2个步骤,第一步:读取文本文件,创建双亲表示的树(森林);第二部:从双亲表示转换为二叉链表表示的树(森林)。
(2)树(森林)数据文件格式说明
数据文件主要包含三个部分:树(森林)标识;结点列表;父子结点对(边)。
①标识行
Tree or Forest,以区别其它数据文件,这一行是非必须的。
②结点列表
给出树(森林)中的所有结点,结点次序无关,只要列出所有结点即可。如图7-1所示的森林,结点列表可为:
//下面为树(森林)的结点列表
A B C D E F G H I J K L M N O P。
③父子结点对(边)信息
父子对信息严格按照父结点、子结点表示一对父子结点,父子对也次序无关,只要列出森林中所有父子对即可,例图7-1所示森林,所有父子对为:
//以下为父子结点对(边)信息
A B
A C
A D
B E
B F
B G
C H
C I
D J
E K
L M
L N
O P
(3)创建树(森林)包含文件说明
createTree.h,包括树(森林)的双亲存储、二叉链表存储的定义;从文件创建双亲表示的树(森林);从双亲表示的森林创建二叉链表表示的森林;其它辅助算法。
1