西电软件工程大作业二叉排序树.docx

1、西电软件工程大作业二叉排序树1.题目二叉排序树2.功能描述1. 构造二叉查找树（1）从文本文件中读入文本内容，能够分离出单词，过滤掉阿拉伯数字和标点符号，并将英文字母的大写形式全部转换成小写形式。（2）按照英文字母表的顺序构造英文单词的二叉查找树。当两个英文单词的首字母相同时，按第二个字母进行排序，依次类推。（3）当待插入的单词已在二叉查找树中，则将该单词的出现次数增1。2. 遍历二叉查找树（1）搜索：输入一个待检索单词，在二叉查找树中进行查找，如果能找到该单词，则输出该单词及其出现次数；（2）实现二叉查找树的中序遍历，并将遍历结果输出到屏幕上，包括单词和单词出现的位置。3. 删除结点：给定一

2、个停用词列表（停用词是指对搜索没有作用的词，如：of,and,a,an,the等等），将二叉查找树中的属于停用词表中的单词依次删除。4. 可以显示菜单，在菜单中可以进行如下四项操作（但并不局限这些操作）：（1）读入文本内容，包含若干英文单词、标点符号以及阿拉伯数字，用于构建二叉查找树。（2）输入停用词，每个停用词占一行。对于每个停用词，都需要删除二叉查找树中的相应结点，即：每输入一个停用词，执行一次删除结点的操作。（3）中序遍历二叉查找树，遍历结果中的每个单词占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。（4）输入查询词。对每个查询词，都需要在二叉查找树中的搜索相应结点，如果

3、找到，则输出该单词及其出现次数；如果未找到，则输出相应的信息。每个查询词的查询结果占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。3.流程图4.程序源代码和注释#include /头文件 #include #includetypedef char keytype; typedef struct node /定义结构体类型 keytype *key; /数据域 int weight; /权重 struct node *lchild,*rchild; /左右孩子指针 bstnode; bstnode*INSERTBST(bstnode*t,bstnode*s) /二叉排序树的（非递

