第九组数据结构课程设计二叉排序树实现

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

1、黄淮学院“数据结构”课程设计报告系（院）：信息工程学院设计题目：二叉排序树的实现专业班级：软件工程15级小组成员：唐二虎、赵梦娟、贾月指导教师：汪洋完成时间：2016.12.2717二叉排序树的实现1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明为什么二叉排序树效率高

2、（或者低）。2.程序设计流程图（设计思想）无结点x存在含x的结点，则删除该结点，并作中序遍历找到该节点x输入元素x，查找二叉排序树T对二叉排序树T作中序遍历,并输出结果二叉链表作存储结构和顺序表作存储结构输入数列L，以回车(‘’)为输入结束标志生成二叉排序树T；17详细设计思想：建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结

3、点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。3.函数模块：3.1.主函数main模块功能1.通过bstreeCreatTree()操作建立二叉排序树。2.在二叉排序树t中通过操作bstreeInsertBST(bstreet,intkey,nametypename,doublegrade)插入一个节点。3.从二叉排序树t中通过操作voidDelete(bstree&p)删除任意节点。4

4、.在二叉排序树t中通过操作bstnode*SearchBST(bstreet,keytypekey)查找节点。5.在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息6.非递归遍历二叉排序树。7.定义函数voidcompare()对数组和二叉排序树的查找效率进行比较比较。3.2创建二叉排序树CreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后，返回根节点T。3.3删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节

5、点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为*p（指向节点的指针为p），其双亲节点为*f（节点指针为f）。若*p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；若*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接

6、前驱（或直接后继）。在二叉排序树中删除一个节点的算法为voidDeleteData(bstree&t,keytypekey)17若二叉排序树t中存在关键字等于key的数据元素，则删除该数据元素节点，并返回TRUE，否则返回FALSE。3.4插入模块二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子的节点。一个无序系列可以通过构

7、造一棵二叉排序树而变成一个有序系列，构造树的过程即为对无序系列进行排序的过程，并且每次插入的节点都是二叉排序树上新的叶子节点，则在进行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空即可。二叉排序树的插入算法为bstreeInsertBST(bstreet,intkey,nametypename,doublegrade)若二叉排序树中不存在关键字等于key的数据元素时，插入元素并返回TRUE。3.5查找模块二叉排序树又称二叉查找树，当二叉排序树不为空时，首先将给定的值和根节点的关键字比较，

8、若相等则查找成功，否则将依据给定的值和根节点关键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定义一个二叉排序树的查找算法为bstnode*SearchBST(bstreet,keytypekey)在根指针t所指向的二叉排序树中查找关键字等于key的数据元素，如成功，返回指向该元素节点的指针，否则返回空指针。3.6二叉排序树的遍历先序遍历也叫做先根遍历。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树