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

树和森林应用实验实验报告实验目的(1)掌握树和森林的二叉链表表示方法。(2)掌握树和二叉树的结构及算法之间的对应关系。(3)掌握树的两种遍历算法及其应用。实验运行环境VisualC++实验任务为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序trees.h中的函数的形式给出，并假设该库函数中定义了树指针和结点类型分别为tree和tnode，以及部分常用运算，例如构建树（森林）、以某种方式显示树和森林等。各运算的名称较为直观，因而易于理解。读者可自行设计自己的库函数，也可到作者的网站下载。说明2：为便于数据的描述，和前面的实验一样，将测试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名为tree1.tre的树，其具体结构形式参见附录中的树列表中的标有tree1.tre的树。实验内容第一题：1将一棵树（或森林）转换为二叉树。实验测试数据基本要求：第一组数据：tree1.tre第二组数据：tree2.tre实验准备：用广义表来表示树的数据，保存到文件中，通过文件流来读入数据，并根据读入的数据来创建树第二题：2求森林的高度。实验测试数据基本要求：第一组数据：tree1.tre第二组数据：tree2.tre第一组数据：full41.cbt第二组数据：letter.cbt实验准备：遍历每一棵树，寻找高度的最大值。可以设立一个私有成员来记录数的高度。第三题：3按层次方式遍历森林。实验测试数据基本要求：第一组数据：tree1.tre第二组数据：tree2.tre实验准备：先访问第一层结点，并将它放入队列中，并反复从队列中取结点，访问其孩子结点，直至访问到叶子结点。第四题：4输出一个森林中每个结点的值及其对应的层次数。实验测试数据基本要求：第一组数据：tree1.tre第二组数据：tree2.tre实验准备：使用递归函数来访问森林，同时输出层次数及结点值，使用形参来传递当前层次数第五题：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))))实验测试数据基本要求：第一组数据：tree1.tre第二组数据：tree2.tre实验准备：使用递归函数调用，若当前节点有左孩子，则先输出‘(’再访问下一节点，若当前节点的右指针不为空，则先输出‘,’再访问下一结点。实验测试数据实验程序#includeiostreamusingnamespacestd;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;cinT-dataab;if(a==1)T-firstchild=NULL;elsecreat(T-firstchild);if(b==1)T-nejtsibling=NULL;elsecreat(T-nejtsibling);returnT;}BTreeFOREST::change(CSTree&T,BTree&BT){if(!T){BT=NULL;returnNULL;}BT=newBTNode;BT-data=T-data;if(!T-firstchild)BT-lchild=NULL;elsechange(T-firstchild,BT-lchild);if(!T-nejtsibling)BT-rchild=NULL;elsechange(T-nejtsibling,BT-rchild);returnBT;}voidFOREST::first(CSTree&T,inti){if(!T)return;coutT-dataiendl;if(T-firstchild)first(T-firstchild,i+1);if(T-nejtsibling)first(T-nejtsibling,i);}voidFOREST::second(CSTree&T){if(!T)return;coutT-data;if(T-firstchild){cout'(';second(T-firstchild);}if(T-nejtsibling){cout',';second(T-nejtsibling);}elsecout')';}voidFOREST::third(constCSTree&T){CSTreeS[MAX];CSTreep;intj=1,i=1;p=T;while(p){S[i++]=p;p=p-nejtsibling;}while(i!=j){CSTreeq;q=S[j++];coutq-data;q=q-firstchild;while(q){S[i++]=q;q=q-nejtsibling;}}}voidFOREST::fourth(BTree&BT){if(!BT)return;coutBT-data;if(BT-lchild)fourth(BT-lchild);if(BT-rchild)fourth(BT-rchild);}intFOREST::higth(constCSTree&T){inths,hb;if(!T){return0;}hs=higth(T-firstchild);hb=higth(T-nejtsibling);high=(hs+1)hb?(hs+1):hb;returnhigh;}intmain(){FORESTf_1,f_2,f_3,f_4,f_5;intchioce;coutendl;cout数据结构实验五--树和森林应用实验endl;coutendl;cout第1题:将一棵树（或森林）转换为二叉树endl;cout第2题:求森林的高度endl;cout第3题:按层次方式遍历森林endl;cout第4题:输出一个森林中每个结点的值及其对应的层次数endl;cout第5题:输出一个森林的广义表形式endl;cout退出程序:0endl;coutendl;cout请选择一道题endl;cinchioce;switch(chioce){case1:{cout请输入森林的元素endl;CSTreep1;BTreep;p1=f_1.returnT();p=f_1.returnBT();p1=f_1.creat(p1);p=f_1.change(p1,p);cout按照二叉树先序遍历的结果是：endl;f_1.fourth(p);coutendl;break;}case2:{cout请输入森林的元素endl;CSTreep2;p2=f_2.returnT();p2=f_2.creat(p2);cout森林的高度是：;coutf_2.higth(p2);coutendl;break;}case3:{cout请输入森林的元素endl;CSTreep3;p3=f_3.returnT();p3=f_3.creat(p3);cout按照层次遍历的结果是：endl;f_3.third(p3);coutendl;break;}case4:{cout请输入森林的元素endl;CSTreep4;p4=f_3.returnT();p4=f_3.creat(p4);cout按照森林先序遍历输出的结果是输出endl;cout一个森林中每个结点的值及其对应的层次数：endl;f_3.first(p4,1);coutendl;break;}case5:{cout请输入森林的元素endl;CSTreep5;p5=f_3.returnT();p5=f_3.creat(p5);cout输出一个森林的广义表形式：endl;f_3.second(p5);coutendl;break;}case0:{coutEXITendl;break;}default:{cout输入错误，请重新输入endl;}}return0;}