4、归）插入 返回根节点 已知（根节点，插入节点） bstnode*f,*p; p=t; /p指向根节点 while(p!=NULL) /遍历树，直至找到相同单词或p为NULL f=p; /f指向p的双亲（当未找到相同单词） if(strcmp(s-key,p-key)=0) /单词相同频次加1 p-weight=p-weight+1; return t; if(strcmp(s-key,p-key)lchild; /查找左子树 else p=p-rchild; /查找右子树 if(t=NULL) return s; /原树为空，返回s为根节点 if(strcmp(s-key,f-key)lchi

5、ld=s; /s插入为f的左孩子 else f-rchild=s; /s插入为f的右孩子 return t;bstnode*CREATEBST() /读取文件并建立二叉排序树 返回根节点 bstnode *t,*s; long int i,j=0; char ch,string2000000; /声明总单词字符串长度 FILE*fp; fp=fopen(D:/工具/创建的文件/0.txt,r); /读取文件 do /去除非字母字符并将大写字母转换为小写字母 i=20*j; /使每个单词首字母间隔20 while(1) ch=fgetc(fp); /逐个读取字符 if(ch=a&ch=A&chl

6、child=s-rchild=NULL; /另新节点左右孩子为空 s-key=key; /新节点赋值 s-weight=1; /初始权重为1 t=INSERTBST(t,s); /把新节点插入到树中 key=key+20; /令key指向下一个单词首字母 return t; /返回根节点 bstnode*Search(bstnode*t,char*word) /二叉排序树的查找 返回所查找单词节点 已知(根节点,单词数组) bstnode*p; p=t; /令p指向根节点 while(p!=NULL) /遍历整个树 if(strcmp(word,p-key)=0) break; /查找正确，跳

7、出循环 else if(strcmp(word,p-key)lchild;/小于根节点令P指向其左孩子 else p=p-rchild; /大于根节点令P指向其右孩子 return p; /返回查找到的地址 void PutSearch(bstnode*t,char*word) /输出查找的单词和频次 已知（根节点,单词数组） bstnode*p; p=Search(t,word); /查找所需单词节点 if(p!=NULL) printf(%s %dn,p-key,p-weight);/查找成功输出单词和频次 else printf(There is not the word.n); /查找

8、不成功输出未查到 void inorder(bstnode*t) /中序遍历输出 已知（根节点） if(t!=NULL) /根节点不为NULL进行操作 inorder(t-lchild); /中序遍历左子树 printf(%s %d %pn,t-key,t-weight,t-key);/输出节点的单词频次和地址 inorder(t-rchild); /中序遍历右子树 bstnode*FindP(bstnode*t,bstnode*s) /遍历查找任意节点的双亲节点 返回这个节点的双亲节点 已知（根节点，查找节点） bstnode*m,*temp=NULL; /temp为标识符（判断是否查找成功

9、） m=t; /m指向根节点 if(t=NULL) return NULL; /根节点位NULL 返回NULL if(t=s) return NULL; /查找节点为根节点 返回NULL if(m-lchild=s|m-rchild=s) return m; /子节点为查找值 返回地址 else if(temp=FindP(m-lchild,s) return temp; /遍历左子树 ,未找到返回NULL if(temp=FindP(m-rchild,s) return temp; /遍历右子树 未找到返回NULL int LorR(bstnode*p,bstnode*s) /判断子节点为左

10、孩子还是右孩子 if(p-lchild=s) return 1; /左返回1 else return 2; /右返回2 bstnode*Max(bstnode*t) /查找二叉排序树中的最大节点(递归） 返回最大节点 已知（根节点） if(t-rchild!=NULL) Max(t-rchild); /右子树不为NULL，遍历右子树 else return t; /返回最大节点 bstnode*Deletenode(bstnode*t,bstnode*s) /删除停用词节点（遍历） 返回根节点 已知（根节点，删除节点） int d; bstnode*p,*m; if(s=NULL); /删除节

11、点在二叉排序树中不存在，直接返回根节点 else p=FindP(t,s); /查找停用词节点的双亲节点 if(s-lchild=NULL&s-rchild=NULL) /s为叶子节点 if(p=NULL) free(s); /s为根节点，直接释放 else d=LorR(p,s); /判断S为P的左孩子还是右孩子 if(d=1) /左孩子 p-lchild=NULL; /将其双亲节点左孩子指针置空 free(s); /释放S节点 if(d=2) /右孩子 p-rchild=NULL; /将其双亲节点孩子指针置空 free(s); /释放S节点 else if(s-lchild!=NULL&s

12、-rchild=NULL) /s仅有左子树 if(p=NULL) /s为根结点 free(s); return s-lchild; /返回s的左孩子节点 else d=LorR(p,s); /判断S为P的左孩子还是右孩子 if(d=1) /左孩子 p-lchild=s-lchild; /将S的左孩子成为p的左孩子 free(s); /释放S节点 if(d=2) /右孩子 p-rchild=s-lchild; /将S的左孩子成为p的右孩子 free(s); /释放S节点 else if(s-lchild=NULL&s-rchild!=NULL) /s仅有右子树 if(p=NULL) /s为根结点

13、 free(s); return s-rchild; /返回s的右孩子节点 else d=LorR(p,s); /判断S为P的左孩子还是右孩子 if(d=1) /左孩子 p-lchild=s-rchild; /将S的右孩子成为p的左孩子 free(s); /释放S节点 if(d=2) /右孩子 p-rchild=s-rchild; /将S的右孩子成为p的右孩子 free(s); /释放S节点 else if(s-lchild!=NULL&s-rchild!=NULL) /s既有左子树又有子树 m=Max(s-lchild); /中序遍历查找s左子树最大节点 s-key=m-key; /以最大节

14、点代替删除节点 s-weight=m-weight; Deletenode(s,m); /删除最大节点 return t; int main() char e=end,word20; /end作为中止符 char x; /x为操作符 bstnode*t,*s; printf(-操作选项-n); /建立菜单 printf(1:读入文本建立二叉排序树n); printf(2:输入停用词删除节点n); printf(3:二叉树中序遍历输出n); printf(4:查询单词并输出频次n); printf(5:退出程序n); printf(-n); while(1) /不断执行菜单内容直至退出程序 pr

15、intf(输入数字选择执行操作：); scanf(%c,&x); /输入操作种类 fflush(stdin); /清除输入缓冲流中的回车符（scanf所产生） if(x=5) break; /程序退出 switch(x) /判断操作类型 case 1:t=CREATEBST(); break;/读入文本建立二叉排序树 case 2:while(1) /连续删除停用词，直到输入end printf(输入停用词（end为终止符）:); gets(word); if(strcmp(word,e)=0) break; /终止删除停用词，返回菜单 else s=Search(t,word); /查找停用

16、词地址 t=Deletenode(t,s); /删除停用词 break; case 3:inorder(t); break; /中序遍历输出 case 4:while(1) /连续查询，直至输入end printf(输入查询单词（end为终止符）：); gets(word); if(strcmp(word,e)=0) break; /终止查询，返回菜单 else PutSearch(t,word); /查询单词并输出频次 break; default:printf(输入错误请重输n); break; /提示输入的是非法操作符 return 0; 5.数据检测1.读入的文件2.检测步骤及结果读入

17、文件-中序遍历输出-查找（for,the）-停用（for,the）-查找（for,the）-中序遍历输出-结束程序6.心得体会在编程过程，学会了由文本文件读取文本内容，并在其中删除非字母字符和转换大小写。通过使用long大大增加了可读入内容的数量，通过网上查询的方式解决了scanf语句后gets语句无法运行的问题，解决了在不存在双亲指针的二叉排序树查找双亲节点。但是还存在当文本文件太大时无法运行，以及存在插入删除中有end作为标识符在操作时无法作为目的字符操作。此次编程启发了我，编写程序不是一帆风顺的，在过程中会出现很多问题，要分块分析问题的来源，在自己无法独立解决时与他人交流想法或网上学习都能给自己一些启发。多进行一些测试，是找出问题的重要方法，也是确保正确的重要途径。在本次编程中我都在各种数据的测试下寻找到的几处只有在特定树的结构下才会出现的问题。