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

成绩： _ 课程设计（数据结构）院、系 计算机与软件学院专业 软件工程姓 名 学号 指导教师 二零一二 年 十二 月 二十五 日4目 录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普通二叉排序树的插入，删除Status Insert(BiTree &T,int e)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为新的根结点else if(edata)p-lchild=s; / 被插结点*s为左孩子else p-rchild=s; / 被插结点*s为右孩子return ok;else return false;Status DeleteBST(BiTree &T,int key) /若二叉排序树T存在关键字等于key的数据元素时，则删除该数据元素结点if(!T)return false;else if(key=T-data)return Delete(T);else if(keydata)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key); 3.2按递增顺序插入N个整数，并按同样顺序删除Status CreateBiTree(BiTree &T,int n)int i;T=NULL;for(i=0;in;i+)int key=i;Insert(T,key); /循环插入N个整数return ok;void Dele(BiTree &T,int m,int n)int i;int key;for(i=0;i=n-m;i-)key=i;DeleteBST(T,key); /按照相反顺序删除M个整数3.4按随机顺序插入N个整数，并按随机顺序删除void Rand(BiTree &T,int n,int a) /返回一随机数值，范围在0至RAND_MAX 间int j,p,i=0;srand(unsigned)time(NULL); /设置随机种子for(i=0;in;i+)p=rand()%n; for(j=0;j=i)ai=p;elsei-;continue;for(i=0;in;i+)printf(%5d,ai);Status CreateBiTree(BiTree &T,int n,int a)Rand(T,n,a);int i;T=NULL;for(i=0;in;i+) Insert(T,ai); /随机输入不同的整数return ok;void Dele(BiTree &T,int m,int n,int a)int i;int key;for(i=0;im;i+)key=i; DeleteBST(T,ai);4.课程设计实验结果4.1课程实验数据要求N从1000到10000取值，测试3种数据结构的运行时间，通过Microsoft Visual C+中配置文件的计时功能测试。4.2实验操作效率比较图根据4.1中的数据绘图，以数据规模N为横轴，运行时间为纵轴制作3种数据结构的操作效率比较图。参考文献1严蔚敏 吴为