数据结构课程设计说明书排序二叉树的建立及遍历的实现.doc

课程设计任务书学生姓名： XXX 专业班级： 计算机0502 指导教师： XXX 工作单位：计算机科学与技术学院 题 目: 二叉排序树的建立及遍历的实现初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）建立二叉排序树；（2）中序遍历二叉排序树并输出排序结果；2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。时间安排： 2007年7月2日7日 （第18周）7月2日 查阅资料7月3日 系统设计，数据结构设计，算法设计7月4日-5日 编程并上机调试7月6日 撰写报告7月7日 验收程序，提交设计报告书。指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日排序二叉树的建立及其遍历的实现摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历0引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归调用，这将极大的方便算法设计。1需求分析建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。2数据结构设计在写算法之前，应对其进行数据结构设计。本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。结点结构体定义：typedef struct tnode /*建立节点*/ int data; struct tnode *lchild,*rchild;TNODE; 3算法设计 在进行算法设计时，应将题目分为两部分，排序二叉树的建立，排序二叉树的遍历。3.1 定义结点typedef struct tnode /*建立节点*/ int data; struct tnode *lchild,*rchild;TNODE;TNODE *q; /*构造指针变量*/TNODE *bt;3.2 插入结点函数insert() Void insert(TNODE *b,TNODE *s)/*排序二叉树中插入节点*/ if(*b)=NULL)(*b)=s; else if(s->data=(*b)->data) return; else if(s->data<(*b)->data) insert(&(*b)->lchild),s); else if(s->data>(*b)->data) insert(&(*b)->rchild),s); 3.3 创建树函数creat()void creat(TNODE *b) /*建立排序二叉树*/ int x; TNODE *s; b=NULL; /*初始化二叉数*/ scanf("%d",&x); s=(TNODE *)malloc(sizeof(TNODE); q=s; /*将根结点指针地址赋值给q*/ while(x!=-1) /*反复读入节点,直至-1结束*/ s->data=x; s->lchild=NULL; s->rchild=NULL; insert(&bt,s); scanf("%d",&x); /*节点插入排序二叉树中*/ s=(TNODE *)malloc(sizeof(TNODE); n=n+1; 3.4 求排序二叉树的深度int deep(TNODE *t) /*求排序二叉树的深度 */ int rd; int ld; if(!t) return 0; else ld=deep(t->lchild); rd=deep(t->rchild); if(ld>rd) return ld+1; else return rd+1; 3.5 建立先序遍历函数void preorder(TNODE *p) /*先序遍历二叉树*/ if(p) printf("%4d",p->data) ; preorder(p->lchild); preorder(p->rchild); 3.6 中序遍历void inorder(TNODE *p) /*中序遍历二叉树*/ if(p) inorder(p->lchild); printf("%4d",p->data) ; inorder(p->rchild); 3.7 后序遍历void postorder(TNODE *p) /*后序遍历二叉树*/ if(p) postorder(p->lchild); postorder(p->rchild); printf("%4d",p->data) ; 这三个函数都应用了递归调用。最后，在主函数中分别调用所建立的函数，3.8 有关技术的讨论 在设计程序时，我发现用递归函数来写程序会简洁很多，能大大的缩小程序的代码，在求排序二叉树的深度，先序遍历排序二叉树，中序遍历排序二叉树以及和；后序遍历排序二叉树中，都用到了递归函数，大大简化了源程序的代码。在输入数据时，用 while函数会使数据能够不断的输入进来，解决了无法从外部输入数据的问题，用的很巧妙。4程序实现 4.1 调入文件#include<math.h>#include<stdio.h>#include <stdlib.h>4.2 主函数main()void main() /*主函数*/ printf("please insert the numbers(when you finish inserting numbers,please insert -1 to the end):n"); creat(bt); /*构造排序二叉树*/ printf("the numbers of the nodes are:%4d",n); /*输出排序二叉树的结点数*/ printf("nthe depth of the tree:"); printf("%4d",deep(q); /*求二叉树的深度*/ printf("npreorder,the result is:"); preorder(q); /*先序遍历排序二叉树*/ printf("ninorder,the result is:"); inorder(q); /*中序遍历排序二叉树*/ printf("npostorder ,the result is:"); postorder(q); /*后序遍历排序二叉树*/ getchar();然后输出结果。在设计中，最难的那一部分为求插入结点函数，在函数内部要进行比较，将较小的数赋给左子树，将将较大的数赋给右子树。在其他的算法设计中，只要理清思路就不会太难。4.3 运行结果 显示程序：输入数据： 输出结果： 5.设计体会我感受最深的一点是以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的思路该怎么设计，在哪一阶段该设计什么。经过这一次设计，我学会了怎样设计程序，怎样控制整个程序，它使我学会了怎样设计程序，设计算法，设计课题。通过这个星期的课程设计，我的收获还是不少。我的c语言水平有了比较大的提高，其中c语言关于指针，链表的操作理解的比以前深刻不少。另外是数据结构方面的提高，对存储结构，及各种查找排序方面也有不少的提高。虽然我做的程序里还有写问题，做的不够深入，但独立完成一个比较大一点的程序的经历也是很宝贵的。通过这次课程设计我觉得我们学习数据结构的方法存在一定的弊端数据结构的效果直接影响到我们对其它专业课的学习和今后业务的成长。我觉得我们对于数据结构的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。整个实验过程要结合教学进度与我们的实际情况，制定实验的内容。实验分两部分，一是验证性的，主要结合课堂理论教学内容展开，学生可以对在课堂上学到的基本算法进行验证；二是设计性实验，坚持“学以致用”的原则，目的是让学生充分利用所学的理论知识进行相对复杂的应用设计，以进一步提高综合能力和创新实践能力。通过这次设计，我感慨颇多，的确，从选题到定稿，从理论到实践，在一个星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故。6.结束语本文主要是排序二叉树的建立及其遍历的实现，其主要功能有：对输入的数据形成排序二叉树，并求出排序二叉树的节点和深度，并对排序二叉树进行先序遍历，中序遍历和后序遍历，输出其结果。参考资料 1严蔚敏, 吴伟名.数据结构 清华大学出版社 2001年1月 2谭浩强.C程序设计 清华大学出版社 2002年1月 3赵仲孟 ,张蓓. 数据结构典型题解析西北工业大学出版社 2002年8月 4钱能编. C+程序设计教程 清华大学出版社 2005年2月