排序二叉树的应用数据结构专业课程设计报告样本.doc

1、排序二叉树的应用数据结构专业课程设计报告数据结构课程设计报告题目 : 排序二叉树的应用一、设计任务1、 程序在运行时，可以执行有关排序二叉树的操作：如插入一个元素、删除一个元素、查找一个元素、打印一个元素等。2、 用递归算法遍历二叉树。二 、设计分析1 、 二叉树是n（n=0）个结点的有限集合，它或为空树（n=0），或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。二叉树是一个递归定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左而右。2 、 二叉树的存储结构1） 顺序存储结构：二叉树可以采用顺序存贮结

2、构，即用一维数组来存放二叉树的数据元素。它是按照满二叉树的结点层次编号层次来依次存放二叉树中的数据元素。2）链式存储结构：设计不同的结点结构可构成不同形式的链式存储结构。在本程序中，采用顺序存储结构，对二叉树进行插人、删除、查找、遍历等操作。3 、 二叉树的建立已知一棵二叉树，共有n个结点，建立的方法如下：1） 照完全二叉树的编号方法，对该二叉树进行编号。2） 次输入一个结点的值x和该结点的编号k，动态申请一块空间来存放该结点，空间的地址为p。3） 把p值赋给adrk中。4） 如果k=1，转到5；否则，把p的值填入其父结点的指针域中。p的父结点地址为adrk/2，若k为偶数，则做adrk/2-

3、lc=p；若为奇数，则做adrk/2-rc=p。5） 重复24，直到全部顶点数据输入完为止。4 、 遍历二叉树，即如何按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。一棵非空二叉树是由根结点（D）、左子树（L）和右子树（R）三个基本部分组成。要遍历这三个基本部分，可以有六种可能的顺序。若限定先左后右，则只有三种情况：先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。在本程序中，遍历二叉树函数的核心是以一个简单的case语句来实现的。5 、 二叉树的插入操作：这个操作首先生成一个新的结点结构，把数据存入新结点，然后搜索二叉树寻找插入结点的位置，再把新结点连接

4、到二叉树。把这个操作定义为一个函数，其函数名为instree。6 、 二叉树中元素的查找：在许多情况下，我们需要在一棵已知的二叉树中查找某个元素，以确定树中是否存在这个元素。这种查找与链表数据结构中查找成员的情况极类似。查找函数名字定义为membertree。7 、 从二叉树中删除一个成员：进行成员删除操作时，首先必须用递归函数遍历这棵树，找到这个元素。当找到这个元素之后，还要考虑以下四种不同的情况：删除一个终端结点；删除只有一个左孩子的结点；删除只有一个右孩子的结点；删除带有两个孩子的结点。删除函数名字定义为deltree。8 、 在主函数main( )中，除了初始化指针tp之外，用循环语句

5、while(1)在屏幕上显示出主菜单：I Insert an element into treeDDelete an element from the treeFFind a member in the treePPrint the treeQQuit用户可以根据自己的需要，从键盘键入不同的合法字母（例如I），而进入不同的树处理函数进行处理。不同树处理函数的选择是通过简单的switchcase语句来实现，其中包括了若错技术。如果用户从键盘输入的不是I，D，F，P，Q这些合法字符，则程序会先告诉用户输入出错，让用户重新输入，直到输入选择正确为止。三 、设计思路1 、主函数main() ：由cas

6、e语句组成，支持程序选择，当运行时，可以执行有关二叉树的操作：如插入一个元素、删除一个元素、查找一个元素、打印一个元素等。2 、主要的树函数的说明部分1）void prttree(treeptr tnode,int t)；/打印树。该函数在屏幕上打印出存放在树中的元素，如果是空树，则无输出。参数：tnode-指向根结点的指针； t-打印方式：0：前序 1：中序 2：后序（用递归算法遍历二叉树）。 2）treeptr instree(char *s,int key,treeptr tnode)；/插入一个元素。该函数把一个元素插入到二叉树中。参数：s,key-接收插入数据； tnode-是指向根

7、结点的指针。3）treeptr membertree(char *s,treeptr tnode)；/查找一个元素。该函数测定树中的指定元素，如果元素是树中的成员，则函树返回该元素，否则返回NULL指针.。参数：s-指向要找的那个串的指针；tnode-指向树根结点的指针。4）treeptr deltree(char *s,treeptr tnode)；/删除一个元素。该函数删除一个结点。参数：s-要删除的结点的数据域的值； tnode-指向根结点的指针。5）treeptr findinspos(char *s,treeptr tnode)；/该函数寻找一个元素要插入的位置。开 始四 、流程图输

