用顺序和二叉链表作存储结构实现二叉排序树全代码

安徽新华学院数据结构课程设计报告题目：用顺序和二叉树存储结构实现二叉树排序学院：信息工程专业：信息与计算科学班级：12信科本一班姓名：李智学号：1242155110指导教师：李明设计时间：2013-12-16至2013-12-30数据结构课程设计课程设计任务书一．设计任务研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。二．设计要求（1）.利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。（2）.利用顺序存储和链式存储两种算法计算实现中序遍历。（3）.利用顺序存储和链式存储两种算法计算实现查找结点。（4）.利用顺序存储和链式存储两种算法计算实现删除结点。三．设计期限2013-12-16至2013-12-30数据结构课程设计前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。二叉树是树形结构的一个重要的类型，二叉树是n（n=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。数据结构课程设计目录1需求分析................................................................................................................................11.1问题的提出.....................................................................................................................11.2任务与分析......................................................................................................................12总体设计................................................................................................................................12.1二叉排序树的建立..........................................................................................................12.2二叉排序树的中序遍历..................................................................................................22.3二叉排序树中元素的查找..............................................................................................22.4二叉排序树中元素的删除..........................................................................................................22.5总体设计流程图3详细设计.................................................................................................错误!未定义书签。3.1中序遍历模块.................................................................................................................73.2删除模块.........................................................................................................................74编码与调试.............................................................................................................................94.1顺序存储.......................................................................................................................104.2二叉链表存储...............................................................................................................145总结......................................................................................................................................17总结.................................................................................................错误!未定义书签。心得体会...............................................................................................................................18参考文献..................................................................................................................................19全部代码..................................................................................................................................20二叉链表结构C....................................................................................................................20二叉链表结构C++...............................................................................................................24顺序存储结构C....................................................................................................................27-1-1需求分析1.1问题的提出研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。1.2任务与分析用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。2总体设计2.1二叉排序树的建立建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果bdata(p),将b插入左子树中；如果b≥data(p)，将b插入右子树中；左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。-2-2.2二叉排序树的中序遍历中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树（L）；访问根结点（V）；中序遍历右子树（R）。中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。2.3二叉排序树中元素的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。2.4二叉排序树中元素的删除对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。-3-2.5总体设计流程图4.1程序总体流程图初始化输入数据无X查找函数中序遍历遍历结果插入节点X12删除节点存在含x的结点不存在输出遍历结果-4-3．详细设计Tnode的声明typedefstructTnode{intdata;structTnode*lchild,*rchild;}*node,