《数据结构实验报告[实验报告]》由会员分享，可在线阅读，更多相关《数据结构实验报告[实验报告]（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告一 题目要求1） 编程实现二叉排序树，包括生成、插入，删除；2） 对二叉排序树进行先根、中根、和后根非递归遍历；3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?二 解决方案对于前三个题目要求，我们用一个程序实现代码如下#include#include #include #include Stack.h /栈的头文件，没有用上typedef int ElemType; /数据类型typedef in
2、t 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(k
3、eyT-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);elseif(!(T)-lChild) /若左子树空 则重新接它的右子树 q=T;T=(T)-rChild;elseq=T;s=(T)-lChild;while(s-rChild) q=s; s=s-rChild;(T)-data=s-data; /s指向被删除结点的前驱i
4、f(q!=T)q-rChild=s-lChild; elseq-lChild=s-lChild;free(s);return 1; /删除函数，在T中 删除key元素int DeleteBST(BiTree &T,int key)if(!T) return 0;elseif(key=(T)-data) return Delete(T);elseif(keydata) return DeleteBST(T-lChild,key);elsereturn DeleteBST(T-rChild,key);int PosttreeDepth(BiTree T)/求深度int hr,hl,max;if(!
5、T=NULL)hl=PosttreeDepth(T-lChild);hr=PosttreeDepth(T-rChild);max=hlhr?hl:hr;return max+1;elsereturn 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
6、 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;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
7、=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;elsep=p-rChild;printf(
8、n);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;inum;i+)scanf(%d,arr+i); BiTree bst=CreateBST(arr,num);printf(n);printf(二叉树创建成功!); printf(n); layer=PosttreeDepth(bst); printf(树状
9、图为:n); printtree(bst,layer);int j;int T;int K;for(;)loop:printf(n);printf( *按提示输入操作符*:);printf(n);printf( 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出);scanf(%d,&j);switch(j)case 1:printf(输入要插入的节点:);scanf(%d,&T);InsertBST(bst,T);printf(插入成功!);printf(树状图为:n);printtree(bst,layer);break;case 2:printf(输入要删除的节点
10、);scanf(%d,&K);DeleteBST(bst,K);printf(删除成功!);printf(树状图为:n);printtree(bst,layer);break;case 3:layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:printf(非递归遍历二叉树);printf(先序遍历:n);PreOrderNoRec(bst);printf(中序遍历:n);InOrderNoRec(bst);printf(后序遍历:n);PostOrderNoRec(bst);printf(树状图为:n);printtree(bs
11、t,layer);break;case 5:printf(程序执行完毕!);return 0;goto loop;return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为typedef int ElemType; /数据类型typedef string SlemType; typedef int Status; /返回值类型/定义二叉树结构typedef struct BiTNode SlemTypename; ElemTypescore;ElemTypeno; /数据域 struct BiTNode *lChild, *rChild;/左右子树域BiTNode, *BiTree;参数不是key,而是另外三个 int InsertBST(BiTree &T,int no,int score,
