第九组数据结构课程设计报告

黄淮学院“数据结构”课程设计报告系 （院）： 信息工程学院设计题目： 二叉排序树的实现 专业班级： 软件工程 15 级 小组成员： 唐二虎、梦娟、贾月指导老师： 汪洋 完成时间： 2024.12.27 二叉排序树的实现1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、、成绩 3 项),对比查找效率，并说明为什么二叉排序树效率高（或者低）。2.程序设计流程图（设计思想）对二叉排序树 T 作中序遍历 , 并输出结果二叉链表作存储结构和顺序表作存储结构输入数列 L ， 以回车 (‘\\n’) 为输入结束标志生成二叉排序树 T ；找 到 该 节点 x存在含 x 的结点，则删除该结点，并作中序遍历无结点 x输入元素 x，查找二叉排序树 T详细设计思想：建立二叉排序树采纳边查找边插入的方式。查找函数采纳递归的方式进行查找。假如查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采纳递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采纳边查找边删除的方式。假如没有查找到，进行提示；假如查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。3.函数模块：3.1.主函数 main 模块功能1.通过 bstreeCreatTree()操作建立二叉排序树。2.在二叉排序树 t 过操作 bstreeInsertBST(bstreet,intkey,nametypename,double grade)插入一个节点。3. 从二叉排序树 t 过操作 void Delete(bstree&p)删除任意节点。4.在二叉排序树 t 过操作 bstnode *SearchBST(bstreet,keytype key)查找节点。5.在二叉排序树 t 过操作 p=SearchBST(t,key)查询，并修改节点信息6.非递归遍历二叉排序树。7.定义函数 void compare()对数组和二叉排序树的查找效率进行比较比较。3.2 创建二叉排序树 CreatTree 模块从键盘中输入关键字与记录，并同时调用插入函数并不断进行插入。最后，返回根节点 T。3.3 删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为*p（指向节点的指针为 p），其双亲节点为*f（节...