数据结构课设-二叉排序树

1、课程设计(论文)任务书 学院 专业 班 一、课程设计(论文)题目 二、课程设计(论文)工作自 年 月 日起至 年 月 日止。三、课程设计(论文) 地点: 四、课程设计(论文)内容要求：1本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义； （2）使学生熟练掌握数据类型的定义和实现； （3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计： 二叉排序树：将输入的n个关键字构建成为一棵二叉排序树，并按照层次输出。 文档检索系统：实现一个信息检索系

2、统，包含至少10条记录。（1）每条记录至少包含4个数据项（2）能够按照不同数据项的关键字进行查询。 校园导游咨询：参见数据结构题集P151。3课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分。学生签名： 2014年 12月 22日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）； （3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般

3、（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人： 职称： 讲 师 2014年12 月 31日正 文一、 数据结构定义1. 抽象数据类型本设计中用到的数据结构ADT定义如下：ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。数据关系 R：若D为空集，则称为二叉树；    若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关

4、系H下无前驱；  (2)  若D-rootNULL，则存在D-root的一个划分D1,D2,D3, ,Dm(m>0)，对于任意jk(1j,km)有DjDk=NULL,且对任意的i(1im)，唯一存在数据元素xiDi有<root,xi>H; (3) 对应于D-root的划分，H-<root,xi>,<root,xm>有唯一的一个划分H1，H2,Hm(m>0)，对任意jk(1j,km)有HjHk=NULL，且对任意i(1im),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root

5、的子树。基本操作P： CreateTree(&T,definition); 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。  InsertChild(&T,&p,I,c); 初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。 操作结果：插入c为中指结点的第棵子树。DeleteChild(&T,&p,i); 初始条件：树T存在，p指向T中某个结点，1ip指结点的度。 操作结果：删除中所指结点的第棵子

