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

《数据结构课程设计--二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、成绩：__________课程设计（数据结构）院、系计算机与软件学院专业软件工程姓名学号指导教师二零一二年十二月二十五日4目录1.绪论12.课程设计12.1课程设计目的12.2课程设计要求13.课程实验内容23.1普通二叉排序树的插入，删除23.2按递增顺序插入N个整数，并按同样顺序删除23.3按递增顺序插入N个整数，并按相反顺序删除23.4按随机顺序插入N个整数，并按随机顺序删除34.课程设计实验结果34.1课程实验数据34.2实验操作效率比较图44二叉排序树魏麟祥南京信息工程大学计算机与软件学院，南京210044摘要：本文主要是对二

2、叉排序树的操作效率进行探讨，先从二叉排序树的定义来进行分析，然后分析其主要的性质。通过对其性质的分析，让人们了解二叉排序树的运行。从理论上分析二叉排序树的创建、删除、插入以及遍历，运用C语言算法编程实现对普通二叉排序树制定操作，通过普通二叉排序树对实例的运行时间来判断普通二叉排序树的运行效率。关键词：二叉排序树；C语言；随机函数1.绪论通过对数据结构的不断学习，对二叉排序树有了一定的了解。在教材中，只是从理论上说明了二叉排序树的定义及其效率，并没有用具体算法的在计算机上实现。就此问题，本文在其理论的基础上给出了具体的算法。利用普通二叉排

3、序树的定义，为了更详细的描述二叉排序树的算法，文章采用C语言来编程实现。该算法主要描述二叉排序树的建立，删除，插入以及遍历等操作。通过分别测试3类数据来直观的表现出普通二叉排序树的运行效率。2.课程设计2.1课程设计目的掌握了解二叉排序树插入删除的效率，通过合作写程序提高自己的设计能力和测试的能力。在写程序的时候能了解自己的不足，提高自己解决问题的能力。2.2课程设计要求对普通二叉排序树实现定制操作，分析这一数据结构对应的插入和删除操作效率。要求对N个不同整数进行下列操作：（1）按递增顺序插入N个整数，并按同样顺序删除；（2）按递增顺序

4、插入N个整数，并按相反顺序删除；（3）按随机顺序插入N个整数，并按随机顺序删除；要求N从1000到10000取值，并以数据规模N为横轴，运行时间为纵轴，画出3种不同数据结构对应的操作效率比较图。43.课程实验内容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;//被插结点

5、*s为新的根结点elseif(edata)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(keydata)returnDeleteBST(T->lchil

6、d,key);elsereturnDeleteBST(T->rchild,key);}}3.2按递增顺序插入N个整数，并按同样顺序删除StatusCreateBiTree(BiTree&T,intn){inti;T=NULL;for(i=0;i

7、3.3按递增顺序插入N个整数，并按相反顺序删除voidDele(BiTree&T,intm,intn){inti;intkey;for(i=n-1;i>=n-m;i--){key=i;DeleteBST(T,key);}}//按照相反顺序删除M个整数43.4按随机顺序插入N个整数，并按随机顺序删除voidRand(BiTree&T,intn,inta[]){//返回一随机数值，范围在0至RAND_MAX间intj,p,i=0;srand((unsigned)time(NULL));//设置随机种子for(i=0;i

8、and()%n;for(j=0;j=i)a[i]=p;else{i--;continue;}}for(i=0;i