排序二叉树的应用_数据结构课程设计报告

-1/14-前言数据结构是研究数据之间关系的一门科学，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。同一逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“二叉树结构”。具体采用的是“二叉排序树”，并且使用“一维数组”作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自左而右、自上而下存储二叉排序树的结点元素；本课程设计实现了二叉排序树的创建、查找、插入、删除，中序遍历输出等基本操作，完美地实现了二叉排序树的大部分功能。二叉树是树形结构的一个重要抽象数据类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序时计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。排序在我们日常生活中随处可见，经常会用到，因此，学习和研究各种排序方法是计算机工作者的重要课题之一。二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。顺应二叉树的这个特点来进行对二叉树的排序操作，这个问题也就思路清晰，设计起来没那么困难了。二叉树有5种基本形态，二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。即空二叉树，只有一个结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，左右子树均非空的二叉树。这些形态在后面的设计程序中均可以实现.正文1.1课程设计的教学目的及任务(1)使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2)使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。(3)使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。1.2课程设计的主要内容(1)问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？-2/14-(2)逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明）。(3)物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚(5)程序调试与测试。利用VC++6.0调试程序，能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6)结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。(7)撰写课程设计报告2.1课程设计的要求1、根据所学知识并自主查找相关资料；2、进行算法设计与分析；3、算法实现，测试并检验运行结果是否符合要求；4、书写课程设计说明书2.2问题描述排序在我们日常生活中随处可见，经常会用到，因此，学习和研究各种排序方法是计算机工作者的重要课题之一。二叉排序树是一种简单的树的排序方法，排序原理简单易懂，具有较高的易学性与理解性。2.3数据结构分析-3/14-2.3.1抽象数据类型定义（ADT）抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。2.3.2抽象数据类型结构抽象数据类型可用三元组表示（D,S,P）其中，D是数据对象，S是D上的关系集，P是D的基础操作集。用以下格式定义抽象数据类型：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基础操作：基本操作的定义}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名初始条件：初始条件描述操作结果：操作结果描述基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除提供输入值外，还将返回输入结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化情况和应返回的结果。若初始条件为空，则省略之。2.4二叉排序树设计分析2.4.1二叉树的全面定义二叉树是n（n=0）个结点的有限集合，它或为空树（n=0），或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。二叉树是一个递归定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的结点进行连续编号，一开始就规定编号从根结点起，自上而下，自左而右。2.4.2二叉树的存储结构1）顺序存储结构：二叉树可以采用顺序存贮结构，即用一维数组来存放二叉树的数据元素。它是按照满二叉树的结点层次编号层次来依次存放二叉树中的数据元素。2）链式存储结构：设计不同的结点结构可构成不同形式的链式存储结构。在本程序中，采用顺序存储结构，对二叉树进行插人、删除、查找、遍历等操作。2.4.3二叉树的建立已知一棵二叉树，共有n个结点，建立的方法如下：1）照完全二叉树的编号方法，对该二叉树进行编号。2）次输入一个结点的值x和该结点的编号k，动态申请一块空间来存放该结点，空间的地址为-4/14-p。3）把p值赋给adr[k]中。4）如果k=1，转到5；否则，把p的值填入其父结点的指针域中。p的父结点地址为adr[k/2]，若k为偶数，则做adr[k/2]-lc=p；若为奇数，则做adr[k/2]-rc=p。5）重复2~4，直到全部顶点数据输入完为止。6）遍历二叉树，即如何按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。一棵非空二叉树是由根结点（D）、左子树（L）和右子树（R）三个基本部分组成。要遍历这三个基本部分，可以有六种可能的顺序。若限定先左后右，则只有三种情况：先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。在本程序中，遍历二叉树函数的核心是以一个简单的case语句来实现的。7)二叉树的插入操作：这个操作首先生成一个新的结点结构，把数据存入新结点，然后搜索二叉树寻找插入结点的位置，再把新结点连接到二叉树。把这个操作定义为一个函数，其函数名为instree。8)二叉树中元素的查找：在许多情况下，我们需要在一棵已知的二叉树中查找某个元素，以确定树中是否存在这个元素。这种查找与链表数据结构中查找成员的情况极类似。查找函数名字定义为membertree。9)从二叉树中删除一个成员：进行成员删除操作时，首先必须用递归函数遍历这棵树，找到这个元素。当找到这个元素之后，还要考虑以下四种不同的情况：删除一个终端结点；删除只有一个左孩子的结点；删除只有一个右孩子的结点；删除带有两个孩子的结点。删除函数名字定义为deltree。2.4.4二叉排序树的查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。平均情况分析（在成功查找两种的情况下）在一般情况下，设P（n，i）且它的左子树的结点个数为i时的平均查找长度。如图的结点个数为n=6且i=3;则P（n,i）=P（6,3）=[1+(P(3)+1)*3+(P(2)+1)*2]/6=[1+(5/3+1)*3+(3/2+1)*2]/6注意：这里P(3)、P(2)是具有3个结点、2个结点的二叉分类树的平均查找长度。在一般情况，P（i）为具有i个结点二叉分类树的平均查找长度。P(3)=（1+2+2）/3=5/3P(2)=（1+2）/2=3/2∴P（n,i）=[1+(P(i)+1)*i+(P(n-i-1)+1)*(n-i-1)]/nn-1∴P（n）=∑P（n,i）/n=2(1+I/n)lnni=0因为2(1+I/n)lnn≈1.38logn故P(n)=O(logn)2.5设计思路-5/14-2.5.1二叉排序树的操作实现目的主函数main()：由简单的if语句外加自定义函数，支持程序选择，当运行时，可以执行有关二叉树的操作：建立二叉排序树，如插入一个元素、删除一个元素、查找一个元素、等。此次设计仅此设立简单的几种操作，主要是让大家认识和真正理解二叉排序树。2.5.2二叉排序树的分块流程图二叉排序树的建立二叉排序树的遍历（分块）先序遍历中序遍历后序遍历2.5.3简单举例分析例如：给定一组序列{8，,1,6,78,5,96,56,7}利用二叉排序树的特点构造一个二叉排序树。具体做法如下（全例流程图解）：88612861257（a）（b）（c）86125778-6/14-861257785696（d）（e）先序：（先根遍历）865712785696中序：（中根遍历）567812567896后序：（后根遍历）576569678128以上（a）—（e）过程就是二叉排序树的构建与排序的过程，简单说，就是在一组数中，取一个元素为根节点，以所选根节点为准，比根节点大的为左子树，比根节点小的做为右子树，另外，左右子树又可以做为根节点，同样原理对二叉树进行排序，直到左右子树后再无其他可以排序的元素为止。在进行遍历操作的时候，除根节点便利是顺序变化，其余的都是先左子树，后右子树的顺序。2.5.4主要的树函数的说明及关键代码分析部分1）voidprttree(treeptrtnode,intt)；//打印树。该函数在屏幕上打印出存放在树中的元素，如果是空树，则无输出。参数：tnode-指向根结点的指针；If{Else}语句While{}语句结构体定义类型（struct）Break语句t-打印方式：0：先序1：中序2：后序（用递归算法遍历二叉树）。#includestdlib.h：库函数的头文件，stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、-7/14-wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。structbtree*left;structbtree*right;}BTR,*PBTR;这就利用了struct结构类型定义建立的二叉排序树。第一块：函数功能：实现非递归建立二叉树函数原型：voidcreat_btree(int*a,intsize)函数参数：int*a:保存二叉树节点的数组首地址intsize:节点数目函数返回值：void优点：建立的二叉树按中序遍历后：是从小到大有序的可以是一种排序算法第二块：函数功能：实现递归前序遍历二叉树函数原型：voidpreorder(PBTRhea