6、树。 LevelOrderTraverse(T,visit(); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：层序遍历T，对每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。 ADT BinaryTree2. 存储结构定义数据存储结构的C语言定义如下：#define maxx 1000typedef struct node int key; struct node *lchild; struct node *rchild;BSTNode;3. 基本操作数据结构的基本操作实现如下：/* 菜单界

7、面 */void showmenu() system("cls"); printf("nnnn"); printf("tt 请选择你要进行的操作 nn"); printf("ttn"); printf("tt n"); printf("tt 1.创建一颗具有 n 个元素的二叉排序树 n"); printf("tt 2.层次输出二叉树 n"); printf("tt 3.查找元素 n"); printf("tt 4.插入元素 n

8、"); printf("tt 5.删除元素 n"); printf("tt 6.退出程序 n"); printf("tt n"); printf("ttn");/* 向二叉排序树中插入元素 */int InsertBST(BSTNode *&p,int k) if(p = NULL) p = (BSTNode *)malloc(sizeof(BSTNode); p->key = k; p->lchild = p->rchild = NULL; return 1; else if(

9、k = p->key) return 0; else if(k < p->key) return InsertBST( p->lchild , k); else if(k > p->key) return InsertBST( p->rchild , k); /*查看关键字k的深度*/int finddepth(BSTNode *p,int k,int depth) if(p != NULL) if(p->key = k) return depth; else if(k > p->key) return finddepth(p->

10、;rchild,k,depth+1); else if(k < p->key) return finddepth(p->lchild,k,depth+1); /* 二叉排序树的层次遍历 */void showBST(BSTNode *p) BSTNode *qmaxx; int top,back; top = back = 0; if(p != NULL) printf("n %d",p->key); else return ; q+back = p; BSTNode *Knode; int now = 1; while(back != top) t

11、op = (top + 1) % maxx; Knode = qtop; if(Knode->lchild != NULL) if(now != finddepth(p,Knode->lchild->key,1) printf("n"); now = finddepth(p,Knode->lchild->key,1); printf(" %d",Knode->lchild->key); back = (back + 1) % maxx; qback = Knode->lchild; if(Knode->

12、;rchild != NULL) if(now != finddepth(p,Knode->rchild->key,1) printf("n"); now = finddepth(p,Knode->rchild->key,1); printf(" %d",Knode->rchild->key); back = (back + 1) % maxx; qback = Knode->rchild; /a+i = &ai printf("n");/* 创建一颗具有 n 个数据元素的二叉排序树*

13、/void CreateBSTNode(BSTNode *&p) system("cls"); int amaxx; int n, k; printf("请输入一个整数 n ："); scanf("%d",&n); int i = 0; printf("请输入 n 个整数并以空格隔开："); for(i = 0;i < n; +i) scanf("%d",&ai); printf("正在向二叉排序树中插入元素.n"); i = 0; while(

14、i < n) if(InsertBST(p,ai) = 1) printf("成功插入元素 %d:",ai); showBST(p); else printf("元素 %d 插入失败！n",ai); i+; printf("二叉排序树创建完成!n"); system("pause"); showmenu();/* 从二叉排序树中查找数据元素 k*/int searchBST(BSTNode *p,int k,int path,int i) if(p = NULL) return 0; if(p->key

15、 = k) printf("成功查找到关键字 %d ,其路径为: ",k); int j = 0; pathi+ = p->key; printf(" %d",path0); for(j = 1;j < i; +j) printf(" -> %d",pathj); printf("n"); return 1; pathi+ = p->key; if(p->key < k) return searchBST(p->rchild,k,path,i); else return s

16、earchBST(p->lchild,k,path,i); return 0;/* 当数据元素 k 有左右子树时的删除过程 */void deleteBST2(BSTNode *&p,BSTNode *&r) BSTNode *q; if(r->rchild = NULL) p->key = r->key; q = r; if(r->lchild = NULL)r = NULL; else r = r->lchild; free(q); else deleteBST2(p,r->rchild); /* 删除数据元素 k */void d

17、eleteBST1(BSTNode *&p) BSTNode *q; if(p->lchild = NULL) q = p; p = p->rchild; free(q); return ; if(p->rchild = NULL) q = p; p = p->lchild; free(q); return ; deleteBST2(p,p->lchild);/* 查找要被删除的数据元素 k */int deleteBST(BSTNode *&p,int k) if(p = NULL) return 0; else if(k > p->

18、key) return deleteBST(p->rchild,k); else if(k < p->key) return deleteBST(p->lchild,k); else deleteBST1(p); return 1; 二、 解题过程1. 问题分解该问题主要应实现以下功能：1. 创建一颗具有 n 个关键字的二叉排序树读取一个整数n代表有n个关键字需要被储存进二叉排序树中，然后通过调用函数把这n个关键字存进一颗二叉排树中2. 层次输出该二叉树要层次输出二叉树，就要先进行层序遍历该二叉树，再在输出完每一层的所有关键字之后进行一次换行，并且每一个关键字之间有一个

19、空格。输出来的每一层关键字将会左对齐。2. 模块结构系统主要由7个模块组成，分别是：菜单模块：界面展示模块，显示整个菜单二叉树创建模块：二叉排序树创建模块，创建一颗具有n个关键字的二叉排序树关键字插入模块：向二叉排序树中插入关键字二叉树输出模块：层次输出该二叉排序树关键字查询模块：在二叉排序树中查询关键字，并输出路径关键字删除模块：删除该二叉排序树中的关键字退出模块:一个break语句，跳出循环模块之间的结构如下：主函数菜单模块关键字删除模块退出模块关键字查询模块二叉树输出模块关键字插入模块二叉树创建模块退出程序3. 解题思路各模块的实现步骤为菜单模块：用一连串的printf( )语句输出一个

20、可视化的操作界面而已，除此之外该模块本身没有任何其他功能二叉树创建模块：首先，初始化一颗二叉树，然后根据要求，要创建一个具有n个关键字的二叉排序树，所以在此模块中，需要输入一个n，代表有n个关键字需要输入，然后输入n个关键字，这n个关键字用一个数组a储存，因为无法确认输入的n有多大，所以尽量把数组a的范围开大一点，在本程序中我把数组a的储存大小开到了1000 。如果需要，还可以开到更大。当把关键字成功存放在数组中后，就可以遍历一遍数组，并调用InsertBST( )函数（该函数的实现过程会在下面的插入模块中进行详细的解释）把关键字一个一个插入到我们创建的二叉树中，并在插入成功后调用showBS

21、T( )函数（该函数的实现过程在输出模块中）把当前的二叉树状态输出来。当然，如果插入失败了，则会提示哪个关键字插入失败！总之，该模块其实就是通过调用其他模块来实现二叉树的创建功能的。关键字插入模块：我主要是通过递归来实现关键字的插入功能的。根据二叉排序树的性质，根节点储存的关键字一定大于左子树中所有存在的关键字，一定小于右子树中所有存在的关键字。所以，便可通过递归，去查找即将要插入的关键字的位置在哪里。即：从根节点开始，判断所要插入的关键字和根节点的关键字的大小关系，如果当前节点关键字大于我们所要插入的关键字，则去把所要插入的关键字放入到左子树中进行递归。如果小于，则把所要插入的关键字放入到右

22、子树中进行递归。直到找到一个为“空”的指针，就把我们要插入的关键字放到该节点的数据域上，并返回1，表示关键字插入成功。当然，也有可能找到一个与所需要插入的关键字相等的节点，出现这种情况时则返回0，代表插入关键字失败，因为该关键字已经在该二叉树中了，不必再插入了。二叉树输出模块：要实现二叉树的层次输出，要做的便是两件事。1. 层序遍历该二叉排序树。 2. 输出完每一层的最后一个关键字后要进行换行。完成第一个要求很简单，我用的方法是定义一个数组，用来模拟队列。首先把根节点放入队列中。用一个while( )循环开始进行遍历，遍历的方法为：查看当前队头节点的左（右）子树是否为“空”，如果为空则不做处理

23、，不为空则把左（右）子树的指针放入到队尾，并把左右子树节点所储存的关键字输出到窗口中。其中，while( )循环结束的条件为：队列为空即跳出。因为当队列为空时，便表示已经把所有节点访问了一遍。至于第二件事，输出完每一层的最后一个关键字后要进行换行。我原本的想法是用一个函数计算树的每一层的关键字的个数，并且把他存储到一个宏定义的数组里，每次输出结完一层的关键字数量后便进行换行，不过这样写实在太麻烦了。所以我改进的想法是，再写一个finddepth(BSTNode *p,int k,int depth) 函数，用来查询关键字所在的深度。而finddepth( ) 函数的实现方法为，令depth初始

24、值为1，把被查询的关键字 k 和当前节点的关键字进行比较，如果被查询的关键字大（小）于当前节点的关键字则对左（右）子树进行递归，并且令 depth+1 ，如果相等，就说明找到了被查询的关键字，则返回depth 。depth便是该关键字的深度！而要到达换行的目的，则还需要在输出模块中的队列那个循环外面再加一个now变量，用来储存当前节点的深度，在输出层序遍历输出的时候，对每一个找到的关键字做一个判断，即，查看该关键字的深度是否和now相等，如果不相等则换行，并且把now进行更新，如果相等则不做处理。以上，便是我的二叉排序树的层次输出的思路。关键字查询模块：用一个searchBST(BSTNode

25、 *p,int k,int path,int i) 函数进行递归查找关键字 k ，其中path数组用来储存查找的路径，i表示“路径”上节点的个数。至于递归的方法，则是把被查询的关键字 k 和当前节点的关键字进行比较，如果被查询的关键字大（小）于当前节点的关键字则对左（右）子树进行递归，找到了k则输出所有路径并返回1，没有找到则直接返回0。关键字删除模块：因为删除关键字后，要使得该二叉树依旧是二叉排序树，所以要进行删除操作时需要考虑到4种情况。这4种情况分别为：1. 被删除的关键字所在的节点没有左右子树时，则直接删除该节点即可。 2. 被删除的关键字所在的节点“只”有左子树或者右子树，则只需要把

26、左子树或者右子树接到被删除节点的双亲节点上即可。3. 被删除的关键字所在的节点既有左子树又有右子树，那么，就需要进行特殊的替换了，通过递归查找被删除节点的左子树的最右节点。把该最右节点的关键字直接替换原节点的关键字，再把最右节点的左子树接到最右节点的双亲节点上。4. 被删除的关键字不在该二叉排序树中,此时则不做处理。三、 实现代码及注释#include <stdio.h>#include <windows.h>#include <malloc.h>#include <conio.h>int main( ) BSTNode *p = NULL; i

27、nt amaxx; int n, i; showmenu(); while(1) int c; c = getch(); c = c - '0' if(c = 1) CreateBSTNode(p); else if(c = 2) printf("该二叉树的层次遍历为："); showBST(p); system("pause"); showmenu(); else if(c = 3) int k; int pathmaxx; printf("请输入你要查找的元素："); scanf("%d",&a

28、mp;k); if(searchBST(p,k,path,0) printf("元素 %d 在该二叉树中存在！n"); else printf("元素 %d 在该二叉树中不存在！n"); system("pause"); showmenu(); else if(c = 4) system("cls"); int k; while(1) printf("请输入你要插入的数据元素："); scanf("%d",&k); if(InsertBST(p,k) = 1) pri

29、ntf("成功插入元素 %d:",k); showBST(p); printf("n"); else printf("元素 %d 插入失败！nn",k); int x; printf("是否需要继续插入数据元素？ 1.是 2.否nn"); x = getch(); x -= '0' if(x = 2) break; showmenu(); else if(c = 5) system("cls"); int k; while(1) printf("请输入你要删除的数据元素

30、："); scanf("%d",&k); if(deleteBST(p,k) printf("成功删除元素 %d!n"); printf("现在该二叉树如下："); showBST(p); printf("n"); else printf("删除失败！二叉树中没有该元素！"); int x; printf("是否需要继续删除数据元素？ 1.是 2.否nn"); x = getch(); x -= '0' if(x = 2) break; showmenu(); else if(c = 6) break; else printf("您输入的指令有误，请重新输入！n"); return 0;四、 实验结果1. 实验数据实验中输入的数据如下（数据右边的为解释）：1 /