1、10计本数据结构课程设计报告1安徽省巢湖学院计算机与信息工程学院课程设计报告 课程名称 数据结构 课题名称 二叉排序树 专 业 计算机科学与技术 班 级 学 号 姓 名 xxxx 联系方式 指导教师 xxxxx 20 11 年 12 月 25 日目 录1、数据结构课程设计任务书 1.1、题目 1.2、要求 2、总体设计 2.1、功能模块设计 2.2、所有功能模块的流程图 3、详细设计 3.1、程序中所采用的数据结构及存储结构的说明 3.2、算法的设计思想 4、调试与测试： 4.1、调试方法与步骤： 4.2、测试结果的分析与讨论： 5、时间复杂度的分析： 6、源程序清单和执行结果 7、C程序设计
2、总结 8、致谢 9、参考文献 1.数据结构课程设计任务书1.1、题目 二叉排序树1.2、要求（1）用BiTree CreatBST创建二叉排序树模块；（2）用DeleteNode实现删除模块；（3）用void InsertBST1实现插入模块；（4）用BiTree searchBST1实现查找模块；2.总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：3.详细设计3.1程序中采用的数据结构及储存结构说明：模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；1）主函数模块 Main()建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点
3、,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于 key2 的数据元素；2）创建二叉排序树模块BiTree CreatBST(int n)建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程； 3）删除模块DeleteNode(BiTree &T, int x)从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块void InsertBST1(BiTree &T,BiTNode *s)在二叉树排序树T中，
4、插入一个结点s(递归算法)； 被CreatBST函数调用； 5）查找模块BiTree searchBST1(BiTree T,TElemType key)在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；3.2算法的设计思想 1、二叉排序树的查找，即给定值先与根结点比较，若相等则查找成功，否则根据根据他们之间的大小关系，分别在左子树或右子树查找。 2、二叉排序树的插入，插入的一定是叶子结点，根据查找结果决定插入位置。 3、二叉排序树的删除分三种情况： 1)若*p结点为叶子结点，即PL和PR均为空树。由于删除叶子结点不破坏
5、整棵树的结构，则只需改其双亲结点的指针即可。 2)若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。3)若*p的左右子树均不空。令*p的左子树为*s的左子树，*p的右子树为*s的右子树，如图。4、调试与测试4.1、调试方法与步骤：第一步：创建一个二叉树；第二步：查找一个结点；第三步：删除一个结点；第四步：插入一个结点； 4.2、测试结果的分析与讨论：1,程序运行时菜单显示如下：当输入的二叉树序列为：2,6,9,8,4时，创建二叉排序树，并输出结果如下：1.查找9结点时，运行结果如下：2.删除结点6时运行结果如下：3.插入结点7时运行结果如下：5
6、、时间复杂度的分析：a)查找由于查找需要访问所有结点，故时间复杂度为O（t）b）删除删除需要访问结点找到所要删除的结点，则时间复杂度是O（t）c）插入 由于插入结点处即为查找和删除的结点处，即O（t）6、源程序清单和执行结果#includeusing namespace std;typedef int KeyType;typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针 struct tree *right; /存放又子树的指针 KeyType key; /存放节点的内容 BSTNode, * BSTree; /声明二叉树的链表BSTr
7、ee insertBST(BSTree tptr,KeyType key)/ 在二叉排序树中插入结点 /若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回 BSTree f,p=tptr; /p的初值指向根结点 while(p) /查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲 if(p-key=key) /树中已有key，无须插入 return tptr; f=p; /f保存当前查找的结点，即f是p的双亲 p=(keykey)?p-left:p-right; p=(BSTree )malloc(sizeof(BSTNode); /生成新结点 p-key=key
8、; p-left=p-right=NULL; if(tptr=NULL) /原树为空，新插入的结点为新的根 tptr=p; else if(keykey) f-left=p; else f-right=p; return tptr;BSTree createBST()/建立二叉树 BSTree t=NULL; /根结点 KeyType key; cinkey; while(key!=-1) t=insertBST(t,key); cinkey; return t;void inorder_btree(BSTree root)/ 中序遍历打印二叉排序树 BSTree p=root; if(p!=
9、NULL) inorder_btree(p-left ); cout keyright ); int searchBST(BSTree t,KeyType key)/查找 if(key=t-key) return 1; if(t=NULL) return 0; if(keykey) return searchBST(t-left,key); else return searchBST(t-right,key);BSTree deleteBST(BSTree tptr,KeyType key)/删除 BSTree p,tmp,parent=NULL; p=tptr; while(p) if(p-
10、key=key) break; parent=p; p=(keykey)?p-left:p-right; if(!p) return NULL; tmp=p; if(!p-right&!p-left) /*p的左右子树都为空*/ if(!parent) /要删根，须修改根指针 tptr=NULL; else if(p=parent-right) parent-right=NULL; else parent-left=NULL; free(p); else if(!p-right) /p的右子树为空，则重接p的左子树 p=p-left; if(!parent) /要删根，须修改根指针 tptr=
11、p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子树为空，则重接p的左子树 p=p-right; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子树和右子树，用p的后继覆盖p然后删去后继 /另有方法：用p的前驱覆盖p然后删去前驱|合并p的左
12、右子树 parent=p; /由于用覆盖法删根，则不必特殊考虑删根 p=p-right; while(p-left) parent=p; p=p-left; tmp-key=p-key; if(p=parent-left) parent-left=NULL; else parent-right=NULL; free(p); return tptr;int main() KeyType key; int flag,test; char cmd; BSTree root; do coutnnendl; couttt*请选择你要执行的操作:*endl; coutnendl; couttt C.创建一
13、棵二叉排序树n; couttt E.结束本程序n; coutnntt*endl; flag=0; do if(flag!=0) coutcmd; flag+; while(cmd!=c&cmd!=C&cmd!=a&cmd!=A); if(cmd=c|cmd=C) cout请输入你所要创建的二叉树的结点的值，以-1结束：n; root=createBST(); do flag=0; coutnn中序遍历二叉树：endl; inorder_btree(root); coutnendl; couttt*请选择你要对这棵二叉树所做的操作:*endl; couttt* *endl; couttt* S.
14、查找你想要寻找的结点 *endl; couttt* I.插入你想要插入的结点 *endl; couttt* D.删除你想要删除的结点 *endl; couttt* Q.结束对这棵二叉树的操作 *endl; couttt* *endl; couttt*endl; do if(flag!=0) cout选择操作错误！请重新选择！n; fflush(stdin); scanf(%c,&cmd); flag+; while(cmd!=s&cmd!=S&cmd!=i&cmd!=I&cmd!=d&cmd!=D&cmd!=q&cmd!=Q); switch(cmd) case s: case S: cout
15、key; test=searchBST(root,key); if(test=0) coutn对不起，你所查找的结点 key不存在!; else coutn成功找到结点nkey ; break; case i: case I: coutkey; root=insertBST(root,key); /注意必须将值传回根 break; case d: case D: coutkey; root=deleteBST(root,key); /注意必须将值传回根 if(root=NULL) coutn对不起，你所删除的结点 key 不存在!n; else coutn成功删除结点 key ; break;
16、 while(cmd!=q&cmd!=Q); while(cmd!=e&cmd!=E); return 0;7、C程序设计总结通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程中和同学相互讨论，询问老师，不断进步。也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。 看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。8、致谢能够完成这次课程设计必须感谢C语言课程老师张步群和C+语言程序设计老师许荣泉。9、参考文献1 严蔚敏，吴伟民，数据结构（C语言版）北京：清华大学出版社，1997.42 谭浩强，C程序设计（第四版），北京：清华大学出版社，2010.63 郑莉，董渊，何江舟，C+语言程序设计 北京：清华大学出版社，2010.7