8、 入ch1、main( ) 函 数 I P D F Q 其exit 它输入s,key 输 入输 入 s s printf tp!=NULL tp=deltree Y N (s,tp) t=membe -tree(s,tp) printf printf break Yt!=NULLN 输 入 printf printf任 意 数输 入 i break输 入 任 意 数prttree(tp,i)break输入任意数break结 束 2、主 要 树 函 数1） prttree( ) 函 数 开 始 tnode Y !=NULL Nt 0 1 2prttree(tnodprttree(tnodepri

9、ntf-e-left,t) -left,t)prttree(tnod printfprttree(tnod-e-left,t)-e-right,t)prttree(tnod prttree(tnod-e-right,t) -e-right,t)printf结 束2) instree( ) 函 数开 始 为t1分配空 间 Y t1=NULL N printf t1-right=NULLprintft1-left=NULLreturnt1-key(tnode) =key strcpy(t1-data,s)Ytnode=NULL N returnt2=findinspos(s,tonde) (t1)

10、 Y (strcmp(t2-data,s)right=t1 t2-left=t1return(tnode)结 束3) membertree( ) 函 数 开 始 t=tnode Nt!=NULL Ycmp=strcmp(t-data,s)Y cmp=0 Nreturn(t)Y cmpright t=t-left return(NULL)结 束4) findinspos( ) 函 数开 始Y(strcmp(tnode-data,s)=0NY tnode-left=NULL NYtnode-right=NULL N return(tnode) findinspos(s,tnode-left)ret

11、urn(tnode) findinspos(s,tnode-right) 结 束5) deltree( ) 函 数 开 始tnode=NULL Yreturn(NULL)ch=strcmp(tnode-data,s)Y ch=0 N无孩子 ch0 Nfree(tno Y 无左孩子 N tnode-left=del tnode -de- -tree(s,tnode-left) -rightdata) =deltree t1=tnode- Y 无右孩子 N (s,tnode right -right) t1=tno t1=tnode free(tn -de- -righ-ode) free(tno

12、 left -de-da -ta) t2=tnodereturnfree -right(NULL) (tnode- free data) (tnode)t2-left!=NULL N free Y return (tnode) (t1) t2=t2-leftreturn(t1) t2-left= tnode-left free(tnode-data) free(tnode) return(t1) 结 束五、源程序程序清单：#include #include #include #include #include typedef struct treenode *treeptr; /重定义机构指针

13、类型为treeptrstruct treenode /树结点的基本数据结构int key; /数据域char data20; /数据域treeptr left,right; /左,右指针;/主要的树函数的说明部分void prttree(treeptr tnode,int t);treeptr instree(char *s,int key,treeptr tnode);treeptr membertree(char *s,treeptr tnode);treeptr deltree(char *s,treeptr tnode);treeptr findinspos(char *s,treep

14、tr tnode);main( )treeptr tp,t;char ch;char s80;int key;int i;tp=NULL; /初始化根结点指针while(1)clrscr();gotoxy(20,5);printf(I-Insert an element into the tree);gotoxy(20,6);printf(D-Delete an element from the tree);gotoxy(20,7);printf(F-Find a member in the tree);gotoxy(20,8);printf(P-Print the tree);gotoxy(

15、20,9);printf(Q-Quit);gotoxy(20,12);print(Make a seletion );ch=getche();ch=toupper(ch);switch(ch)case I:printf(nEnter element name ); /插入一个元素scanf(%s,s);printf(nEnter element key (a number) );scanf(%d,&key);if(tp=instree(s,key,tp)!=NULL)printf(nElement inserted,press any key to continue);elseprintf(n

16、Element cant be inserted,press any key to continue);getch();break;case D:printf(nEnter element ); /删除一个元素scanf(%s,s);tp=deltree(s,tp);break;case F:printf(nEnter element ); /查找一个元素scanf(%s,s);t=membertree(s,tp);if(t!=NULL)printf(n The Element is %s %d,t-data,t-key);elseprintf(nElement not found);getc

