数据结构课程设计报告---二叉排序树实现集合的运算

1、 数据结构课数据结构课程设计报告程设计报告 设计题目设计题目 二叉排序树实现集合的运算二叉排序树实现集合的运算 班班 级级 信息管理信息管理 1 1 班班 学学 号号 一一引言引言 数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数 据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存 储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设 计程序中的数据采用“树形结构”作为其数据结构。而二叉排序树又是一种特殊的二 叉树。本课程设中的二叉排序树是用来实现集合中的运算功能，一共要实现五项集合 的基本的功能。它们分别是集合的元素判定，子

2、集判定，交，并，差运算。实现这五 项基本功能的目的是为了巩固和运用理论知识、锻炼实践能力、构件合理知识结构和 提高程序设计能力。 二二正文正文 1 需求分析需求分析 1.1 课程设计题目、任务及要求课程设计题目、任务及要求 （1） 用二叉排序树实现集合的元素判定，子集判定，集合的交，并，差的运算； （2） 集合的元素限整数； （3） 程序运行时要先显示题目，班级，学号，姓名，完成时间等信息。 1.2 课程设计思想课程设计思想 a.用二叉排序树建立集合，然后用二叉排序树的算法实现集合的元素判定，子集 判定，集合的交并差的运算；可见，要想完成集合的这些算法，最主要运用到 了二叉排序树里面的查找算法

3、，然后将数组与二叉排序树结合起来，来实现这 些算法。 b.查找函数采用递归的方式进行查找； 对二叉排序树进行中序遍历采用递归函数的方式：在根结点不为空的情况下， 先访问左子树，再访问根结点，最后访问右子树。由于二叉排序树自身的性质， 左子树小于根结点，而根结点小于右子树，所以中序遍历的结果是递增的。 2 概要设计概要设计 2.1 对二叉排序树的理解对二叉排序树的理解 二叉排序树是一种动态数表。 二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树： （）每个结点都有一个作为搜索依据的关键码（key） ，所有结点的关键码互不相同； （）若它的左子树非空，则左子树上所有结点的

4、值均小于根结点的值； （）若它的右子树非空，则右子树上所有结点的值均大于根结点的值； (4) 左、右子树本身又各是一棵； （5）左、右子树本身又各是一棵二叉排序树。 2.2 建立二叉排序树（二叉链表做存储结构）建立二叉排序树（二叉链表做存储结构） 从空的二叉排序树开始，经过一系列的查找插入操作以后，生成一棵二叉排序树。 根据二叉排序树的定义， 建立一棵二叉排序树的过程是按照待排序序列元素的先后次序， 不 断动态生成二叉树的结点，逐个插入到二叉树中。其过程可以描述为： BSTree createBST(int *iArr)/建立集合二叉排序树 BSTree t=NULL; /根结点 KeyType key; int i=0; if(!*iArr) cinkey; while(key!=-1 for(i=1;ileft ); coutkey) re