logo资料库

数据结构课程设计二叉排序树的实现.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.60M 资料格式：docx 举报 版权申诉
第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
资料共27页，剩余部分请下载后查看
    二叉排序树的实现
    课程设计要求：
    1、编程实现二叉排序树， 包括生成、插入、删除；
    1.2生成一颗二叉排序树
    2、对二叉排序树进行先根、中根、 和后根非递归遍历；
    3、每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
    3.1打印二叉排序树
    3.2给排序树加上树枝
    3.3写打印树函数遇到的困难和总结
    4、分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项)
    4.1初始化数组和二叉排序树
    4.2写这个函数遇到的问题：
    课 程 设 计 课程名称 数据结构课程设计 题目名称 二叉排序树的实现 学生学院 应用数学学院 专业班级 信息计算 1 班 学 号 3114008104 学生姓名 陈辉腾 指导教师 刘志煌 2016 年 6 月 27 日 1
    二叉排序树的实现 应数 14 信计 1 班 3114008104 陈辉腾 课程设计要求： 二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的 数据小于右边. 1）编程实现二叉排序树， 包括生成、插入，删除； 2）对二叉排序树进行先根、中根、 和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 例如,a 为根,左右孩子是 bc,b 的孩子是 de,c 的孩子是 fg. 也可以像这样更加美观: 也可以是竖着显示,a 为根,bc 为孩子. 4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 5） 格式就要按照我们作业的要求,对数据测试,分析,总结 和改进的工作要做的详细一点。 2
    1、编程实现二叉排序树， 包括生成、插入、删除； 1.1 数据类型定义 方法一：手工输入，递归生成。 1.2 生成一颗二叉排序树 生成一颗二叉排序树如下： 这样生成一棵二叉排序树，就是要自己判断每个结点应该放在什么地方，因为二叉排 序树规定了二叉排序树左边的数据小于右边。显然，这样每次构建一棵二叉排序树都需要事先 规定好一个数据元素序列，然后依次输入。这样的弊端就是你不细心一点就有可能构建出一棵 错误的二叉排序树——非二叉排序树。优点就是可以构建自己想要的二叉排序树。 3
    方法二：随机生成。 这里用到了C++里面的rand()函数，用于生成大于等于0的伪随机数(每次运行产生的随 机数都是固定的)。用这个函数需要使用名字空间using namespace std;同时引进 #include。 思路是：按依次插入结点来生成一棵二叉排序树，在插入函数里进行判断：即编写生 成二叉排序树的规则。另外，事先要有一堆结点（用于生成二叉排序树），我是事先保存在一 个数组里。然后每次产生一个伪随机数（范围是0到数组长度）作为数组下标，并把对应的该下 标的数组元素插入到要生成的二叉排序树里。 其中for循环次数就是生成二叉排序树结点个数的最大值减1。最大是因为产生的伪随 机数可能会重复，而重复的结点不再插入树中。减1是因为根结点我事先就定义了，它的data默 认为30，默认为30的目的是因为我可以产生0—64的伪随机数，学号范围也是暂时定在0—64这 个范围。这样规定可以照顾生成的左右子树尽量均衡，即靠近完全二叉排序树。要靠近完全二 叉树是因为到时打印一颗树的时候，打印的层数（树的深度）尽量少，因为到时候打印一棵树， 深度越大就越难控制。（当然也可以把上述函数的2,3,4行注释起来，这样就要保证T一开始是 空树。） 其中 InsertBST()函数为： 在插入一个结点的函数里，首先要找一下原树里有没有与即将被插入的结点元素相同 的结点元素。有的话就放弃插入，没有就进行与根结点判断大小，小就插到它的左边作为左孩 子，大的就到右边。 其中查找函数 SearchBST()为： 4
    查找函数是递归定义，同时也用到了比较函数 LT(a,b)。 LT(a,b)比较函数定义如下： 在比较函数里又用到了字符串比较函数strcmp(a,b)。这个函数c++里面有，只要 #include就行了。但是它比较的是字符串。由于对于我来说我的关键字是学号，比 较的就是学号，所以我用比较数值型的比较函数就够了（学号暂时用两位数，因为打印树的时 候占用位置少，还有就是用整形int可以存得下）。于是自己写了比较函数。 即： 函数名字忘记改了，不能见名知义，不过没关系了。 运行结果： 经过验证，是成功的生成了一棵二叉排序树。for 循环了 8 次，此时生成了 9 个结点， 说明产生的伪随机数没有重复，而且随机构造的树也基本左右均衡。 1.3 对生成的二叉排序树插入一个节点 生成了一棵二叉排序树，接下来对它插入一个结点。（其实生成树时一直在插入，不 过还是做一下验证一下。由于产生的是伪随机数，所以运行结果和上次一样） 5
    插入关键字（学号）为 27 的结点后，它已成功接到关键字为 26 的结点右边作为其右孩子。并 以树的形状打印出来。所以，插入结点是成功的。 1.4 对生成的二叉排序树删除一个结点 对二叉排序树进行删除操作，删除函数代码为： 此函数也是递归调用。其中 EQ()函数和 LT()函数上面有说明。这里关键是 Delete()函数， 定义如下： 6
    在原来树插入结点 27 后，删除结点 54 的运行结果为： 所以，由遍历结果和打印结果知，删除是成功的。 2、对二叉排序树进行先根、中根、 和后根非递归遍历； 非递归遍历要用到栈，自己有写栈的各种操作。另外，我发现可以用 C++库里面人家写 好的，include 进来就可以直接调用，以下代码有些是用自己写的栈，有些是用 C++库里面的 （感觉别人写的很好用，比如调试的时候查看栈内元素就比自己写的简单明了）。思路都写在 代码的注释里面面，个人觉得这样好看些，截图放入 word 文档就省去排版了，更方便理解。 2.1 栈相关数据类型及函数定义 初始化栈 InitStack()函数为： malloc 是存储空间分配函数，返回分配空间的首地址，所以一开始 S.base 和 S.top 保 存的是首地址,即栈顶指针和栈底指针指向同一个地方。其实栈是一个数组。 判断栈是否为空的 StackEmpty()函数： 7
    访问元素的 visit()函数： 入栈 Push()函数： 入栈后栈顶指针上移，指向一个待存数据的位置。 出栈 Pop()函数： 出栈后栈顶指针下移，指向下一个数据的位置。 2.2 先、中、后序非递归遍历算法 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料