数据结构课程设计-二叉排序树

精品文档欢迎下载成绩：__________课程设计〔数据结构〕院、系计算机与软件学院专业软件工程姓名学号指导教师二零一二年十二月二十五日精品文档欢迎下载I目录1.绪论 12.课程设计 12.1课程设计目的 12.2课程设计要求 13.课程实验内容 23.1普通二叉排序树的插入，删除 23.2按递增顺序插入N个整数，并按同样顺序删除 23.3按递增顺序插入N个整数，并按相反顺序删除 23.4按随机顺序插入N个整数，并按随机顺序删除 34.课程设计实验结果 34.1课程实验数据 34.2实验操作效率比拟图 4精品文档欢迎下载二叉排序树魏麟祥南京信息工程大学计算机与软件学院，南京210044摘要：本文主要是对二叉排序树的操作效率进行探讨，先从二叉排序树的定义来进行分析，然后分析其主要的性质。通过对其性质的分析，让人们了解二叉排序树的运行。从理论上分析二叉排序树的创立、删除、插入以及遍历，运用C语言算法编程实现对普通二叉排序树制定操作，通过普通二叉排序树对实例的运行时间来判断普通二叉排序树的运行效率。关键词：二叉排序树；C语言；随机函数1.绪论通过对数据结构的不断学习，对二叉排序树有了一定的了解。在教材中，只是从理论上说明了二叉排序树的定义及其效率，并没有用具体算法的在计算机上实现。就此问题，本文在其理论的根底上给出了具体的算法。利用普通二叉排序树的定义，为了更详细的描述二叉排序树的算法，文章采用C语言来编程实现。该算法主要描述二叉排序树的建立，删除，插入以及遍历等操作。通过分别测试3类数据来直观的表现出普通二叉排序树的运行效率。2.课程设计2.1课程设计目的掌握了解二叉排序树插入删除的效率，通过合作写程序提高自己的设计能力和测试的能力。在写程序的时候能了解自己的缺乏，提高自己解决问题的能力。2.2课程设计要求对普通二叉排序树实现定制操作，分析这一数据结构对应的插入和删除操作效率。要求对N个不同整数进行以下操作：〔1〕按递增顺序插入N个整数，并按同样顺序删除；〔2〕按递增顺序插入N个整数，并按相反顺序删除；〔3〕按随机顺序插入N个整数，并按随机顺序删除；要求N从1000到10000取值，并以数据规模N为横轴，运行时间为纵轴，画出3种不同数据结构对应的操作效率比拟图。3.课程实验内容3.1普通二叉排序树的插入，删除StatusInsert(BiTree&T,inte){ if(!Search(T,e,NULL,p)){//查找不成功 s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=NULL;s->rchild=NULL; if(!p)T=s;//被插结点*s为新的根结点 elseif(e<p->data)p->lchild=s;//被插结点*s为左孩子 elsep->rchild=s;//被插结点*s为右孩子 returnok;}elsereturnfalse;}StatusDeleteBST(BiTree&T,intkey){//假设二叉排序树T存在关键字等于key的数据元素时，那么删除该数据元素结点 if(!T)returnfalse; else{if(key==T->data)returnDelete(T); elseif(key<T->data)returnDeleteBST(T->lchild,key); elsereturnDeleteBST(T->rchild,key);}}3.2按递增顺序插入N个整数，并按同样顺序删除StatusCreateBiTree(BiTree&T,intn){ inti;T=NULL;for(i=0;i<n;i++){intkey=i;Insert(T,key);}//循环插入N个整数 returnok;}voidDele(BiTree&T,intm,intn){inti;intkey;for(i=0;i<m;i++){key=i;DeleteBST(T,key);}}//按照相同顺序删除M个整数3.3按递增顺序插入N个整数，并按相反顺序删除voidDele(BiTree&T,intm,intn){ inti;intkey; for(i=n-1;i>=n-m;i--){key=i;DeleteBST(T,key);}}//按照相反顺序删除M个整数3.4按随机顺序插入N个整数，并按随机顺序删除voidRand(BiTree&T,intn,inta[]){//返回一随机数值，范围在0至RAND_MAX间 intj,p,i=0;srand((unsigned)time(NULL));//设置随机种子 for(i=0;i<n;i++){p=rand()%n;for(j=0;j<i;j++)if(p==a[j])break; if(j>=i)a[i]=p;else{i--;continue;}} for(i=0;i<n;i++)printf("%5d",a[i]);}StatusCreateBiTree(BiTree&T,intn,inta[]){ Rand(T,n,a);inti;T=NULL; for(i=0;i<n;i++){Insert(T,a[i]);}//随机输入不同的整数 returnok;}voidDele(BiTree&T,intm,intn,inta[]){ inti;intkey; for(i=0;i<m;i++){key=i;DeleteBST(T,a[i]);}}4.课程设计实验结果4.1课程实验数据要求N从1000到10000取值，测试3种数据结构的运行时间，通过MicrosoftVisualC++中配置文件的计时功能测试。4.2实验操作效率比拟图根据4.1中的数据绘图，以