数据结构实验报告._计算机-数据结构与算法.pdf
.I .r .数据结构实验报告 一 题目要求 1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、成绩 3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?二 解决方案 对于前三个题目要求，我们用一个程序实现代码如下#include#include#include#include Stack.h /栈的头文件，没有用上 typedef int ElemType;/数据类型 typedef int Status;/返回值类型/定义二叉树结构 typedef struct BiTNode ElemType data;/数据域 struct BiTNode*lChild,*rChild;/左右子树域 BiTNode,*BiTree;int InsertBST(BiTree&T,int key)/插入二叉树函数 if(T=NULL)T=(BiTree)malloc(sizeof(BiTNode);T-data=key;T-lChild=T-rChild=NULL;return 1;else if(keydata)InsertBST(T-lChild,key);else if(keyT-data)InsertBST(T-rChild,key);else return 0;BiTree CreateBST(int a,int n)/创建二叉树函数 BiTree bst=NULL;int i=0;while(irChild)/右子树为空 重接它的左子树 q=T;T=(T)-lChild;free(q);else if(!(T)-lChild)/若左子树空 则重新接它的右子树 q=T;T=(T)-rChild;else q=T;s=(T)-lChild;while(s-rChild)q=s;s=s-rChild;(T)-data=s-data;/s 指向被删除结点的前驱 if(q!=T)q-rChild=s-lChild;else q-lChild=s-lChild;free(s);return 1;/删除函数，在 T中 删除 key 元素 int DeleteBST(BiTree&T,int key)if(!T)return 0;else if(key=(T)-data)return Delete(T);else if(keydata)return DeleteBST(T-lChild,key);else return DeleteBST(T-rChild,key);历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .int PosttreeDepth(BiTree T)/求深度 int hr,hl,max;if(!T=NULL)hl=PosttreeDepth(T-lChild);hr=PosttreeDepth(T-rChild);max=hlhr?hl:hr;return max+1;else return 0;void printtree(BiTree T,int nlayer)/打印二叉树 if(T=NULL)return;printtree(T-rChild,nlayer+1);for(int i=0;idata);printtree(T-lChild,nlayer+1);void PreOrderNoRec(BiTree root)/先序非递归遍历 BiTree p=root;BiTree stack50;int num=0;while(NULL!=p|num0)while(NULL!=p)printf(%d ,p-data);stacknum+=p;p=p-lChild;num-;p=stacknum;p=p-rChild;printf(n);void InOrderNoRec(BiTree root)/中序非递归遍历 BiTree p=root;历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .int num=0;BiTree stack50;while(NULL!=p|num0)while(NULL!=p)stacknum+=p;p=p-lChild;num-;p=stacknum;printf(%d ,p-data);p=p-rChild;printf(n);void PostOrderNoRec(BiTree root)/后序非递归遍历 BiTree p=root;BiTree stack50;int num=0;BiTree have_visited=NULL;while(NULL!=p|num0)while(NULL!=p)stacknum+=p;p=p-lChild;p=stacknum-1;if(NULL=p-rChild|have_visited=p-rChild)printf(%d ,p-data);num-;have_visited=p;p=NULL;else p=p-rChild;printf(n);历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .int main()/主函数 printf(-二叉排序树的实现-);printf(n);int layer;int i;int num;printf(输入节点个数:);scanf(%d,&num);printf(依次输入这些整数（要不相等）);int*arr=(int*)malloc(num*sizeof(int);for(i=0;ino=no;T-name=name;T-score=score;T-lChild=T-rChild=NULL;return 1;else if(nono)InsertBST(T-lChild,no,score,name);else if(keyT-data)InsertBST(T-rChild,no,score,name);else return 0;其他含参函数也类似 即可完成 50 个信息存储 用数组存储 50 个信息，查看以往代码#include#include using namespace std;class student private:int num;string name;int ob1;int ob2;int ara;public:void set(int a,string b,int c,int d);void show();int average();历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .;void student:set(int a,string b,int c,int d)num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;void student:show()cout 学号：num：name 科目一：ob1 科目二：ob2 平均成绩：araendl;int student:average()return ara;int main()cout 欢迎来到学生管理系统endl;cout 0.查询学号信息：endl;cout 1.删除学号信息：endl;cout 2.添加学号新信息endl;cout 3.按平均分降序显示所有学生信息endl;cout 4.退出endl;历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .student*ptr=new student21;ptr1.set(1,小明,88,67);/已存入的学生信息 ptr2.set(2,小,68,82);ptr3.set(3,小王,68,62);ptr4.set(4,小,79,82);ptr5.set(5,小,63,82);ptr6.set(6,小红,68,73);ptr7.set(7,小木,62,77);ptr8.set(8,小添,65,86);ptr9.set(9,小天,68,82);ptr10.set(10,三,88,82);ptr11.set(11,四,98,82);ptr12.set(12,王五,88,81);ptr13.set(13,小月,58,82);ptr14.set(14,小鑫,78,80);ptr15.set(15,小良,68,92);ptr16.set(16,小成,68,82);ptr17.set(17,小敏,98,92);ptr18.set(18,小问,88,88);ptr19.set(19,小文,48,82);ptr20.set(20,小瑞,98,62);/已存入的学生信息 int numlock;历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .int j=0;int i,k,m;int q,e,r;string w;while(1)cout 按 0,1,2,3,4 进行操作numlock;switch(numlock)case 0:cout 输入想查询的学号i;if(i=j)cout 该学号信息已被删除endl;break;ptri.show();break;case 1:cout 输入想删除的学号j;deletejptr;cout 删除成功endl;break;历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .case 2:cout 输入想添加的学号信息k;if(k!=j)cout 该学号信息已经存在，添加失败endl;break;cout 重新输入添加的学号q;cout 输入w;cout 输入科目一的成绩e;cout 输入科目二的成绩r;ptrk.set(q,w,e,r);break;case 3:for(m=1;m20;m+)for(int n=m+1;n20;n+)if(ptrm.average()ptrn.average()student a;历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .a=ptrm;ptrm=ptrn;ptrn=a;ptrm.show();break;case 4:cout 使用endl;return 0;default:coutnumber out of 0 to 4endl;break;return 0;三 测试结果 二叉排序树储存数据界面（储存学生信息略）创建二叉树：历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .插入节点：删除节点：非递归遍历：历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .退出：数组储存学生信息界面 分析查找效率：因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。四 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在 C+编历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修.I .r .译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。递归遍历的实现比非递归的遍历真的简单很多。开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。历每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来分别用二叉排序树和数组去存储一个班人以上的成员信息至少包括学号成绩项对比查找效率并说明在什么情况下二叉排序树效率高为什么二解决方案左右子树域插入二叉树函数创建二叉树函数右子树为空重接它的左子树若左子树空则重新接它的右子树指向被删除结点的前驱删除函数在中删除元素求深度打印二叉树先序非递归遍历中序非递归遍历后序非递归遍历主函数二叉排序打印二叉树非递归遍历二叉树退出输入要插入的节点插入成功树状图为输入要删除的节点删除成功树状图为非递归遍历二叉树先序遍历中序遍历后序遍历树状图为程序执行完毕对于第四小问要储存学生的三个信息需要把上面程序修