17、h();break;case P: /打印树gotoxy(20,14);printf(0-Prinf preorder);gotoxy(20,15);printf(1-Prinf inorder);gotoxy(20,16);printf(2-Prinf postorder);gotoxy(20,18);printf(Enter option );scanf(%d,&i);printf(n);prttree(tp,i);getch();break;case Q:exit(0); /退出default:printf(nInvalid selection);/主要树函数void prttree(t

18、reeptr tnode,int t)/该函数在屏幕上打印出存放在树中的元素,如果是空树,则无输出./参数：tnode-指向根结点的指针;*/t-打印方式:0:先序1:中序 2:后序if(tnode!=NULL) /打印成员switch(t)case 0:printf(n%s :%d,tnode-data,tnode-key);prttree(tnode-left,t);prttree(tnode-right,t);break;case 1:prttree(tnode-left,t);printf(n%s:%d,tnode-data,tnode-key);prttree(tnode-right

19、,t);break;case 2:prttree(tonde-left,t);prttree(tonde-right,t);printf(n%s:%d,tnode-data,tnode-key);break;default:printf(nInvalid printf selection);treeptr instree(char *s,int key,treeptr tnode)/该参数把一个元素插入到二叉树中./参数：s,key-接收插入数据;tnode-是指向根结点的指针treeptr t1,t2;t1=(treeptr)malloc(sizeof(struct treenode); /

20、分配空间if(t1=NULL)printf(Memory is fulln);printf(Insert is failuren);return(tnode);elset1-right=NULL;t1-left=NULL;t1-key=key;strcpy(t1-data,s);if(tnode=NULL)return(t1);elset2=findinspos(s,tnode); /得到要插入的位置if(strcmp(t2-data,s)right=t1; /插入右孩子elset2-left=t1; /插入左孩子return(tnode); /插入完毕treeptr membertree(c

21、har *s,treeptr tnode)/该函数测定树中的指定元素,如果元素是树中的成员,则函树返回该元素,否则返回NULL指针/参数：s-指向要找的那个串的指针;tnode-指向树根结点的指针.treeptr t;int cmp;t=tnode;while(t!=NULL)cmp=strcmp(t-data,s);if(cmp=0)return(t); /找到元素else if(cmpright; /查找右子树 elset=t-left; /查找左子树return(NULL);treeptr deltree(char *s,treeptr tnode)/该函数删除一个结点/参数：s-要删除

22、的结点的数据域的值;tnode-指向根结点的指针.treeptr t1,t2;int ch;if(tnode=NULL)return(NULL); /元素不能删除ch=strcmp(tnode-data,s); /比较元素if(ch=0) /找到元素if(tnode-right=NULL)&(tnode-left=NULL) /结点就是要删除的结点free(tnode-data);free(tnode);return(NULL);else if(tnode-left=NULL) /删除只带右孩子的根结点t1=tnode-right; /使右孩子成为一棵新树根free(tnode-data);f

23、ree(tnode);return(t1);else if(tnode-right=NULL)/删除只带左孩子的根结点t1=tnode-left; /使左孩子成为一棵新的根free(tnode-data);free(tnode);return(t1);else /删除带左,右孩子的根结点t1=tnode-right; /使右结点成为新根t2=tnode-right;while(t2-left!=NULL) /查找新根左边所有的结点t2=t2-left;t2-left=tnode-left; /连结老根的左结点free(tnode-data);free(tnode);return(t1);els

24、eif(ch0)tnode-left=deltree(s,tnode-left);elsetnode-right=deltree(s,tnode-right);return(tnode);treeptr findinspos(char *s,treeptr tnode)/该函数寻找一个元素要插入的位置if(strcmp(tnode-data,s)=0)if(tnode-left=NULL)return(tnode);elsefindinspos(s,tnode-left);elseif(tnode-right=NULL)return(tnode);elsefindinspos(s,tnode-

25、right);六 、参考资料1 、赵逢禹、罗道昆、路玲、杜光耀 . 数据结构与C语言高级程序设计 . 北京航空航天大学出版社2 、严蔚敏、吴伟民 . 数据结构(C语言版) . 清华大学出版社3 、严蔚敏、吴伟民、米宁 . 数据结构题集(C语言版) . 清华大学出版社七 、用户手册本程序在VC+环境下运行八 、运行结果 A: 九、课程总结短短二周的课程设计时间很快就过去了，而我所选的“二叉树的应用”设计题目也接近尾声。这期间，有老师的指导，有同学的帮助，有自己不懂就翻阅资料寻求解答的努力。经过磕磕碰碰总算完了任务。虽然所做的程序算不上了自己最满意的，但却是这二个星期以来的努力成果，是这学期学数据结构的总结，是对自己能力的考验，是自己尽最大努力做出来的。在课程设计的过程当中，是对平时学习的检测，虽然平时书上所讲似乎懂了，就如我所做的“二叉树的应该”一样，但在真正设计起程序来，很多困难还是意想不到的，那只能在设计过程中不断的摸索，在摸索中不断提升自己。二周课程设计的时间是过去了，但是，对数据结构的学习似乎才是开始，以后要学习的还很多很多，前面要走的路还很远很远。而我也要整装待发，在摸索中前进，在前进中不断摸索，让自己的路走得更远更长！彭福原 2005年6月