欢迎来到天天文库
浏览记录
ID:47519948
大小:345.51 KB
页数:36页
时间:2020-01-12
《用顺序和二叉链表作存储结构实现二叉排序树全代码》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构课程设计安徽新华学院数据结构课程设计报告题目:用顺序和二叉树存储结构实现二叉树排序学院:信息工程专业:信息与计算科学班级:12信科本一班姓名:李智学号:1242155110指导教师:李明设计时间:2013-12-16至2013-12-30数据结构课程设计课程设计任务书一.设计任务研究关于如何创建二叉排序树并对树进行遍历,查找和删除等操作,同时关注用顺序和二叉链表作存储结构带来的区别。二.设计要求(1).利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。(2).利用顺序存储和链式存储两种算法计算
2、实现中序遍历。(3).利用顺序存储和链式存储两种算法计算实现查找结点。(4).利用顺序存储和链式存储两种算法计算实现删除结点。三.设计期限2013-12-16至2013-12-30数据结构课程设计前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树,可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树,一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。二叉树是树形结构的一个重要的类型,二叉树是n(
3、n>=0)个结点的有限集,它或者是空集(n=0),或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比较简单,特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点,按照一定的次序顺序,存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树,对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。现实中有许多应用到二叉树的例子,所以我们要把理论与现实结合起来。在学习中主要掌握
4、怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。数据结构课程设计目录1需求分析11.1问题的提出11.2任务与分析12总体设计22.1二叉排序树的建立22.2二叉排序树的中序遍历22.3二叉排序树中元素的查找22.4二叉排序树中元素的删除32.5总体设计流程图3详细设计63.1中序遍历模块93.2删除模块94编码与调试124.1顺序存储124.2二叉链表存储165总结19总 结19心得体会20参考文献21全部代码22二叉链表结构c22二叉链表结构c++26顺序存储结构c291需求分析1
5、.1问题的提出研究关于如何创建二叉排序树并对树进行遍历,查找和删除等操作,同时关注用顺序和二叉链表作存储结构带来的区别。1.2任务与分析用顺序和二叉链表作存储结构实现二叉排序树:(1)以回车('')为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”。2总体设计2.1二叉排序树的建立建二叉树的结点至少应当包含三个域,分别存放结点的数据data,左子女
6、结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点从空的二叉排序树开始,经过一系列的查找插入操作以后,生成了一棵二叉排序树。根据二叉排序树的定义,建立一棵二叉排序树的过程是按照待排序序列元素的先后次序,不断动态生成二叉树的结点,逐个插入到二叉树中。若p为根结点指针,b为当前待插入元素,其过程可以描述为:若为空树(p=nil),动态生成一个结点,其数据域为当前待插入元素b,左、右指针域为“空”,p指向该结点。若非空树,
7、比较b与根结点数据data(p)如果b8、,最后访问右子树.直至所有的结点都被访问完毕。2.3二叉排序树中元素的查找在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素,查找过程从根结点开始。如果根指针为NULL,则查找不成功;否则用给定值x与根结点的关键码进行比较;如果给定值等于根结点的关键码,则查找成功,返回查找成功的信息,并报告查找到的结点地址。如
8、,最后访问右子树.直至所有的结点都被访问完毕。2.3二叉排序树中元素的查找在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素,查找过程从根结点开始。如果根指针为NULL,则查找不成功;否则用给定值x与根结点的关键码进行比较;如果给定值等于根结点的关键码,则查找成功,返回查找成功的信息,并报告查找到的结点地址。如
此文档下载收益归作者所有