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

《数据结构课程设计--二叉排序树》由会员分享，可在线阅读，更多相关《数据结构课程设计--二叉排序树（6页珍藏版）》请在毕设资料网上搜索。

1、 成绩：成绩： _ 课程设计（数据结构）课程设计（数据结构） 院、系院、系 计计算机与软件学院算机与软件学院专业专业 软件工程软件工程 指导教师指导教师 二零一二二零一二 年年 十二十二 月月 二十五二十五 日日 I 目 录 1.绪论 1 2.课程设计 . 1 2.1 课程设计目的 1 2.2 课程设计要求 1 3.课程实验内容 . 2 3.1 普通二叉排序树的插入，删除 . 2 3.2 按递增顺序插入 N 个整数，并按同样顺序删除 2 3.3 按递增顺序插入 N 个整数，并按相反顺序删除 2 3.4 按随机顺序插入 N 个整数，并按随机顺序删除 3 4.课程设计实验结果 . 3 4.1 课程

2、实验数据 3 4.2 实验操作效率比较图 4 1 二叉排序树 摘要摘要：本文主要是对二叉排序树的本文主要是对二叉排序树的操作效率操作效率进行探讨，先从二叉排序树的定义来进行分析，然后进行探讨，先从二叉排序树的定义来进行分析，然后分析其主要的性质。分析其主要的性质。 通过对其性质的分析，让人们了解二叉排序树的运行通过对其性质的分析，让人们了解二叉排序树的运行。从理论上分析二叉排序树的创建、删除、插入以及遍历，运用。从理论上分析二叉排序树的创建、删除、插入以及遍历，运用 C C 语语 言算法编程实现言算法编程实现对对普通二叉排序树制定操作，通过普通二叉排序树对实例的运行时间来判断普通二叉排序树的运

3、行效率普通二叉排序树制定操作，通过普通二叉排序树对实例的运行时间来判断普通二叉排序树的运行效率。 关键词关键词：二叉排序树；C 语言；随机函数 1.绪论 通过对数据结构的不断学习，对二叉排序树有了一定的了解。在教材中，只是从理论上说明了二叉排 序树的定义及其效率，并没有用具体算法的在计算机上实现。就此问题，本文在其理论的基础上给出了具 体的算法。利用普通二叉排序树的定义，为了更详细的描述二叉排序树的算法，文章采用 C 语言来编程实 现。该算法主要描述二叉排序树的建立，删除，插入以及遍历等操作。通过分别测试 3 类数据来直观的表 现出普通二叉排序树的运行效率。 2.课程设计 2.1 课程设计目的

4、 掌握了解二叉排序树插入删除的效率，通过合作写程序提高自己的设计能力和测试的能力。在写 程序的时候能了解自己的不足，提高自己解决问题的能力。 2.2 课程设计要求 对普通二叉排序树实现定制操作，分析这一数据结构对应的插入和删除操作效率。要求对 N 个不 同整数进行下列操作： （1）按递增顺序插入 N 个整数，并按同样顺序删除； （2）按递增顺序插入 N 个 整数， 并按相反顺序删除； （3） 按随机顺序插入 N 个整数， 并按随机顺序删除； 要求 N 从 1000 到 10000 取值，并以数据规模 N 为横轴，运行时间为纵轴，画出 3 种不同数据结构对应的操作效率比较图。 2 3.课程实验内

5、容 3.1 普通二叉排序树的插入，删除 Status Insert(BiTree 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 else if(key=T-data)return Delete(T); else if(keydata)return DeleteBST(T

6、-lchild,key); else return DeleteBST(T-rchild,key); 3.2 按递增顺序插入 N 个整数，并按同样顺序删除 Status CreateBiTree(BiTree T=NULL;for(i=0;in;i+)int key=i;Insert(T,key); /循环插入 N 个整数 return ok; void Dele(BiTree int key; for(i=0;i=n-m;i-)key=i;DeleteBST(T,key); /按照相反顺序删除 M 个整数 3 3.4 按随机顺序插入 N 个整数，并按随机顺序删除 void Rand(BiTree 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)