《数据结构树和森林实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构树和森林实验报告.docx（9页珍藏版）》请在三一办公上搜索。
1、数据结构树和森林实验报告树和森林应用实验 实验报告 实验目的 (1)掌握树和森林的二叉链表表示方法。 (2)掌握树和二叉树的结构及算法之间的对应关系。 (3)掌握树的两种遍历算法及其应用。 实验运行环境 Visual C+ 实验任务 为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序trees.h中的函数的形式给出，并假设该库函数中定义了树指针和结点类型分别为tree和tnode，以及部分常用运算，例如构建树、以某种方式显示树和森林等。各运算的名称较为直观，因而易于理解。读者可自行设计自己的库函数，也可到作者的网站下载。 说明2：为便于数据的描述，和前面的实验一样，将测
2、试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名为tree1.tre的树，其具体结构形式参见附录中的树列表中的标有tree1.tre的树。 实验内容 第一题： 将一棵树转换为二叉树。 实验测试数据基本要求： 第一组数据： tree1.tre 第二组数据： tree2.tre 实验准备： 用广义表来表示树的数据，保存到文件中，通过文件流来读入数据，并根据读入的数据来创建树 第二题： 求森林的高度。 实验测试数据基本要求： 第一组数据： tree1.tre 第二组数据： tree2.tre 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 遍历每一棵树
3、，寻找高度的最大值。可以设立一个私有成员来记录数的高度。 第三题： 按层次方式遍历森林。 实验测试数据基本要求： 第一组数据： tree1.tre 第二组数据： tree2.tre 实验准备： 先访问第一层结点，并将它放入队列中，并反复从队列中取结点，访问其孩子结点，直至访问到叶子结点。 第四题： 输出一个森林中每个结点的值及其对应的层次数。 实验测试数据基本要求： 第一组数据： tree1.tre 第二组数据： tree2.tre 实验准备： 使用递归函数来访问森林，同时输出层次数及结点值，使用形参来传递当前层次数 第五题： 输出一个森林的广义表形式，如下图中的森林的输出为： (a(b(c,
4、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 实验准备： 使用递归函数调用，若当前节点有左孩子，则先输出 (再访问下一节点，若当前节点的右指针不为空，则先输出,再访问下一结点。 实验测试数据 实验程序 #include using namespace std; typedef char ElemType; #define MAX 200 typedef struct CSNode ElemType data; struct CSNode *fir
5、stchild , *nejtsibling ; CSNode , *CSTree; typedef struct BTNode ElemType data; struct BTNode *lchild , *rchild ; BTNode,*BTree; class FOREST public : FOREST; CSTree returnT; /输出森林的根结点 BTree returnBT; /输出森林的根结点 CSTree creat(CSTree &T); /创建森林 BTree change(CSTree &T,BTree &BT1); /将森林转换成为二叉树 void first
6、(CSTree &T,int i); /第一题：按照先序遍历的方式来输出树林每个结点的值以及层次 void second(CSTree &T); /第五题：输出一个森林的广义表形式 void third(const CSTree &T); /第三题：按层次方式遍历森林。 void fourth(BTree &BT); /第四题：按照先序遍历的方式来输出二叉树每个结点的值 int higth(const CSTree &T); /第二题：求森林的高度 private : CSTree T; /森林的头结点 BTree BT; int high; ; FOREST : FOREST high =
7、0; T = NULL; BT = NULL; CSTree FOREST : returnT return T; BTree FOREST : returnBT return BT; /二叉树的头结点 /森林的高度 CSTree FOREST : creat(CSTree &T) int a ,b; T = new CSNode; cinT-dataab; if(a = 1) T-firstchild = NULL; else creat(T-firstchild); if(b = 1) T-nejtsibling = NULL; else creat(T-nejtsibling); ret
8、urn T; BTree FOREST : change(CSTree &T,BTree &BT) if(!T) BT = NULL; return NULL; BT = new BTNode; BT - data = T - data; if(!T-firstchild) BT-lchild = NULL; else change(T-firstchild,BT-lchild); if(!T-nejtsibling) BT-rchild = NULL; else change(T-nejtsibling,BT-rchild); return BT; void FOREST : first(C
9、STree &T,int i) if(!T) return ; coutdata ifirstchild) first(T-firstchild,i+1); if(T-nejtsibling) first(T-nejtsibling,i); void FOREST : second(CSTree &T) if(!T) return ; coutdata; if(T-firstchild) coutfirstchild); if(T-nejtsibling) coutnejtsibling); else cout nejtsibling ; while(i!=j) CSTree q; q = S
10、j+; cout data firstchild; while(q) Si+ = q; q = q - nejtsibling; void FOREST : fourth(BTree &BT) if(!BT) return ; coutdatalchild) fourth(BT-lchild); if(BT-rchild) fourth(BT-rchild); int FOREST : higth(const CSTree &T) int hs,hb; if(!T) hs = higth(T-firstchild) ; hb = higth(T-nejtsibling); high = (hs
11、 + 1) hb ? (hs + 1) : hb; return high; int main FOREST f_1,f_2,f_3,f_4,f_5; int chioce; coutendl; return 0; cout数据结构实验五-树和森林应用实验endl; coutendl; cout第1题: 将一棵树转换为二叉树endl; cout第2题: 求森林的高度endl; cout第3题: 按层次方式遍历森林endl; cout第4题: 输出一个森林中每个结点的值及其对应的层次数endl; cout第5题: 输出一个森林的广义表形式endl; cout退出程序:0endl; cout请选择
12、一道题chioce; cout请输入森林的元素endl; coutendl; switch (chioce) case 1: CSTree p1; BTree p; 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; cout请输入森林的元素endl; case 2: CSTree p2; p2 = f_2.returnT; p2 = f_2.creat(p2); cout森林的高度
13、是：; coutendl; break; coutf_2.higth(p2); cout请输入森林的元素endl; case 3: CSTree p3; p3 = f_3.returnT; p3 = f_3.creat(p3); cout按照层次遍历的结果是：endl; coutendl; break; f_3.third(p3); case 4: cout请输入森林的元素endl; CSTree p4; p4 = f_3.returnT; p4 = f_3.creat(p4); cout按照森林先序遍历输出的结果是输出endl; cout一个森林中每个结点的值及其对应的层次数：endl; f_3.first(p4,1); coutendl; break; case 5: cout请输入森林的元素endl; CSTree p5; p5 = f_3.returnT; p5 = f_3.creat(p5); cout输出一个森林的广义表形式：endl; coutendl; break; f_3.second(p5); case 0: coutEXITendl; break; default: cout输入错误，请重新输入endl; return 0 ;
