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

1、树和森林应用实验实验报告实验目的(1) 掌握树和森林的二叉链表表示方法。(2) 掌握树和二叉树的结构及算法之间的对应关系。(3) 掌握树的两种遍历算法及其应用。实验运行环境Visual C+实验任务为使实验程序简洁直观， 下面的部分实验程序中的一些功能实现仍以调用库 函数程序 中的函数的形式给出， 并假设该库函数中定义了树指针和结点类型分 别为 tree 和 tnode ，以及部分常用运算，例如构建树(森林) 、以某种方式显示 树和森林等。各运算的名称较为直观， 因而易于理解。 读者可自行设计自己的库 函数，也可到作者的网站下载。说明 2：为便于数据的描述，和前面的实验一样，将测试数据结构列出

2、，并 以一个文件名的形式给出标注， 例如测试数据名为的树， 其具体结构形式参见附 录中的树列表中的标有的树。实验内容第一题：将一棵树(或森林)转换为二叉树。实验测试数据基本要求：第一组数据：第二组数据： 实验准备：用广义表来表示树的数据， 保存到文件中， 通过文件流来读入数据， 并根据 读入的数据来创建树第二题：求森林的高度。实验测试数据基本要求：第一组数据：第二组数据：第一组数据：第二组数据：实验准备： 遍历每一棵树，寻找高度的最大值。 可以设立一个私有成员来记录数的高度。第三题：按层次方式遍历森林。实验测试数据基本要求： 第一组数据： 第二组数据：实验准备： 先访问第一层结点， 并将它放入

3、队列中， 并反复从队列中取结点， 访问其孩 子结点，直至访问到叶子结点。第四题： 输出一个森林中每个结点的值及其对应的层次数。 实验测试数据基本要求：第一组数据：第二组数据：实验准备： 使用递归函数来访问森林， 同时输出层次数及结点值， 使用形参来传递当前 层次数第五题： 输出一个森林的广义表形式，如下图中的森林的输出为： (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) 实验测试数据基本要求：第一组数据：第二组数据：实验准备:使用递归函数调用，若当前节点有左孩子，则先输出(再访问下一节点, 若当前节点的右指针不为空

4、，则先输出，再访问下一结点。实验测试数据实验程序#include using namespace std;typedef char ElemType;#define MAX 200typedef struct CSNodeElemType data;struct CSNode *firstchild , *nejtsibling ; CSNode , *CSTree;typedef struct BTNodeElemType data; struct BTNode *lchild , *rchild ; BTNode,*BTree;class FORESTpublic :输出森林的根结点输出森

5、林的根结点 创建森林 将森林转换成为二叉树FOREST();CSTree returnT(); /BTree returnBT(); /CSTree creat(CSTree &T);/BTree change(CSTree &T,BTree &BT1); /void first(CSTree &T,int i);/ 第一题：按照先序遍历的方式来输出树林每个结点的值以及层次void second(CSTree &T); / 第五题：输出一个森林的广义表形式void third(const CSTree &T); / 第三题：按层次方式遍历森林。void fourth(BTree &BT); /

6、第四题：按照先序遍历的方式来输出二叉树每个结点的值第二题：求森林的高度森林的头结点 二叉树的头结点森林的高度int higth(const CSTree &T);/private :CSTree T;/BTree BT;/int high; / ;FOREST : FOREST() high = 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; c

7、inT-dataab;if(a = 1) T-firstchild = NULL; else creat(T-firstchild);if(b = 1) T-nejtsibling = NULL; else creat(T-nejtsibling);return 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-firstc

8、hild,BT-lchild); if(!T-nejtsibling) BT-rchild = NULL;else change(T-nejtsibling,BT-rchild); return BT;void FOREST : first(CSTree &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

9、-firstchild) coutfirstchild);if(T-nejtsibling) coutnejtsibling);else cout nejtsibling ;while(i!=j)CSTree q;q = Sj+;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 :

10、higth(const CSTree &T)int hs,hb;if(!T)return 0;hs = higth(T-firstchild) ;hb = higth(T-nejtsibling);high = (hs + 1) hb (hs + 1) : hb; return high;int main() FOREST f_1,f_2,f_3,f_4,f_5;int chioce;coutendl;cout 数据结构实验五 - 树和森林应用实验 endl; coutendl;cout 第 1 题 : 将一棵树(或森林)转换为二叉树 endl;cout 第 2 题 : 求森林的高度 endl

11、;cout 第 3 题 : 按层次方式遍历森林 endl;endl;cout 第 4 题 : 输出一个森林中每个结点的值及其对应的层次数cout 第 5 题 : 输出一个森林的广义表形式 endl;cout 退出程序 :0endl;coutendl;cout 请选择一道题 chioce;switch (chioce)case 1:cout 请输入森林的元素 endl;CSTree p1; BTree p;p1 = ();p = ();p1 = (p1);p = (p1,p);cout 按照二叉树先序遍历的结果是： endl; (p);coutendl;break;case 2:cout 请输入森林的元素 endl;CSTree p2; p2 = ();p2 = (p2);cout 森林的高度是： ;cout(p2);coutendl;break;case 3:cout 请输入森林的元素 endl;CSTree p3; p3 = ();p3 = (p3);cout 按照层次遍历的结果是： endl;(p3);coutendl;break;case 4:cout 请输入森林的元素 endl;CSTree p4; p4 = ();p4 = (p4);cout 按照森林先序遍历输出的结果是输出 endl;endl;cout 一个森林中每个结点的值及其对应的层