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

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

1、数据结构课程设计题目二叉排序树的实现一、开发背景数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设计中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。Ｃ语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于Ｃ语言实现了对硬件的编程操作

2、，因此Ｃ语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。C是C++的基础，C++语言和Ｃ语言在很多方面是兼容的，C++程序员可以利用C++与C的兼容性而直接并有效的使用大量现成的程序库，从而开发出更简洁更高效的系统。需求分析：建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。该题目包括三方面的内容：一个是二叉排序树的建立，而是二叉树的中序遍历，三是二叉树元素的查找并删除。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。关键词：二叉排序树；中序遍历；搜索结点；删除结点；CC++二、课程设计题目1、二叉排序树的实现问题描述：用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车('')为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。2、课程设计要求在处理题目时，要求从分析题目的

4、需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述，用流程图或伪代码表示。说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。在写算法之前，应对数据结构进行设计。本题主要会用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。三、算法思

5、想1、二叉排序树的定义二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；（2）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（3）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（4）左、右子树本身又各是一棵二叉排序树2、二叉排序树的实现1）建立二叉排序树建立二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用

6、是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果b

7、有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。2）二叉排序树的中序遍历中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树（L）；访问根结点（V）；中序遍历右子树（R）。中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕3）二叉排序树中元素的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键