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

1、树木和森林应用实验实验报告实验目的(1)掌握树木和森林的二次链表表达方法。(2)掌握树与二叉树结构及算法的对应关系。(3)掌握树的两个茄子巡回算法及其应用。实验操作环境Visual C实验任务为了使实验程序简洁直观，以下一些实验程序的一些功能实现在库函数节目“trees.h”中作为函数调用提供。假定在牙齿库函数中，树指针和节点类型分别定义为tree和tnode，并定义了一些茄子常见运算，如树(林)配置、树和森林显示等。每个运算的名称都比较直观，很容易理解。读者可以自行设计自己的库函数，也可以下载作者的网站。说明2:为了便于说明数据，与前面的实验一样，测试数据结构列表以档案名称显示(例如，请参阅

2、附录树列表中标记为tree1.tre的树，参阅附录树列表中标记为tree1.tre的树以了解特定结构)。实验内容第一个问题：1将树(或森林)转换为一棵二叉树。实验测试数据的基本要求：第一个数据集：tree1.tre第二个数据集：tree2.tre准备实验：用光学表格表示树中的数据，将其存储在文件中，通过档案流读取数据，然后根据读取的数据创建树第二个问题：2拯救森林的高度。实验测试数据的基本要求：第一个数据集：tree1.tre第二个数据集：tree2.tre第一个数据集：full41.cbt第二个数据集：letter.cbt准备实验：重复每棵树以找到高度的最大值。您可以设置个人成员以记录数量的

3、高度。第三个问题：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 p)，r)实验测试数据的基本要求：第一个数据集：t

4、ree1.tre第二个数据集：tree2.tre准备实验：使用递归函数调用时，如果当前节点具有左侧孩子，则输出“(”后访问下一个节点，如果当前节点的右侧指针不为空，则输出“，”后访问下一个节点。实验测试数据实验程序#includeUsing namespace STDTypedef char ElemType#define MAX 200Typedef struct CSNodeElemType dataStructcs node * firstchild，* nejt siblingCs节点，* cs树；Typedef struct BTNodeElemType dataStruct BTN

5、ode *lchild，* rchild BTNode，* BTreeClass FORESTPublic :FOREST()；c stree returnT()；/导出森林的根节点BTree return Bt()；/导出森林的根节点创建Cs树(cs树t)；/创建森林BTree change(CSTree T，BTree BT1)；/二叉树森林Void first (cs树t，int I):/第一个问题：首先遍历森林中每个节点的值和层次，然后输出Void second(CSTree T) : /第五个问题：输出森林的广义表格。Void third(const CSTree T) : /第三个

6、问题：按层次遍历森林。void fourth(BTree BT)；/第四个问题：先遍历二叉树每个节点的值，然后输出int higth(const CSTree T)；/第二个问题：寻找森林的高度。Private :Cs树t；/森林的头节点BTree BT/二叉树头节点Int high/森林的高度FOREST : FOREST()high=0；T=空；BT=NULLCstreeforest :3360 returnt()return T；Btreeforest :3360 returnbt()Return BTCs treeforest :3360 creat (cs树t)Int a、b；T=n

7、ew CSNodeCinT-dataab；if(a=1)T-first child=NULL；else creat(T-first child)；if(b=1)T-nejtsibling=NULL；else creat(T-nejt sibling)；return T；Btreeforest :3360变更(cs树t，btreebt)If(！T) BT=空；Return NULLBT=new BTNodeBT-data=T-data；If(！t-first child)BT-lchild=NULL；Elsechange (t-first child，Bt-lchild)；If(！t-nejt

8、sibling)BT-rchild=NULL；Elsechange (t-nejt sibling，Bt-rchild)；Return BTVoid forest :3360第一次(cs树t，int I)If(！t)return；cout data first child)first(t-first child，i1)；if(t-nejt sibling)first(t-nejt sibling，I)；void forest 33603360 second(cs树t)If(！t)return；CoutdataIf(T-firstchild) cout(；second(T-first child

9、)；If(T-nejtsibling) Cout，second(T-nejtsibling)；else cout)；void forest :3360 third(const cs tree t)Cs树smax；Cs树p；Int j=1，I=1；p=T；While(p) sI=p；p=p-nejtsibling；While(i)！=j)Cs树q；q=Sj；cout q-data ；q=q-first child；While(q) sI=q；q=q-nejtsibling；void forest 33603360 fourth(btreebt)If(！BT)return；Coutdataif(BT-lchild)fourth(BT-lchild)；if(BT-rchild)fourth(BT-rchild)；int forest :3360 const cs tree tInt hs、HB；If(！t)return 0；hs=higth(T-first chi