数据结构——树和森林实验报告.doc

树和森林应用实验实验报告实验目的(1)掌握树和森林的二叉链表表示方法。(2)掌握树和二叉树的结构及算法之间的对应关系。(3)掌握树的两种遍历算法及其应用。实验运行环境VisualC++实验任务为使实验程序简洁直观,下面的部分实验程序中的一些功能实现仍以调用库函数程序""中的函数的形式给出,并假设该库函数中定义了树指针和结点类型分别为tree和tnode,以及部分常用运算,例如构建树(森林)、以某种方式显示树和森林等。各运算的名称较为直观,因而易于理解。读者可自行设计自己的库函数,也可到作者的网站下载。说明2:为便于数据的描述,和前面的实验一样,将测试数据结构列出,并以一个文件名的形式给出标注,,。实验内容第一题:<1>将一棵树(或森林)转换为二叉树。 实验测试数据基本要求:第一组数据:::用广义表来表示树的数据,保存到文件中,通过文件流来读入数据,并根据读入的数据来创建树第二题:<2>求森林的高度。 实验测试数据基本要求:第一组数据:::::遍历每一棵树,寻找高度的最大值。可以设立一个私有成员来记录数的高度。第三题:<3>按层次方式遍历森林。 实验测试数据基本要求:第一组数据:::先访问第一层结点,并将它放入队列中,并反复从队列中取结点,访问其孩子结点,直至访问到叶子结点。第四题:<4>输出一个森林中每个结点的值及其对应的层次数。 实验测试数据基本要求:第一组数据:::使用递归函数来访问森林,同时输出层次数及结点值,使用形参来传递当前层次数第五题:<5>输出一个森林的广义表形式,如下图中的森林的输出为:(a(b(c,d,e,f),g(h,i,j),k(l,m,n)),o(p(q)),r(s(t(u)),v(w(x,y,z))))实验测试数据基本要求:第一组数据:::使用递归函数调用,若当前节点有左孩子,则先输出‘(’再访问下一节点,若当前节点的右指针不为空,则先输出‘,’再访问下一结点。实验测试数据实验程序#include<iostream>usingnamespacestd;typedefcharElemType;#defineMAX200typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nejtsibling;}CSNode,*CSTree;typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BTree;classFOREST{public:FOREST();CSTreereturnT();//输出森林的根结点BTreereturnBT();//输出森林的根结点CSTreecreat(CSTree&T);//创建森林BTreechange(CSTree&T,BTree&BT1);//将森林转换成为二叉树voidfirst(CSTree&T,inti);//第一题:按照先序遍历的方式来输出树林每个结点的值以及层次voidsecond(CSTree&T);//第五题:输出一个森林的广义表形式voidthird(constCSTree&T);//第三题:按层次方式遍历森林。voidfourth(BTree&BT);//第四题:按照先序遍历的方式来输出二叉树每个结点的值inthigth(constCSTree&T);//第二题:求森林的高度private:CSTreeT;//森林的头结点BTreeBT;//二叉树的头结点inthigh;//森林的高度};FOREST::FOREST(){high=0;T=NULL;BT=NULL;}CSTreeFOREST::returnT(){returnT;}BTreeFOREST::returnBT(){returnBT;}CSTreeFOREST::creat(CSTree&T){inta,b;T=newCSNode;cin>>T->data>>a>>b;if(a==1)T->firstchild=NULL;elsecreat(T->firstchild);if(b==1)T->nejtsibling=NULL;elsecreat(T->nejtsibling);returnT;}BTreeFOREST